天下一プログラマーコンテスト2019に参加しました。
「天下一プログラマーコンテスト」は、KLab株式会社が開催するAtCoder Regular Contest / AtCoder Beginner Contest相当のプログラミングコンテストです。
競プロ参戦記
この連載記事では、着手した問題の考察を自分なりに書いていきます。
Tenka1 Programmer Contest 2019
- 問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/tenka1-2019/tasks
C - Stones
問題概要: 黒または白の石が N 個、一直線上に並んでいる。いくつかの石を黒または白に塗り替えて、「黒白」の並びがないようにするとき、最小で何個の石を塗り替える必要があるか求めよ。
考察:
最終的に「黒白」の並びがないということは、石は「白白..黒黒..」という並びになります。
⚪⚪⚪⚫⚫⚫
白と黒の境界 が左から k 番目だとします。この状態にする最適な操作は明らかで、境界 k の左を白に、右を黒に塗ることです。そのため、境界 k の左側にある黒の個数と、右側にある白の個数の和が、このケースでの解となります。
境界 k の値を全通り試して最小値を求めればOK。これは単純にやると O(N^2) 時間ですが、累積和または状態遷移によって O(N) で解けます。
解法 1. 累積和
(この問題しか解けなかったので詳細に書きます。)
累積和 は数列 A から部分和の列 W を作る操作です。
W[i] = A[0] + A[1] + .. + A[i - 1]
例えば A = [3, 1, 4, 1, 5] なら:
A: 3, 1, 4, 1, 5
W: 0, 3, 3+1, 3+1+4, 3+1+4+1, 3+1+4+1+5
これのいいところは数列 A のある区間における総和が簡単に求まることです。
W[l] = A[0] + .. + A[l - 1]
W[r] = A[0] + .. + A[l - 1] + A[l] + .. + A[r - 1]
W[r] - W[l] = A[l] + .. + A[r - 1]
さて、いまの問題では A[i] = (i 番目の石が白なら 1, 黒なら 0) とおくとうまくいきます。この累積和 W は、白石の個数を数えることに使えます。
S[i] = A[0] + .. + A[i - 1]
= (左から i 個の石のうち白の個数)
S[r] - S[l] = (l から r までの白の個数)
こういう「もし〜なら 1、そうでなければ 0」という変数の和を計算することで「条件を満たすものの個数を数える」のはしばしば見る手です。
同様に黒石の個数も数えると、k が境界のときの解が O(1) 時間で計算できるようになります。
B[k] + (W[N] - W[k])
筆者の回答 (Rust, AC): https://atcoder.jp/contests/tenka1-2019/submissions/5038567
解法 2. 状態遷移
累積和を使うよりシンプルな方法もあります。
いま境界 k に対して知りたいのは「境界より左側にある黒の個数」と「境界より右側にある白の個数」です。それらの値を変数として持っておくことにします。
初期値は簡単に計算できます。
- 「境界より左側にある黒の個数」は 0 (境界より左に石がないため)
- 「境界より右側にある白の個数」は全体の白石の個数 (すべての石が境界の右側のため)
変数 k の値が変化する (1 増える) たびに、それらの変数も適切に変更します。境界 k → k + 1 と変化したとき、以下のような変化が起こります:
- k 番目の石が黒なら「境界より左側にある黒の個数」が 1 増える
- k 番目の石が白なら「境界より右側にある白の個数」が 1 減る
筆者の回答 (Rust, AC): https://atcoder.jp/contests/tenka1-2019/submissions/5091528
これは「各 k ごとに何かを計算する」のではなく「変数 k の差分に対して、k に依存する変数の差分を計算する」という手法です。累積と差分で対比したら格好いいかなと思いました。
D - Three Colors
問題概要: 長さ N の整数列 A が与えられる。各要素を赤・緑・青のいずれかに塗るとき、各色の総和を辺の長さとする三角形が存在するような塗りかたの個数を数えよ。
考察:
解けませんでしたが、解説放送を聞いたらおおよそ分かりました。
辺の長さが x, y, z (x ≤ y ≤ z) であるような (正の面積を持つ) 三角形が存在するための条件は 三角不等式 (の等号を除いたもの) として知られています:
x + y > z
私はこれをこねくり回してどうにかしようと思ったんですがダメでした。
3辺の長さの総和 S (= x + y + z) は簡単に計算できるので、この条件は次のように変形できます:
x + y > z
⇔ S - z > z
⇔ S/2 > z
つまり x, y, z のどれかが S/2 未満になる塗りかたを数えればよさそうです。しかし x, y, z のうち2つ以上が S/2 未満になるケースが存在するところがやっかいです。(たぶん)
《逆から考える》と「三角不等式が成り立たないような塗りかたを数えて、すべての塗りかたから引く」ということも可能です。つまり、
z ≥ S/2
になるような塗りかたを数えるのはどうでしょうか。包除原理により、
全体の塗りかた
- (x ≥ S/2 になる塗りかた)
- (y ≥ S/2 になる塗りかた)
- (z ≥ S/2 になる塗りかた)
+ (x, y ≥ S/2 になる塗りかた)
+ (y, z ≥ S/2 になる塗りかた)
+ (z, x ≥ S/2 になる塗りかた)
- (x, y, z ≥ S/2 になる塗りかた)
となりますが、ここで x ≥ S/2 なら x ≥ y, z が成り立ち、他の2つも同様なので以下の3つは等しいことが分かります:
- (x ≥ S/2 になる塗りかた)
- (y ≥ S/2 になる塗りかた)
- (z ≥ S/2 になる塗りかた)
同様に以下の3つも等しいです:
- (x, y ≥ S/2 になる塗りかた)
- (y, z ≥ S/2 になる塗りかた)
- (z, x ≥ S/2 になる塗りかた)
最後は 0 です:
- (x, y, z ≥ S/2 になる塗りかた)
結局、求めるべきものは以下の2つだけになりました:
- (x ≥ S/2 になる塗りかた)
- (x = y = S/2, z = 0 になる塗りかた)
これはそれぞれ次のような DP で解けます:
-
dp1[t][x]: 特定の色の総和が x になる場合の数 -
dp2[t][x]: 2色しか塗らないとき、特定の色の総和が x になる場合の数
筆者の回答 (Rust, AC): https://atcoder.jp/contests/tenka1-2019/submissions/5066118
E - Polynomial Divisors
問題概要: N 次の整数係数多項式 f(x) = Σa_k・x^k が与えられる。「すべての整数 a について p | f(a)」が成り立つような素数 p をすべて求めよ。
考察:
練習のため解説 AC しました。厳密な話はできないのでおおまかに書きます。
まず f(x) = 6x のように f(x) = n・g(x) の形になっているときは明らかに n の素因数がすべて条件を満たします。n は係数の最大公約数 (GCD) をとることで求まります。
入力例 1 をみると f(x) = 7(x(x - 1) + 2) において p = 2 が条件を満たしますが、これは x(x - 1) が常に偶数だからです。一般に x(x - 1)..(x - (p - 1)) は p の倍数です。
- f(x) を因数分解してこの形になるか判定する……？
- 逆に p が条件を満たすなら必ずこの形の式 ((x - r_i) の積で r_i を p で割った余りとして 0, 1, .., p-1 がすべて出現する) が現れる……？
というあたりで詰まって解説 PDF を読みました。ポイントは mod p で考えることのようです。以下が同値になる ([n] は整数を mod p で考えていることを表す)。
- p が条件を満たす
- f(x) = [0]
- x = [0], [1], .., [p - 1] はすべて f の根
- f(x) = x(x - [1])..(x - [p - 1])・g(x)
- f(x) = (x^p - x)・g(x)
- (x^p - x) | f(x)
また、f は N 次なので p > N なら明らかにNG。
結局 p ≤ N について f(x) を x^p - x で試し割りすればいいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/tenka1-2019/submissions/5077094
今回の教訓
- C: 最適な操作をした後の状態を考えるといいかも
- D: 条件の逆を考えるといいかも
- E: 練習あるのみ