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 個全部を列挙して重複を取り除いても良いです。
C Snukeと対戦！
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 が偶数のときは石の総数の偶奇で勝敗が決まる。
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])
を４方向に計算すればいい。
想定解ではもう少し複雑なDPをしてしまっていました・・・
J ピラミッド - 2D編
これを求めるときの分母を効率的に求めたい。
- 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 も求まる。
