ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

ARC102 参加記録

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

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

f:id:betrue12:20180902001717p:plain

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

C - Triangular Relationship

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

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

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

これで解けます。

ACコード

D - All Your Paths are Different Lengths

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...

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 それぞれについて、問題の要求は以下のような条件になります。

  • 同一数のペアによる条件( 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ペアが全く増えなかったりしますが、これらは分けて考える必要がありません。これはとても便利で、包除原理を使ってまで条件を言い換える最大のメリットになります。

f:id:betrue12:20180902024230p:plain

このように計算すると、「 M 個のNGペアのうち  m 個を固定した時、それらが両方存在しているような場合の数」は  _{K}H_{N-2m} です。

 m 個のペアの選び方は  _{M}C_{m} 通りなので、これらをまとめると

 _{M}C_{m} \times _{K}H_{N-2m}

となり、この値を包除原理に基づいて足し引きしていけば、答えが求められます。

 i が偶数の場合

 i が偶数の場合は同一数のペアによる条件があって、具体的には出目が  \frac{i}{2} のサイコロの個数が0~1個でなければいけません。

というわけで、0個か1個かで場合分けをします。同一数のペアによる条件を処理してしまえば、あとは奇数の場合と同じように考えることができます。出目が1つ使えなくなることに注意してください。

  • 出目が  \frac{i}{2} のサイコロが0個の場合
    • サイコロの出目の総数が  K-1 個、サイコロが  N 個として、奇数の場合と同様に考えられる。
  • 出目が  \frac{i}{2} のサイコロが1個の場合
    • サイコロの出目の総数が  K-1 個、サイコロが  N-1 個として、奇数の場合と同様に考えられる。

これを両方計算して、合計すればよいです。

ACコード

さいごに

700点問題が本番で通るようになってきたのは本当に嬉しいです。実際、500~800点くらいの過去問をけっこう解いてきたので、その成果が出ていると思います。

次の記事は「AtCoder黄色になりました」の予定です!

脚注

*1:本来の解法を隠すために、わざと不規則な例になっていることも多いです。

*2:今回は説明の流れを切らないために、最後に制約確認をしましたが、実際にはアイデアの骨子が浮かんだ段階で「足りそうか?」というのを考えるほうが良いとは思います。これで足りない場合、2進数から別のn進数に考え直してみるか、節約の方法を考えるか、全く別のアプローチを考えるか、になると思います。

*3:今回の問題と記号を合わせています。リンク先のWikipediaと逆なので注意。