AtCoder Regular Contest #019 参加記録

最近、ちょくちょく AtCoder の Regular Contest に参加しています。

ここ数回は毎回参加できているのですが、一向に上達する気配が無い……というか、単に当日に漫然と参加している程度では上達するわけもないので、せめて最低限の記録と復習を残してみようと思います。

Summary

AtCoder Regular Contest #019 (公式解説)

問題A 問題B 問題C 問題D
コンテスト中の最終回答 AC
8:13(1回目)
AC
37:33(2回目)
- -
終了後じっくりと回答 - - TLE AC(30点)
解説を読んでから回答 - - AC (未挑戦)

総合: 200点 42:33 (1ペナルティx5分) 92位

問題A

文字列置換するだけ。速度を気にする必要も無いし、愚直にやればよい。

問題B

問題を理解して、場合分けして数えるだけ。
最初は細かく場合分けしてたのに、途中で小賢しくまとめようとして間違えた結果、1回目の提出で WA し、デバッグに時間がかかってしまった。

教訓: 半端に小賢しいことをしようとしない。

問題C

時間内に解き終わらず。
1時間以上かけて、TLE ながら、答えが出せる程度の答案はできた。

…と思っていたのだが、分岐点が丁度"E"マスだった場合の計算間違えてたことを、解説を見て思い知らされた。

大まかな方針は間違ってなくて、

  • 正解の経路は必ずT字型になる
  • Tの分岐点Xから、スタート、ゴール、祠の3点それぞれへのコスト(敵数と距離)を DP で求める。
    • その際は、Xをスタートにするのではなく、三点をスタートにした幅優先探索する
  • 「スタートからX」+「Xから祠」×2(往復分)+「Xからゴール」が最小になる X を求める。
  • 計算量は DP に O(3*RC*K) で、最小を求めるのに O(RC*K*K)

といったところは合っていた。

TLEなのは単純に Dynamic Programming が下手だったという落ちで、前述のとおり、忘れていた分岐点Xが "E" マスだった場合の対応も加えて書き直したら通った。

教訓: 迷路の探索ぐらいはサクっと書けるようになっておきたい。あと、多項式時間解法では、python で解く場合、定数を減らすような小細工も多少は入れないと時間が厳しいことがある。

問題D

部分点あり。ハンドメイドの答えでもOKなので、点数を少しでも稼ぎたいなら先に解くべき。

ランダムにマスを選択して置けるなら置く、の戦略でといたら30点だった。

満点回答は解説にあるとおり。N * sqrt(N) が最大だと気付ければ、sqrt(N) が整数になる時、つまり N が何かの二乗のときに特別な解法があると気付けるかもしれない。
N = a * a としたとき、縦横 a * a のブロックが a * a 個並んでいると考えると、1ブロックに a 個置けば良い、という流れだ。ただ、素数のほうが容易に解ける、というのは気付けそうにない。

教訓: 部分点がある問題は点を拾いに行くと順位は伸びるはず。数学知識があると良い問題は、少しずつ勉強するしか無いよね。