AtCoder ABC125 参戦記
AtCoder の ABC125
に参戦しました。
前回の ARC (形式のコンテスト) へぐって水色から落ちていたので水色に返り咲くのを目標にしました。
結果は C 問題に手こずった挙句 1TLE 出して 64 分かかり、601 位でした。
終了直後は C 問題に手こずって順位を落としたので若干気落ちしていましたが、パフォーマンスが意外に伸びた*1ために水色に返り咲くことができました。
感想
A 問題
速攻
B 問題
速攻
C 問題
一つの数字を抜かした GCM すればよいところまでは簡単に考察できたのに、ひとつずつ数字を除外して GCM する全探索を書いて TLE 。
考えてもわからなかったので D 問題を先にといた。
もどってきて複数数値の GCM は順番は関係ないことに気が付き、GCM(先頭からの GCM, 末尾からの GCM) の最大値が答えであることに気が付く。これを投げて終了。
1 TLE はもったいなかった...とりあえずだめっぽい解答をなげる癖をやめなければ。
D 問題
C 問題ができなかったので先に解いた。
一回ひっくり返すとマイナスが伝播することに気が付き、マイナスの数が偶数なら全部の数の abs の和、奇数ならそこから abs が一番小さい数を引けばよいことに気が付く。テストケースで 0 がある場合 (この場合は全部の数の abs の和が答え) のコーナーケースに気が付き、それに注意して実装、AC。
*1:1300 か下手したら 1200 程度でレート以上のパフォーマンスを取ってレートを落とすかもと予想