ARC102 参加記録

今回も前回に引き続きD問題が700点という、ABCには厳しい回でした…

結果は3完79分で30位…一気に黄色になりました！びっくりですね。highestパフォ400くらい更新しました。

f:id:betrue12:20180902001717p:plain

黄色になりました記事は別途書きます。この記事ではC～E問題を振り返っていきます。

C - Triangular Relationship

解法

$a, b, c$ について、 $a+b, b+c, c+a$ が全て $K$ の倍数でなければいけません。数値が3つあると考えにくいので、まずは1つにできないか考えましょう。

$a+b, b+c, c+a$ から $a$ だけの式を作ることを考えます。 $(a+b) - (b+c) + (c+a)$ を計算すると結果は $2a$ になって、 $a$ だけの式になります。

この値は $K$ の倍数3つを足し引きしているものなので、やっぱり $K$ の倍数です。つまり、 $2a$ が $K$ の倍数であるということが言えます。ここから、

$K$ が偶数の場合、 $a$ は $K$ で割った余りが $0$ または $\frac{K}{2}$ でないといけない
$K$ が奇数の場合、 $a$ は $K$ で割ったあまりが $0$ でないといけない

ということが言えます。

これで、 $a$ を $K$ で割った余りは2通りまたは1通りに絞れました。 $0$ か $\frac{K}{2}$ かで場合分けをして、 $b, c$ も含めて問題の要求を満たす条件を明らかにしていきましょう。

をで割った余りがの時…
- $(a+b)$ が $K$ の倍数であるためには、 $b$ を $K$ で割った余りも $0$ である必要がある。
- 同様に $(c+a)$ が $K$ の倍数であるためには、 $c$ を $K$ で割った余りも $0$ である必要がある。
- $b$ も $c$ も $K$ で割った余りが $0$ であれば、 $(b+c)$ も $K$ の倍数となる。
をで割った余りがの時…
- $(a+b)$ が $K$ の倍数であるためには、 $b$ を $K$ で割った余りも $\frac{K}{2}$ である必要がある。
- 同様に $(c+a)$ が $K$ の倍数であるためには、 $c$ を $K$ で割った余りも $\frac{K}{2}$ である必要がある。
- $b$ も $c$ も $K$ で割った余りが $\frac{K}{2}$ であれば、 $(b+c)$ も $K$ の倍数となる。

書いてあることはほとんど同じになりますね。どちらの場合も、全ての数が共通の余りを持っている必要があります。ここから、以下のように解くことができます。

$N$ 以下の正の整数で $K$ で割った余りが $0$ になるものの数を数え、3乗する。
$K$ が偶数の場合は、 $N$ 以下の正の整数で $K$ で割った余りが $\frac{K}{2}$ になるものの数を数えて3乗し、↑と加算する。

これで解けます。

ACコード

D - All Your Paths are Different Lengths

解法

俗に「構築」と呼ばれる、条件に満たす数列やグラフなどを何か1つ作れという問題。こういう問題では、サンプルの出力例はあまり期待しないほうがよくて*1、制約内の入力のうち何がきても、機械的に同じ手順で対応できるような「必勝法」を探すことが多いです。

さて、最も主要な条件は「頂点 $1$ から頂点 $N$ までの経路が $L$ 通りあって、それらの長さが $0, ..., L-1$ になっている」ということです。このように連続する自然数をもれなくダブりなく表現する方法として、10進数や2進数のような進数表記があります。

とりあえず2進数で考えてみます。そして、まずはキリ良く $2^{N-1}$ 通りの数を表すことを考えてみましょう。

f:id:betrue12:20180902013420p:plain

このように $N$ 頂点のグラフを作ってみると、左端から右端までの経路は「4回の移動でそれぞれ上下どちらを通るか？」の組み合わせで $2^{4} = 16$ 通りです。そしてこれで、長さ $0, ..., 15$ のパターンを綺麗に網羅しています。もし $L$ が $2^{N-1}$ の形で表せるような数だったら、これが答えになりますね。

これを基本アイデアとして、端数を調整していくことを考えましょう。例えば $L = 20$ の場合は、長さ $0, ..., 15$ を作った後、そこに長さ $16, 17, 18, 19$ の経路を追加する必要があります。この経路は以下のように追加することができます。

f:id:betrue12:20180902014617p:plain

