AtCoder ABC 130 参戦記

AtCoder の ABC 130 に参戦しました。

結果は 26 分で ABCD 4 完 (ただし 3WA : しかもつまらないミス) で E 問題が解けず...パフォーマンスも 1371 で伸びずレートも下がってしまいました。
次のコンテストで青色挑戦は少し厳しそうです。ただ、よく考えると数回前のレートは水色ぎりぎりだったので、パフォーマンス 1371 でがっかりするのは自分の中で要求水準が上がっただけのような...

感想

A 問題、B 問題

瞬殺

C 問題

一瞬ウッとなったがよく考えると長方形は確実に 2 分できる。さらに複数の分割法があるのは長方形の中心を選んだときのみ。
...なのだが

• 長方形の面積の半分の計算を (int * int) / 2 でやって 1 WA
• (x, y) が (w, h) の半分かを計算するときに (int / 2) でやって 1 WA

の 2 WA をくらう。

D 問題

• を先頭にしたときに まで来たときに 以上になるなら が先頭になる組み合わせは 個
• 先頭の時はあきらかにすでに足した値をもう一度足すのは無駄なのでしゃくとり法で処理

あとはこれを実装するのみ

E 問題

適当な DP をやってしまい手元で WA にしかならずにギブアップ。
コンテスト後 1 週間かけて考えたあげく、以下のようにすればよいことに気が付く。

求める値を とすると、この値は以下の和。

• 
  • までの値をそのまま転写。 は取らない。
• の場合 そうでない場合
  • を取る場合の数
• 
  • を取らない場合の残りの値を足す。上記の値は 列の計算中 で追加された値になるので、この値を足すべきであり、また足しても 2 重カウントされない