AtCoder Regular Contest 002
- 1. AtCoder Regular Contest 002 解説 AtCoder株式会社 代表取締役 高橋 直大
- 2. A問題 問題概要 ? 西暦の年数が与えられる ? その年がうるう年かどうかを判定しなさ い。
- 3. A問題 解説 ? 規則3,2,1,4の順で実装を行う。 ? 滨蹿文を并べればＯＫ！
- 4. B問題 問題概要 ? Y/M/Dの形式で日付が与えられる。 ? y/m/dが整数となるような次の日付を出力 せよ。
- 5. B問題 解説 ? １日ずつ進めていく！ – 日付ライブラリとかある言語を使おう！ – 存在しない場合は、A問題のうるう年判定を 合わせて、１２月までの日数を予め配列に入 れておくなどして対応しよう！
- 6. C問題 問題概要 ? ABXYの4種類で書かれた文字列が存在する。 ? L,Rの2文字に、2文字分の意味を持たせる ことで、この文字列を圧縮したい ? 圧縮後の最小文字数を答えなさい
- 7. C問題 間違った解き方 ? 全通り置換するだけ ? 例えば、ABABBABAのようなケースがダメ になってしまう。 – L = AB、R= BAでLLRRが正解 – Lを出来るだけ置換すると、LLBLAになってし まい、Rに置換することが出来ない。 ? テストが弱い影響で、これで通っちゃう場合が あるみたいです。申し訳ありません。
- 8. C問題 解説 ? L,Rを全通り試す。 ? それぞれに対し、何文字目までいくつの 文字で表せたかをDPで計算する。 – ただの置換ではだめ！
- 9. C問題 解説 ? S = ABABBABA, X = AB, Y = BAのとき – まずは普通にABで表した時の数字を入れる A 0 B A B B A B A 1 2 3 4 5 6 7 8
- 10. C問題 解説 ? S = ABABBABA, X = AB, Y = BAのとき – Xを適用。ABに対して+1の更新を行う。 A B A B B A B A 0 1 2 3 4 5 6 7 8 0 1 1 2 2 3 4 4 5
- 11. C問題 解説 ? S = ABABBABA, X = AB, Y = BAのとき – Yを適用。XYに対して+1の更新を行う。 A B A B B A B A 0 1 2 3 4 5 6 7 8 0 1 1 2 2 3 3 4 4 ? こうしたDPを全通り行う
- 12. D問題 問題概要 ? 以下のように、将棋の歩の動きをする駒 が大量にあるボードゲームがある – 持ち駒は存在しない。初期配置で取れる駒は 存在しない。どちらが勝つかを求める – 相手の陣地（端）に到達したら勝ち
- 13. D問題 解説 ? 問題サイズは、2000*2000 – 探索等の処理は無理 ? 何か規則性を見つけよう！
- 14. D問題 解説 ? 基本的な処理 – 自分の目の前に敵がいないような駒が存在す る場合 ? 片方にいる場合は、そちらの勝ち ? 両方にいる場合は、先に辿り着ける方が勝ち – そうでない場合 ? 自分から取られに行くような操作は不利 – 取られた瞬間取り返す、みたいなのは別だが、考える必 要はない。理由は後述。 ? 取られないような操作だけを考えれば良い
- 15. D問題 問題解説 ? 先手が動かした後、後手はどの駒を動か しても取られる状態になってしまう。 ? このような状態の時、取られた直後にま た同じ状態になる。つまり負けが確定し てしまう。
- 16. D問題 問題解説 ? つまり、先に取られる様な動きをしてし まった方が負け – 相手に取られない動きを何手打てるかが重要 ? この手数だけに注目し、相手との手数の 差を最大化するような手だけを打てば良 い。 – これは、向かい合っている駒の数だけで判定 が可能なので、ソートして貪欲。