せっかくの連休なので Codeforces に参加しました。
競プロ参戦記
この連載記事では、着手した問題の考察を自分なりに書いていきます。
Codeforces Round #556 (Div. 2)
- 問題の詳細は問題一覧を参照してください。
- 問題一覧: https://codeforces.com/contest/1150
A - Stock Arbitraging
問題概要: いま r 個の bourles を持っている。午前は N 回取引を行う。i 回目の取引では share 1個あたり bourles s_i 個のレートで、好きな数の share を購入する。午後は M 回の取引を行う。j 回目の取引では share 1個あたり bourles b_j 個のレートで、好きな数の bourles を購入する。最終的に持っている bourles の個数を最大化せよ。
考察:
午前は share が最も安いときになるべく多く買って、午後は share が最も高いときにすべて売る、というのが最適です。ただし買値より売値が低い場合は何もしないのがベストとなります。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1150/submission/53510334
B - Tiling Challenge
問題概要: N×N の盤面がある。盤面にはあらかじめいくつかのタイルが張られている。5枚のタイルが十字型につながったものを好きなだけ盤面に張る。タイルが重なることなく盤面を覆えるか判定せよ。
考察:
左上から右下に向かって貪欲にタイルを置いていき、最終的に覆えたら OK、覆えなければ NG です。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1150/submission/53512823
C - Prefix Sum Primes
問題概要: 1 または 2 が書かれた N 個のカードが与えられる。カードを好きな順番に並び替えて数列を作った。その部分和の列に含まれる素数の個数を最大化せよ。
考察:
すべてのカードが 1、またはすべてのカードが 2 であるケースでは自明です。そうでなければ、2, 1; 2, 2, ..; 1, 1, .. と並べるのがベストです。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1150/submission/53514982
D - Three Religions
問題概要: 長さ N の小文字アルファベットからなる文字列 S と、Q 個の操作が与えられる。文字列 T(h) (1≤h≤3) を空文字列とする。各操作の後の状態で、条件 (☆) が満たされるかを判定せよ。
- 操作
+ h c: T[h] の末尾に文字 c を挿入する。 - 操作
- h: T[h] の末尾の文字を削除する。 条件 (☆) : 文字列 S のいくつかの文字に 1, 2, 3 のいずれかを割り当てて、「各 h (1≤h≤3) につき、h が割り当てられた文字からなる S の部分文字列が T[h] に一致する」ようにできる。
制約: 1≤N≤10^5, 1≤Q≤10^3, |T[h]|≤250
考察 1. DP
例えば S = abbaab, T[1] = a, T[2] = ab, T[3] = ab という状況では、以下のような割り当てが存在するため条件を満たします。最初の a に 1 を割り当てると失敗するので注意。
22 133
S = abbaab
割り当ては次のような DP によって 250^3 のオーダーで計算できます。
dp[x][y][z] = k : 文字列 S, T[1], T[2], T[3] のそれぞれ長さ k, x, y, z のプリフィックスについて条件(☆)が満たされる、という条件を満たす最小の k
例えば S = abdabc, T[1] = ad, T[2] = b を考えてみます。(x, y, z) = (1, 0, 0) では次のような割り当てで条件を満たすので k = 1 です。
dp[1][0][0] = 1 (a)
1
S = a
T[1] = a
(x, y, z) = (2, 0, 0) では d を割り当てる文字が S に含まれるまでプリフィックスを伸ばさないといけないので、k = 3 が最小です。
dp[2][0][0] = 3 (abd)
1 3
S = abd
T[1] = ad
T[2] のほうをみていくと、まず dp[0][1][0] = 2 です。
2
S = ab
T[2] = b
dp[1][1][0] は (1, 0, 0) と (0, 1, 0) からの遷移があります。つまり、先頭の a に 1 を割り当てた後に次の b に 2 を割り当てるのか、あるいは b に 2 を割り当てた後に次の a に 1 を割り当てるのか、です。前者の方が k が小さくなります。
(1, 0, 0) → (1, 1, 0)
12
S = ab
T[1] = a, T[2] = b
(0, 1, 0) → (1, 1, 0)
2 1
S = abda
T[1] = a, T[2] = b
T に1文字足したとき S がどのくらい伸びるかは、その足された文字が次に出現する位置から分かります。事前計算をすれば O(1) です。
ただしこの DP をクエリーごとに行うと TLE します。
考察 2. 遷移
T[1] の末尾に文字が追加されたり削除されたとしても、追加や削除の影響がないプリフィックスしか使ってない状態 (x < |T[1]|) からの遷移には影響しません。
そのため x = |T[1]| 付近の状態からの遷移をやりなおせばいいです。操作ごとにおおよそ 250^2 回の計算で済むので、ぎりぎり間に合います。
筆者の回答 (Rust, AC): https://codeforces.com/contest/1150/submission/53538910