135. AtCoder参加記録（AtCoder Beginner Contest 268）

38回参加でレート 1377 です。

今回はパフォーマンス 1453 です。

ABCDを通して、EFGExは未解答です。Dで3ペナ。

各問題の思考過程など。

A

問題

1分13秒。

HashSet に全部突っ込んで要素数を出す。

ACコード

B

問題

1分13秒。

C# なら、T.StartsWith(S) で判定できる。

ACコード

C

問題

9分23秒。

C問題にしては急に難しいので、落ち着いて問題を読む。1回ずつテーブルを回してその時の「喜ぶ人数」を $O(1)$ で求めるような形にしたい。
「料理 $i$ と正しいインデックスの距離的なもの」は、ざっくり $d_i = p_i - i$ と計算できる（この式は負の方向を考えていない）。
この「距離的なもの」はテーブルを 1 回動かすごとに 1 ずつ増加する。
$d_i = j$ であるような $i$ の種類数を $c_j$ とすると、求める答えは $c_{N-1} + c_{0} + c_{1}$ と表現できる。
3. の考察から $c$ は 1 つずつ回転していくような動きをする。
以上より、初期状態での $c$ を求めた後、インデックス 0 とみなす点を全探索すればよい。

ACコード

D

問題

初回提出 24分45秒、2回目提出 2分59秒、3回目提出 3分4秒、4回目提出(AC) 16分46秒。

$X$ が $T$ のいずれかと一致しているかは HashSet を使えば $O(1)$ で求められる。
連結順は順列全探索で決定できる。 $N \le 8$ という制約なので、ここからも順列全探索が想定されていることが分かる。
連結順が求まれば、後はアンダーバーを追加して一致を見れば良いだけ？と考えたが、どこかにアンダーバーを2つ以上繋げないと $X$ を作れないテストケースは容易にできることに気付く。
ということは、アンダーバーの数についても、それぞれの位置について全探索する必要がありそう…。 $|X| \le 16$ という条件なので、計算量は問題ない。
まとめると、
1. $T$ を全て HashSet に突っ込む
2. $S$ の連結順を順列全探索する
3. 連結に用いるアンダーバーの数を $|X| \le 16$ という制約のもとDFS全探索する
4. $X$ が HashSet に含まれていなければそれを出力する
5. 最後まで探索して答えが見つからなければ -1 を出力する
実装が重すぎる…と思いつつ書き上げると、入力例 1 でいきなり RE する。 $N = 1$ のときのみ例外処理で判定する。
これで入力例は合ったので投げてみる → 5WA
問題文を読み直すと、 $|X| \ge 3$ という条件があった。は？と思いつつ、DFS全探索にこの条件を組み込む → 7WA（うちサンプルで1WA）
参照していた変数がおかしかったので直す。ついでに $N=1$ のときの $|X| \ge 3$ 条件が抜けていたので入れる → 3WA
流石にこれは何かバグらせているので、一旦落ち着いてじっくりデバッグする。怪しいのはDFS全探索の部分。見てみると、アンダーバーの数の全探索について、最初のアンダーバーの数だけ 1 or 2 でしか探索できていなかった（ダメすぎる）。
これを修正して無事AC。

ACコード

E

問題

解けず。

Cの類題。ただ、考え方のベースはCと同じで良さそうに思える。
正しいインデックスとの距離的なもの $c$ を考える。テーブルが1回動くと、だいたいインデックス $N / 2$ を境界に、それより前のものは不満度が 1 加算され、後のものは不満度が 1 減算される。
「不満度加算集合」「不満度減算集合」を管理しつつ、1 つずつ状況を変化させれば良さそう。1回の変化で、それぞれの集合から1つずつ要素が出入りするので、スコア計算もそれで差分を取ればよい。
入力例 3 が合わず撃沈…。実装ミスのようです。