読者です 読者をやめる 読者になる 読者になる

Golden Week Contest 2015 解説

Welcome to Golden Week Contest 2015 - Golden Week Contest 2015 | AtCoder
というコンテストをAtCoderさんで開かせていただいていました。

まずは、チーム/個人それぞれののtop10から。

チーム

順位 チーム名 点数 問題数 時間 全体順位
1 カラフルジャンボチキン 621 7.5 234:17 3
2 代々木に行くよ(回文) 563 7 221:34 8
3 チーム爽健美茶 563 7 246:07 10
4 †地獄†零春 ‡チーム‡ 563 7 246:07 12
5 chikOkU 487 6 274:59 16
6 yosky 435 6 139:42 18
7 camypaper,nuip 435 6 211:44 21
8 お姉ちゃんと猫 435 6 225:42 22
9 btk(チーム(一人)) 136 2 92:09 43
10 sonna*baka*na 25 1 126:10 110

個人

※すぬけ さんはりんごさんです。

順位 ユーザ名 点数 問題数 時間 全体順位
1 すぬけ 1000 10 198:16 1
2 semiexp 837 9 201:25 2
3 uwi 621 7.5 266:46 4
4 chokudai@AtCoder社長 621 7.5 273:04 5
5 すぎむ 621 7.5 306:56 6
6 cgy4ever 598 7 312:52 7
7 satos 563 7 230:22 9
8 kmjp 563 7 245:27 11
9 stqn 563 7 272:15 13
10 Lepton_s 563 7 297:44 14

各問題の解説

A 得点

DPすればいいです。G問題を初期化のときに処理しておくと楽です。

2^9 * 3 個全部を列挙して重複を取り除いても良いです。

B アリ巣

10080ターン目あたりから長さ104の周期に入ります。

ラングトンの蟻です。

ラングトンの蟻はこれで知りました。

C Snukeと対戦!

HとWのどちらかが偶数の時

後手を選択し、相手の手と点対称な位置に相手と反対の色の碁石を置く。

HもWも奇数の時

先手を選択し、真ん中に碁石を置く。

その後は、相手の手と点対称な位置に相手と同じ色の碁石を置く。

D 最短絡問題

dist(1,1,i,j) を質問し、h[i][j] としておく。

dist(si,sj,ti,tj) を質問されたら、ti>siのときは、siとti・sjとtjを交換しておいて、

  • si ≦ ti かつ sj ≦ tj のとき:h[ti][tj] - h[si][sj]
  • そうでないとき:(h[ti][tj] - h[si][tj]) + (h[si][sj] - h[si][tj])

を答える。

左上(マス(1,1)の方)から右下へ行く経路は(左や上に行かなければ)どんな経路でもコストは同じで、左下から右上へ行く経路は最初に上にずっと行ってそこからずっと右に行くような経路が最短であることが証明できます。

タイトルが少し変なのは、間違い探し的な意味しかないです。(問題自体に短絡要素はあんまりない気がする)

E シフト塗り分け

L = N のとき

蟻本のポリアのところに書いてあります。

L が偶数の時
  • 12345 → 41235 → 45123

というようにシフトすると、L+1 のシフトを偶数回繰り返したものが構成できます。L+1 が奇数なので、L+1 のシフトも構成できます。

L のシフトと L+1 のシフトを組み合わせると、

  • 12345 → 41235 → 12354
  • 12345 → 45123 → 24513 → 13245

のように任意の場所をswapできます。ということは、全ての順列を作ることができます。

この場合は「K個の色からN個の色を重複アリで選ぶ場合の数」になります。

L が奇数の時
  • 123456 → 512346 → 561234

というようにシフトすると、L+1 のシフトを偶数回繰り返したものが構成できます。

L のシフトと L+1 の偶数回シフトを組み合わせると、

  • 123456 → 451236 → 123645
  • 123456 → 145623 → 231456
  • 123456 → 561234 → 235614 → 142356

のように任意の場所で 3 のシフトができます。

3 のシフトができると、偶置換が作れます。(前からN-2個を順番に埋めていけばいい)

偶置換を同じとみなす時の塗り分け方は、

  • 全部異なる色で塗る場合:各色の選び方について 2 通り
  • 同じ色がある場合:各色の選び方について 1 通り

となるので、この場合は「K個の色からN個の色を重複アリで選ぶ場合の数」+「K個の色からN個の色を重複ナシで選ぶ場合の数」が答えになります。

F ピラミッド - 誕生日編

N が奇数の場合

石の総数の偶奇で決まる。

N が偶数の場合

石の個数が最小の山にある石の個数に注目します。これを X とします。

  • X = 0 のとき:石の総数の偶奇で決まる。
  • X = 1 のとき:その山の石を取る or 全部の山から石を取る のどちらかを行うことで、X = 0 にでき、石の総数の偶奇を自由に選べるので勝ち
  • X = 2 のとき:X を 1 にすると負けるので、全部の山から取る操作をすると負ける。つまり、石の総数の偶奇で決まる。
  • X = 3 のとき:その山の石を取る or 全部の山から石を取る のどちらかを行うことで、X = 2 にでき、石の総数の偶奇を自由に選べるので勝ち

というふうに、X が奇数のときは先手必勝、X が偶数のときは石の総数の偶奇で勝敗が決まる。

G ピラミッド - 球編

ある穴が壊れた時に石を置けなくなる場所は、直方体状になっています。

部分点は包除原理で計算すれば良いです。

満点は、JOI2011-2012 Day1 Fish 解説

H ピラミッド - デコ編

ある石の色が勝敗に関係するかどうかを計算します。

数式はいろいろありますが、x = B-1, y = A-B, z = L-A とすると

  • (x|y|z) == x+y+z なら勝敗に関係する

となります。あとは、勝敗に関係する黒の位置の個数 (mod 2) を求めればいいです。

段数によって結果が反転するので気をつけてください。

I ピラミッド - 立方体編

簡単だったらしい。

DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+1, H[i][j])

を4方向に計算すればいい。

想定解ではもう少し複雑なDPをしてしまっていました・・・

J ピラミッド - 2D編

ヤング図形 - Wikipedia

これを求めるときの分母を効率的に求めたい。

  • f(a, x, y) = a~a+x+y-2がずら〜と並んだx*yの長方形の積

という関数を求められれば良い。

例えば、f(4,4,3) は

4 5 6 7
5 6 7 8
6 7 8 9

の積を求めればよくて、4*5*6*7*5*6*7*8*6*7*8*9 になる。

これを求めるためには、10^6 くらいまでの

  • ∏ i^i
  • i! (階乗)

の値が前計算してあれば良い。

次に、以下の図のイメージで計算(赤を掛けて青を割る)すれば三角形の部分(∏ (i+a)^i)が求まる。

f:id:snuke:20150505175344p:plain

あとは、以下の図のイメージで計算すれば f も求まる。

f:id:snuke:20150505175359p:plain