/ 最近 .rdf 追記 編集 設定 本棚

脳log[20211023] AtCoder Beginner Contest 224/D,E



2021年10月23日 (土)

最終更新: 2021-10-26T00:58+0900

[AtCoder] AtCoder Beginner Contest 224/D,E

D 問題で TLE に苦しんだ。E 問題も TLE に苦しんだ。そのまま E 問題が解けなかったので F 問題は読めなかった。

 D 問題 8 Puzzle on Graph

全探索が許されそうな制約。重複チェックのためのハッシュ表のキーを文字列にするか配列にするかで悩んだ。結果的に文字列ベースの探索で AC になった。

 提出 #26768646 (TLE×1 / over 4 秒)
 提出 #26770107 (AC / 2275 ms)

欠けてる数字を9番目の要素にするのがちょっとした Tips. TLE 解消の決め手にはならなかったんだけど。

現在の状態からありうる次の状態(のうち初出のもの)をすべて候補にするという意味で感覚的に全探索と書いたけど、そういうのは幅優先探索と呼ぶらしかった。

 E 問題 Integers on Grid

時間は1時間ほど残っていたのに、結果的に1時間と 10 分が AC までに必要だった。

 提出 #26776942 (TLE×18)

D 問題の TLE×1 と違って全然惜しくない。どこの処理量が膨れ上がるかとソースを眺めてみると、遷移のための辺を逐一処理しているところがダメ。

遷移の方向は A の小さい方から大きい方に決まっているので、A の降順に遷移可能回数を数え、行と列にその回数をメモしておけばいい。今後この行(この列)から遷移先を探すものがあるならメモした回数だけ遷移できますよ、というメモ。A の降順に処理しているから参照したメモはいつでも有効。

ああいや、A の値が等しい別の点が書き込んだメモを参照しないようにだけ注意が必要。この辺の呼吸は珍しくないので心得たものである。

 提出 #26781610 (AC / 1230 ms)

あと 10 分あればなあ。

 提出 #26786787 (AC / 708 ms)

不要になった処理を消し忘れてた。

レートはちょっとだけ上がってる。しかしもっと上がりたかった。