AtCoder AGC026B rng_10s

　AtCoder は競技プログラミング寄りのサイトということで、あまりやりこんでもしかたないような気がするが、ある程度の点数取れるようがんばるとそれなりにアルゴリズムの知識が身につくことに気付き、しばらくやってみることにした。paiza の方が問題は実務的な気がするが、 AtCoder はよくも悪くもアケスケで、わからなくても人のやり方を覗き見できるところがよい。

AtCoder Problems

　ABS という導入(初心者向け過去問よりぬき)をひととおりやってみてなんだこんなもんかと思ったので次は過去問をひととおりやってみるのも手かと上のようなサイトをみて、初心者向けの ABC とかやってみたが、AB が簡単すぎる反面 D でつまづくことが多くてバランスが悪い。それにどうもテストケースの甘さが気になるので上記リンクの一番上にある AGC というのに手を出してみてとりあえず一番上からやってみようとしたら、しょっぱなの A (AGC026A) からつまづいた。テストケースがちゃんと境界値とか上限を突いてくる。ナメてたのでこれはつらい。やりがいあるので他のもやってみようと、B に手を出したらこれがまったくわからず、降参して解法をみたがそれでもわからない。B - g + A%g のあとに (B/g -1) * inv(D/g,B/b) とあるあたりに 1 mod Y とあるのに至っては理解もできない。ただし人の提出解答をみてようやく納得したので、だれかの役にたつかもしれんと残しておく。

　問題の構造はこうで、A が初期量、B が定常購入量、C が補充の閾値で、D が補充量。A < B だと即死、D < B でもほぼ即死、B <= C だと不死。これらは決まっているのでそうでないとき( A >= B 、D >= B 、B > C )、どうなるかが問題の焦点となる。A % B が C より大きいときがマヌケワナで補充できずに死んでしまうというところまではわかったが、その次がどう考えたらいいのかよくわからなかった。

　D の m倍 % B が C より大きいときが落とし穴で、このとき補充できずに死ぬのだが、この B と D の繰り返し寄せる波をどう表現したらいいのかよくわからなかった。見当がつかないので A%B にならってあれこれ剰余を出していじったあげく自爆して降伏して解説を見てそれでもわからず人の解答をみたのだが、ここまで図示してようやくわかった。この B と D の波の波長は最大公約数 g なので図で示すところの「差」は最大公約数 g の倍数になる。したがって閾値 C + 波の最小単位 g が B より小さければ、落とし穴にはまるのである。波、波と書いているが、差分( mD % B )の増減を波と表現しているのでつまり差分(波)の最小単位が最大公約数 g であることは自明なのだが、解法をみるまで気付かなかったのは自分の未熟であった。

　さてここで最初 B と D の波と C の関係という風に見たとき、初期値の余りの A%B は波のどっかの切片になるので考える必要はないとおもってたのだが、解法をみると A%g という項が入っていて考慮にいれることになっており複雑な説明がついていて訳がわからない。

　...と思っていろいろ書いていたが、この A%g は既に C < A % Bで足切りしてるので考慮する必要がなさそうだ。だから考え方としてはまちがってなかったわけだな。うーむなるほど。とことんわかってなくてつらい。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

import sys

iT = int(input())
aR = [[int(x) for x in sLine.split()] for sLine in sys.stdin.readlines()]

def fGcd(iX,iY):
    while iY:
        iX,iY= iY,iX%iY
    return iX

def fFunc(iA,iB,iC,iD):
    ig = fGcd(iB,iD)
    if iA < iB or iD < iB:
        return False
    elif iC >= iB :
        return True
    elif iC < iA % iB :
        return False
    elif iB <= ig + iC :
        return True
    else:
        return False

for eR in aR:
    if fFunc(*eR) :
        print("Yes")
    else:
        print("No")

トリオ　黒棒（黒砂糖焼き菓子）50本入 [その他]