$L = 22$ の場合はどうでしょうか。追加したい経路が6個なので一度に追加することは難しいですが、 4+2と分ければ以下のように追加することができます。

f:id:betrue12:20180902014709p:plain

一般的に考えると、2進数で作った経路の途中までを見ると $2^{k}$ の経路ができていて、その長さが $0, ..., 2^{k}-1$ になっているはずです。そこから適切な長さでゴール地点までのショートカットを作ると、好きな数字から始まる $2^{k}$ の連番が作れますね。これを良い感じに組み合わせていくと、作りたい長さまでの連番ができます。

最後に、頂点数と辺数について確認しておきます。*2

頂点数 $N \le 20$ だと2進数の桁を最大19個作ることができて、2進数19桁で表現できる数は $2^{19}$ 通りです。そこからショートカットを $N$ 以外の全頂点から追加で1本ずつ伸ばすと、増える経路数はそれぞれ $+2^{18}, +2^{17}, ..., 1$ であり、最大で $2^{20} - 1 = 1048575$ 通りになります。 $L \le 10^{6}$ （100万）なので頂点数は足りそうです。

辺数 $M \le 60$ については、まず2進数19桁を作るのに38本。ショートカットを1本ずつ伸ばすと、追加が最大19本で合計57本。足りそうですね。

ACコード

E - Stop. Otherwise...

解法

※実は要らないらしいのですが包除で解いたので包除で解説を書きます。

基礎知識

まず今回の問題を解くには、「 $K$ 個のものから、重複を許して計 $N$ 個選ぶ時の組み合わせ」の数え方が必要です。*3

これは重複組合せと呼ばれていて、 $_{K}H_{N}$ と記載することもあります。その総数は公式として有名で、通常の組み合わせの記号を使うと $_{K+N-1}C_{N}$ 通りとなります。

あとは包除原理。一般には、「または」の計算を「かつ」の結果の足し算引き算だけで求めることができるという原理です。

そのまま使うこともありますし、問題では「どの～も○○でない」という「かつ」型の条件が与えられていて、そのままだと考えにくいので条件を反転して「または」型の条件にしてから包除原理を使うこともあります。今回の問題はそのタイプです。

考察

どの2つのサイコロの和も $i$ にならない、という条件をいくつか書き下してみましょう。

和が2にならない。
- 1と1の組み合わせが作れない。つまり、1の数が0～1個。
和が3にならない。
- 1と2の組み合わせが作れない。つまり、1と2の少なくとも片方が0個。
和が4にならない。
- 2の数が0個～1個。
- 1と3の少なくとも片方が0個。
和が5にならない。
- 1と4の少なくとも片方が0個。
- 2と3の少なくとも片方が0個。

こんな感じになります。

これを一般化してみると、 $i$ それぞれについて、問題の要求は以下のような条件になります。

同一数のペアによる条件（が偶数のときのみ）
- ある1つの出目 $\frac{i}{2}$ について、その個数は0～1個である。
異なる数のペアによる条件
- ある $M$ 個の出目のペアについて、そのうち少なくとも片方は0個である。

（これらの数やペアには、重複して含まれる出目がない、ということも大事です。）

少なくとも片方が0個である必要がある、揃ってはいけないペアのことを「NGペア」と書くことにします。それぞれの $i$ についてのNGペアの個数 $M$ は、面数 $K=6$ とかで書き下してみるとなんとなく法則が分かると思います。

$i$ が奇数の場合のほうが条件が少ないので、まずは奇数の場合を考えます。

$i$ が奇数の場合

「 $M$ 個のNGペアのうち $m$ 個を固定した時、それらが全て存在しているような場合の数」というのを考えます。残りのペアについては、存在しているかどうかは不問です。これを全ての $m$ について求めると、包除原理でNGペアが0個の時の場合の数が求められます。

この固定したペアの出目は必ず存在するので、まず出目にサイコロを1個ずつ割り当てます。残ったサイコロは $N - 2m$ 個です。

最後に、残ったサイコロは $1, ..., K$ のどの目になってもよいので、 $K$ 個の出目から $N-2m$ 個を選ぶ重複組合せを数えます。この過程で、新しいNGペアができたり、固定したNGペアがさらに増えたり、NGペアが全く増えなかったりしますが、これらは分けて考える必要がありません。これはとても便利で、包除原理を使ってまで条件を言い換える最大のメリットになります。