競プロ参戦記 #23 「チップストーリー」 / DDCC 2019 予選
金曜祝日開催の AtCoder！ 参加できなかったので練習記です。
今回は公式の解説PDFがとても詳しく、発展的な解法についても載っていて面白いので、解けた人も読みましょう。
概要
未来のプログラマーを発掘！
ディスカバリーチャンネルは本コンテストを通じて、
若く優秀なソフトエンジニアを発掘・支援し、
未来を創造するソフトエンジニアの育成に貢献します。
4回目を迎える今年は、「装置実装部門※」が登場。書いたコードを装置に実装して、より速く正確に動作するかを競う。
※「装置実装部門」選出条件あり
200人も本戦に行けるらしく、結果的にはC問題まで30分弱で解けばいいのでワンチャンある。
とはいえ練習時の成績では500位ぐらいなのでダメでした。
DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選
問題一覧：
A - チップ・ストーリー ～無色編～
問題概要：はじめ、1枚のチップを持っている。「いま持っているチップをすべて4つ分割する」操作を N 回行ったとき、最終的に持っているチップは何枚か。
考察：1回の操作でチップの総数が4倍になる、というのがポイント。いま持っているチップの枚数、というのを変数として保持し、ループを回せば解けます。
B - チップ・ストーリー ～漆黒編～
問題概要：白い正方形に黒い正方形が内接している。黒い正方形の頂点は、白い正方形の各辺の中点に位置している。白い正方形を N×N 等分に分割したとき、完全に黒い正方形で覆われている領域は何個か。(※図を見ましょう)
考察：数学的にがんばって考察すれば、１本の数式で計算できそうな感じがします。しかしこれは N の偶奇によって場合分けが生じてめんどくさいし、バグりそうなのでやめました。N が小さい (≤100) のでループを回したほうが楽そうな問題。
領域が完全に黒で覆われているための条件は、四隅が黒いことです。これは図をみると明らかですが、公式の解説には丁寧に「正方形が凸な図形だから」という理由付けも書いてありました。
ここまでで各領域につきループを回し、その四隅についてループを回すことまで考えました。この点は黒いでしょうか。
黒い正方形の対角線の交点を原点 (0, 0) とします。(つまり正方形を平面の真ん中に置く。) 点が黒い正方形の上にあるための必要十分条件は以下です：
|x| + |y| ≤ N/2
これは黒い正方形の右上の辺が直線 x + y = N/2 をなぞることから分かります。
実際には正方形が平面の中心にあると N の偶奇によって状況が変わって面倒なので、 N/2 ずつずらして、ついでに整数の計算で完結させるために全体を2倍して、
|2x - N| + |2y - N| ≤ N
を計算します。
余談ですが、このような「すべての x について P(x) が true」系の判定を書くときに if-break を書かないのが最近のマイブームです。やや短め。
let mut ok = true;
for &(x, y) in /* 略 */ {
ok = ok && (2 * x - N).abs() + (2 * y - N).abs() <= N;
}C - チップ・ストーリー ～白銀編～
問題概要：正の整数からなる長さ10の数列 P, Q を考える。積 P_i・Q_j はすべて N 以下であるという。このような (P, Q) の数を求めよ。
考察：いくつかのケースを試したところ、数列 P を微妙に変えても、それと組み合わせることができる数列 Q の種類がだいたい同じであることに気づきました。
これををヒントにして、条件を少し変形します。次の3つは同値です。
1. すべての i, j について P_i・Q_j ≤ N
2. max (P_i・Q_j) ≤ N
3. (max P_i)・(max Q_j) ≤ N
ここで max P_i の値を全探索します。つまり、変数 p を 1 から N まで動かして、 max P_i = p であるような数列 P を選ぶ場合の数の総和を求める、ということです。
最大値が p 「以下」であるような数列 P の総数は簡単で、 p^10 です。各要素ごとに 1〜p の p 通りのどれを選んでもよいからです。
最大値が「ちょうど」 p であるような数列 P の総数は、最大値が p 以下であるものから、最大値が p 未満の数列の個数を引きます。つまり p^10 - (p-1)^10 です。
ここで、数列 Q のうち最大値 q が p・q ≤ N を満たすものを数えます。つまり q ≤ floor(N/p) 。これは最大値が q 以下である数列の総数であり、上述の通り q^10 です。
結局、 Σ (p^10 - (p-1)^10) * q^10 (1≤p≤N, q = floor(N/p) が答え。
おわりに
D問題は解けず、 解説を読んでACしました が説明できることは特にないので略。