競プロ参戦記 #23 「チップストーリー」 / DDCC 2019 予選

金曜祝日開催の AtCoder! 参加できなかったので練習記です。

今回は公式の解説PDFがとても詳しく、発展的な解法についても載っていて面白いので、解けた人も読みましょう。


概要

未来のプログラマーを発掘!
ディスカバリーチャンネルは本コンテストを通じて、
若く優秀なソフトエンジニアを発掘・支援し、
未来を創造するソフトエンジニアの育成に貢献します。
4回目を迎える今年は、「装置実装部門※」が登場。書いたコードを装置に実装して、より速く正確に動作するかを競う。
※「装置実装部門」選出条件あり

200人も本戦に行けるらしく、結果的にはC問題まで30分弱で解けばいいのでワンチャンある。

とはいえ練習時の成績では500位ぐらいなのでダメでした。


DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選

問題一覧:


A - チップ・ストーリー ~無色編~

問題概要:はじめ、1枚のチップを持っている。「いま持っているチップをすべて4つ分割する」操作を N 回行ったとき、最終的に持っているチップは何枚か。


考察:1回の操作でチップの総数が4倍になる、というのがポイント。いま持っているチップの枚数、というのを変数として保持し、ループを回せば解けます。

筆者の回答 [AC]


B - チップ・ストーリー ~漆黒編~

問題概要:白い正方形に黒い正方形が内接している。黒い正方形の頂点は、白い正方形の各辺の中点に位置している。白い正方形を N×N 等分に分割したとき、完全に黒い正方形で覆われている領域は何個か。(※図を見ましょう)


考察:数学的にがんばって考察すれば、1本の数式で計算できそうな感じがします。しかしこれは 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;
}

筆者の回答 [AC]


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) が答え。

筆者の回答 [AC]


おわりに

D問題は解けず、 解説を読んでACしました が説明できることは特にないので略。


コメントやマシュマロでご意見ご感想ください!

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

AC
3

ベイン

競プロ参戦記を書いていました。言語実装 | 競技プログラミング | Webアプリ開発 | ほか

競プロ参戦記

競技プログラミングの問題を解いて考察を書いていく日記
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。