AtCoder Beginner Contest 173の感想

100(1)-200-300-400-500(2)-600で3ペナ全完2100点、時間はペナルティ込みで98:33。

A

atcoder.jp
A問題を舐めていて、n%1000を出力してWA。サンプルの重要性を知る。
1000円ずつ払うと考えて、実際にループを使って1000円ずつ引いていった。こういう処理は割り算を使うと高速に行えるが考えることが多くなるので今回は引き算で書いた。払い切れたときにお釣りが1000円になったりして結構大変だった。 $O(N/1000)$

B

atcoder.jp
ACWATLEREの順で配列に保存しておくと最後の出力の時に少しだけ楽をできる。文字列がこの4種類と合致するかどうかを試していけばよい。実は1文字目が全て違うのでそこだけで判定してもいけるが、特に意味はない…。 $O(N)$

C

atcoder.jp
元のマス目に存在している黒いマスのうちどの $K$ 個を残すか、という考えだと少し複雑になる。
ここで制約を見るとマス目は最大でも $6\times 6$ の大きさにしかならないと書いてある。このことより、各行・列について塗る/塗らないを全探索して実際にマスを赤色に塗り、黒いマスがいくつ残るかを数えることが可能だとわかる。こういう全探索はbit全探索と呼ばれている。最近のC問題で普通に要求されてるけど、bit演算をすらすら書けるようになったら相当すごいと思う。
bit生成に $O(2^{H+W})$ 、実際に塗った後黒いマスを数えるのに $O(HW)$ 、最終的な計算量は $O(2^{H+W}HW)$ となる。制約の最大値 $H = 6, W = 6$ の場合でも $1.4\times 10^5$ 程度となり、十分間に合う。

D

atcoder.jp
実験してみると以下のことが見えた。
フレンドリーさが大きい順にソートしておき、大きい順に到着させる。この時、ある人 $i$ を到着させた時点で人 $i$ より前に到着していた人たちはフレンドリーさが人 $i$ 以上であるので、人 $i$ の右隣と左隣に別の人を到着させれば、人 $i$ のフレンドリーさ分の心地よさを獲得できる。
…つまり何が言いたいかと言うと、フレンドリーさが大きい人の隣にバンバン突っ込んでいけば人1人のフレンドリーさを2回心地よさとして獲得できるので、（おおざっぱに）降順で並べたときの前半の人達のフレンドリーさの2倍が答えとなる。(説明がむずかしい！！)　 $O(N\log N)$

E

atcoder.jp
見た目は簡単そうだが、考察をしっかりしないと実装で詰むタイプの問題。「余りを答えよ」に引っ張られて余り同士で大小比較したり、負の数やゼロの扱いをおざなりにしたりすると、すぐコーナーケースにはじかれてペナが出る。
負の数を2回かけると正の数になる、という性質を利用して、正の数のうちの一番大きい値と2番目に大きい値の積、負の数のうちの一番小さい値と2番目に小さい値の積、の2値を比較して、貪欲に大きい方を取っていけば基本的には正解となる。が、
・どう選んでもゼロを含んでしまう→答えはゼロ
・正の数が1つもない→Kが奇数の時答えは必ず負の数になる…ようにみえるが、ゼロが1つでもあれば答えをゼロにできる（もちろん負の数よりゼロのほうが大きい）
・正の数や負の数が奇数個あり、実装でバグらせる
等というようなコーナーケースがたくさん考えられる。実装に入る前に考察をしっかりまとめておくと、バグがあっても発見しやすいかも。 $O(N\log N)$

F

atcoder.jp
辺が1つもないときの答えは $O(N)$ で出せる。このグラフに辺を一本ずつ加えていくことを考える。 $u\lt v$ を満たす頂点 $u$ と $v$ を結ぶ辺を追加したとき、 $u$ 以下の $L$ と、 $v$ 以上の $R$ に対する関数 $f(L, R)$ の値が1ずつ減少する。辺により連結となる成分が1つ増えるからだ。これを満たす $(L, R)$ の組は、 $u\times (n-v+1)$ 組ある。これをすべての辺に対して計算して最初の答えから引き算していけば答えが求まる。これも、脳内でのイメージを文章化するのが難しいタイプ…。 $O(N)$