メモ@inudaisho

君見ずや出版 / 興味次第の調べ物置き場

AtCoder AGC028 0完 なぜかつらくない

 ついにやりました0完。A は完全に解法わかったとはいうもの、実装が雑だったせいで1waを出し二回ほど出しなおしたものの、失敗。これはドツボにハマるパターンだと思ったのでそこでやめてBに移り、そこで思いついた解法がそこそこいけそうだったので固執してしまい最後まで入力例2入力例3すらきれいに解けず。ううーん。ということでドツボを避けてドツボにハマりこの通りレーティングまで下げてしまった。

f:id:inudaisho:20181014062347j:plain

A

 Aについて。雑というのはこんな感じ。先頭の文字と、そこから最大公約数で割った商おきの文字が衝突するのでそこが揃っているとOKだろうということで、こんな感じに実装したものの、このループ部分の出来がわるかった模様。まぁ見通し悪い実装はどっかおかしいことが多いもので、これもその例にもれず。

def fgcd(a,b):
    if b :
        return fgcd(b,a%b)
    else:
        return a

if sS[0] != sT[0]:
    print("-1")
    exit()
elif fgcd(iN,iM) == 1:
    print(iN*iM)
    exit()
else:
#iLX = iN * iM // fgcd(iN,iM)  の倍数
    iD = fgcd(iN,iM)
    i = 1
    while True:
        if iN -1  <  i * iM //iD   or iM -1  <  i*iN//iD :
            break
        if sS[i*iN//iD ] != sT[i*iM//iD  ] :
            print("-1")
            exit()
        i += 1
    print(iN*iM//iD)

 Python みたいな便利言語にはそういうときにつかえる便利処理があってそれは大いに活用するべきだった。何のために Python で参加してるのか。たとえばリストから一定の間隔で要素を抜くには [開始:終わり:間隔]という記法があってそれを書くだけで今回の処理は終わっていた。こんな感じ。

iD = fgcd(iN,iM)

if sS[0::iN//iD] == sT[0::iM//iD]:
    print(iN*iM//iD)
else:
    print("-1")

 今からおもうと、iN//iDみたいに書いたのを何度もそのままつっこんでいるあたり、余裕がなかった証拠なので、手詰まりになったときに一息置いて変数の整理からやっていった方がよかったのだろう。

 どんくさいために一問落としたのだが、当然手が遅いのも間が抜けているのも実力のうちなので、今回0完なのも実力が反映してるんだな。精進精進( 精進とか言ってる年じゃないかもしれんが死ぬまで精進)

B

 さてBだが、解法の方をみると確率で解くことになっている。自分が思いついたやりかたで結局できなかった事を書いとく。読み物だ。

  • ブロックをひとつづつとりのぞくとき「連結」したブロックの合計の重さがコストとしてかかる。全組み合わせの全コストを計算せよ

f:id:inudaisho:20181014065657p:plain

 入力例2の組み合わせだが、図示するとこんな感じになる。問題でいうところの連結したブロックというのが最初は全部になるなら当然1試行目の重さは全重量* 4! (全組み合わせ)だろう。ということは2試行目は結局このブロック全部どれかさわるのだから4パターンに対しブロック3本分で計算できるのではないか?3段目は6パターンに対し3本分で計算できるのでは? というふうにかなり安直に考えた。

 今こうして書いてるとこの方向であっても、連結した部分を選ぶ試行の頻度が高くなるのでその分の重みが出てくるのだが、雑に式変形したのがなまじ近い計算結果を出したのでそこに固執してしまって堂々巡りに陥り、finishを迎えてしまった。図の2で考えると 1 段目は 24/4 の 6 通り来るのだが、ここではどれをえらんでもコスト 3 かかるので 3 x 6 、その下の2段目は 1 と 2 だが 1 x 2 + 2 x 4 というふうにやっていくととりあえず入力例2の正解が出る。完全に間違えた解に固執していたことになる。

 ここまでわかってようやくこのあたりの親切な解説がわかるというわけだ。今回はなぜかBについてたくさんの人が親切な解説を書いてくれている。ありがたやありがたや。

emtubasa.hateblo.jp

banboooo.hatenablog.com

 となると解法にある確率もいきなり見るとこれは?? この数字は何を割るんだ?となるが、これらの解説にあるようにAiは何回出てくるんだろうということと同じことを言ってるわけで、どうもこのあたりの勘所(問題意識)がなかなかつかめなかった。その確率がいわゆる期待値ということで、うーむ。確率のことを全然わかっていないことがわかる。

beta.atcoder.jp

 つーことで答え合わせのために投げてACしておいた。中に解説めいたこと書いたけどn-iをn-1にしてしまった

結語

 0完とはいえ、何が自分の課題か見えてきたのでよかったような気がする。こりずに次もがんばるぞ。(今回はなぜかつらくない)

今回の教訓

  • 手詰まりのときは変数整理でもやって一回キレイにするといいことがあるかも。ラッキーアイテムはリストのステップ。

  • 雑式変形よくない