AtCoder Beginner Contest 136

結果

順位   315th / 5109
パフォーマンス   1843
レーティング  1913 → 1906(-7)

A - Transfer

　一度間違えてサンプル3の入力を提出欄にコピペして出してしまったがCEになったのでペナルティは付かなかった。あぶねー。

　提出

B - Uneven Numbers

　整数を $N$ までループしてstd::stringに変換してサイズを偶奇判定。std::to_stringがどんな実装になっているかは知らないけどまぁ桁数くらいの計算量だろうしそれなら間に合うはずという判断。最大ケースもサンプルにあったし。

　提出

C - Build Stairs

　右から見ていって左の方が高ければ一つ削る。まだダメならNoだし良ければ次へとやっていく。無駄な分岐も作ってしまったしあまり綺麗なコードになってないな。

　提出

D - Gathering Children

　サンプルを手で考えているとR...RL...LとなっているRLの部分に最大1の差で集まるんだなということがわかるので、あとは偶奇を冷静に考えていると解けている。解説PDFのダブリングによる解法は典型っぽいので覚えておいた方が良さそうだなぁ。

　提出

E - Max GCD

　総和が不変ということにはすぐ目が向くが、その先の考察が進んでいかない。というのも $O(N \sqrt{N \max{A}})$ が間に合わないと勘違いしていて、しばらくして $N$ は小さいからこれでいけるということに気づいて約数列挙→最低操作回数計算という流れで解けた。 $O(N\log N \sqrt{N \max{A}})$ になるのでやや不安だったけどこれが余裕なんだな。

　途中でちらっと見たとき解いている人が少なかったので難しいのかと思ったけど解けてみたらあまりそうでもなく、ACした後に順位表みたら順位がひどかった。最初のはF問題の欄を見間違えていたのかな。

　提出

F - Enclosed Points

　残り30分くらいしかない状況で入ったのでやや諦めつつの考察だったけど、しばらくして「ある点が何回囲われるか」という視点で考えれば解けそうだと気づく。 $x,y$ の範囲が広いので座標圧縮して、 $x$ でソートしてセグメント木で $y$ の位置を取りつつ、重複して数えるのを除いて……というのを10分程度で実装できるわけもなく終了。