一問一答十四週目 - 競プロ引退しました。

AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。

　時間外AC。丁寧に丁寧に場合分けするだけ。レート3200以上の人は灰～赤以外の色も使えるという条件を認識していなくてかなり悩んだ。。

　時間外AC。丁寧に場合分けを考えればよい。階乗した値など、大きな数の余剰を取る場合、計算の毎に余剰を取ると計算量を減らすことができる。

　地力AC。各要素の番目に応じて、右から追加するか、左から追加するか場合分けすればよい。O(n) で解ける。

　解説AC。for 文の中で迂闊にリスト操作すると、二重ループになりかねないので注意。 $x_i = x_{i-1} + ai$ かつ $y_i = X - x_i$ であることを利用して、一回のループで計算可能。

　解説AC。①1~i への経路が存在しているか調べる。②i~Nへの経路が存在しているか調べる。③両方存在していれば移動可能。

　①、②用に bool 配列を2つ用意して、配列の番目を上記 i として記録する方法がとても勉強になった。

　解説AC。丁寧に場合分けする問題。「4の倍数」「4の倍数以外の偶数」「奇数」の並べ方の最適化を考えればよい。「4の倍数以外の偶数」は、一括りにすると奇数一個と等価とみなせるのがポイント。

　解説AC。lcm を求めるだけとは気づいたものの、なぜか解けなかった…実装力？

　gcd や lcm は累積的に求めることができる、というのはポイント。reduce 関数使わなくても、複数の数に対して計算可能。

　解説AC。大きい順に棒を並べて、同じ長さが二本ずつ存在するか調べていき、二つのペアが作れた時点で最大面積が求められる。

　もともとやろうとしていた方法で RE が出たのはなぜなのだろうか…

　C問題に対する抵抗感はだいぶなくなってきたと思う。