ARC 097
ボケ防止にまったり勢でプロコン復帰します。
C
sの異なる連続する部分文字列のうち辞書順でK番目に小さいものを出力せよ。
- 最初から結構難しそう。制約がないと結構面倒な問題じゃなかったっけか。
- substringを全部列挙してsetに入れる → O(N^3logN)とかになり間に合わない。
- Kが小さいらしい。長さ1〜Kの文字列は全部異なるから、各iについてs[i..i+K]まで列挙すれば十分
- AC. 最初の問題に7分以上かかる。相当考察力が落ちている。
D
順列pとn個のタプル(xi, yi)が与えられる。順列に大してxi番目とyi番目を入れ替える操作が何度でもできるとき、pi = iとなるiの個数を最大化せよ。
- (1, 3), (3, 4)が与えられていたら1, 3, 4番目は自由に入れ替えられる
- 各連結成分ごとに要素をまとめて、成分内でマッチングすればよさそう
- 二つの単調増加列のマッチングだから尺取りで書けばいい
- AC.
E
1〜Nまでの数字が書かれた白いボールと黒いボール合わせて2N個が一列に並んでいる。
隣り合うボールを入れ替えて、白いボールだけを見たときにソートされていて、かつ、黒いボールだけを見たときにソートされている状態にしたい。必要な操作の回数の最小値を求めよ。
- バブルソートの交換回数の拡張みたいな奴。バブルソートのときってどうするんだっけ。
- Binary Indexed Treeで転置のペアの個数を数えるだっけ → 今回は転置を数えても最終状態が一意に定まらないし上手くいかなそう
- バブルソートの交換回数って分割統治みたいなアルゴリズムもあったような。忘れた。
- 普通のバブルソートの交換回数は、愚直に求めるには当然O(N^2)でバブルソートを実際にシミュレーションすればいい。
- 今回、最終状態が一通りじゃないからシミュレーションすら無理だ。
- 白いボールの位置を決めたらコストは求まりそう → DPなんかなこれ。
- dp[白いボールを使った個数][黒いボールを使った個数] := その時点の操作の回数 とすると？
- いけそう、書いてみる。
- 遷移が上手く書けない。bitか何かでコストを高速に求めないといけない。
- 思考がごちゃごちゃする。遷移を整理してみる。
- 白をi個、黒をj個使った状態で白のi+1を使うとき
- 列の白i+1の前にあるボールのうち、白の番号がiより大、黒の番号がjより大のものの個数が高速に求まればいい。
- 最初に前計算すればいいか。
- 送信。RE. 配列を2NじゃなくてNで取ってた。
- 再送信してAC.
- 手間取りすぎー。順位表見ると、この時点で48位。どの程度なのか全然わからない。
- 昔のTopCoderだったら微妙。ARCはそれより参加人数少なそうだし（要出典）アレかも。
F
木が与えられる。頂点は白または黒。好きな頂点から出発して、今いる頂点の色を反転させる、または隣接する頂点に移動して、移動先の色を反転させる、の二つの操作を好きなだけ行える。全部の頂点の色を黒にするのにかかる操作の回数の最小値は？終了時にはどこにいてもいい。
