AtCoder Beginner Contest 125

初心者用ということでとりあえず参加

A,B,D問題はAC(Accepted：正解)。CはTLE(Time Limit Exceeded：プログラムが規定時間内に回答できなかった)。

高速化の方法思いつかなかったのでACできず。
解説見たときは「こんなの思い浮かばねーよ！」と思ったけど、答えは出せてる場合、解説のポイント

「正数 $A_{i}$ を書き換える」行為は「整数 $A_{i}$ を消す操作」と等価
gcdには「どこから計算しても結果は変わらない性質」があります

がわかっているわけだからここから計算途中のものを流用していくという考えが出てくるのは自然なんだよなあ。勿体ないことした。

操作で何ができるかというと符号-を任意の場所に移動することができる、と考えればあとは楽ちん。負の数が偶数なら全部正、奇数なら1つだけ負。

解説読んで、C問題を安定してとくには動的計画法触っといた方がいいんだろうなーと思った。

AtCoder Grand Contest 033

ABCでつまづいてる初心者が出ても無駄な涙が流れるだけじゃない？と思ったけどまあいいや目標1問、ワンチャン2問くらいの気持ちで。

AはAC。BはWA(Wrong Answer：不正解)。C以降はBにかかりっきりで問題すら見てねえ…。

(幅優先探索だ…!)と考えればそれで。迷路の探索問題見たことあればｶｶｯと思いつくんじゃないかな。

先手後手の最適な行動の結果は何よ、と考えると
先手：最短手でマス目外
後手：最後までマス目内
先手の最適な行動を考えるのはいかにもめんどくさい。後手は1つしかない上明確なので楽。となるとマス目内に残る条件を逆算してく方法を思いつくのは難しくなかったはず。

前から考えてて結局時間切れでしたが…。

まずは緑色目指してｶﾞﾝﾊﾞﾛｰ!ｵｰ!