コンテストページ
Dwango Programming Contest V - AtCoder
解法
✔A - Thumbnail（200 点）
合計との偏差の n 倍を前計算します。豆知識なのですが、C++ の std::min_element は最小の要素のうち初めのものを指してくれます。嬉しいですね。
✔B - Sum AND Subarrays（400 点）
bit を上から見ていきましょう。最上位 bit に関して言えば、答えでその bit が立っている条件は、数列の方で K 個立っていることです。
無事立てられたとしましょう。すると、この bit の立っていない方は、残念ですが、お帰りいただきましょう。0 を代入です。いずれにしても上の方の bit は降りていると嬉しいので、操作が終わった後でこの位置の bit はすべておろしておきましょう。果たして 5 ペナを頂くような問題でしょうか。（あの！？）
✔C - k-DMC（600 点）
これ好きです。真ん中を全探索という見た目をしていますが、右端を全探索です。 文字だと間違えますから、'D', 'M', 'C' をそれぞれ 0, 1, 2 と置きましょう。これ以外は -1 と書いておきましょうか
右端を決めます。右端が 2 であれば、そのとき中にある 0 と 1 のペアリングの個数分だけスコアを加算です。 スコアを管理ましょう。区間を伸び縮させるとして、左から 0 が pop されたら中身の 1 の個数だけペアリングが減少します。また右に 1 を push すると中身の 0 の個数だけペアリングが増加します。
というわけで、ペアリングの個数、0 の個数、1 の個数をすべて管理しながらスライディングしていきましょう。
✖D - Square Rotation（800 点）
自信はあったのですが、通せませんでした。
どのように解いたか
まず、D = 1 のときには数さえ合えば小さい正方形に入れることができます。 さらに一般に、座標を D で割った余りで独立なゲームです。 そこで、まずは D で割ったあまりごとに分類して重複度をカウントしましょう。
すべての要素が q * q 以下であるような最小の q を取ります。すると q 周すれば入り切ることがわかります。しかし q 周目は途中までで良い可能性がありますから、q 周しなくてもよい正方形がどこなのかを考えましょう。 まず、その行、その列は、そのどの要素も q * (q - 1) 以下である必要があります。また、正方形の中身は (q - 1) * (q - 1) 以下である必要があります。
上述の正方形のうち最大のものを求めます。そのために、まずは行と列の条件だけを考えて、大丈夫な行と列の連結成分を列挙し、その組み合わせを全探索です。そしてその中で (q - 1) * (q - 1) 以下であるマスを塗っておき、最大長方形のアルゴリズムをします。
すると、答えは q * D - r - 1 です。（この -1 は、マス目と座標平面の差に由るものです。）
お気持ち
悲しいですね。
結果
惨敗です。ペナルティの数ならば圧勝なのですが……（はい！？）
本番ならば 237 位 1921 青パフォです。 D も悔しいですが、せめて前 3 問で嵌らなければ耐えていたかもしれません。やはり悔しいですね。
振り返り
ひどかったのは B で、原因は bit を上から見ていくタイプの問題の実装を決めきれていなかったことかもしれません。配列をコピーしたりしなかったり、bit をおろしたり変えなかったりと、迷走しています。昨日の ABC か Div. 2 かでも似たような問題が出ました。経験を積みながら、型化していきたいところです。
