天下一プログラマーコンテスト 2013 本戦

コンテスト前

• 精神統一を実施していないことに気づきあわてて http://www.nicovideo.jp/watch/sm17720979 を視聴する（ただし時間が足りなかった）

A

• A 問題でしかも 40 点だしどうせ簡単な方法だろう
• この mod とかいうやつもフェイクに違いない
• と思って探索を書き始める
• どう考えても 2^49 以上答えあるし無理だろ
• まじめに bit DP を書く
• 通る

B

• 読む
• イメージわかない
• 手ですこし試す
• よくわからん
• よくわからないときは「きっとトリックがある」のでとりあえず 2 つのシャッフルを書いて試す
• なんかリフルシャッフルとカットは簡単な規則で交換できそう
• r 回リフルシャッフルするとして、最初に r 回やってしまってその後カットを(このとき勝手にカットの数を 1, 2, …, 2^r 倍にしてよい)行う、という場合だけ考えればよい
• 書く
• 通らない
• 何回か直す
• 通らない
• リフルシャッフルしたあとに、「あとはカットだけで直せる」状態にしないといけないが、1 度そうなったあとにまたリフルシャッフルを繰り返して同じ状態にしてからカットをしたほうがうれしい場合がある、という罠に気づく
• 書く
• 100 点
• あとで考えよう

D

• とざんが爆速で通していてやばみを感じる
• 読んでみたら包除原理やるだけっぽい
• 書く
• バグる
• C(3, 1) = 9 とか出てきてファッってなる
• 直し、C の計算を O(1) でできるようにする
• 通る

• B に戻ってきて、いろいろ試す
• 試しているうちに通る

• 残るは C と E、どっちにしよう？
• E の満点とか解ける問題に見えないので、C を書くか E の 60 点を書くか
• E のもう 60 点は最大流の場合の数を求めるっぽいけどそんなん知らんし書けない
• とりあえず E の入出力くらいは書いておいた

C

• 書けば通りそうだったのでがんばって書く
• 0 点
• 盤面は正方形に限らないらしい
• それにしても 0 点なのはおかしい
• よくみたら、「上に来る辺の番号」じゃなくて「最初上だった辺の位置」を答えなきゃいけないらしい
• 直したら 26 点が来る
• 長方形でも動くようにして 142 点

E

• C で 18 点取りに行くより E で 60 点とったほうがうれしい
• C, E で迷っている時に E を読んで部分点解法を想像しておいたので、set を使って DP すればよさそうだとわかっていた
• 書く
• 60 点

• C あと 18 点増やせる気がしない
• 内部、辺、角に分類して試すピースを限定する方法をやろうと思ったけどバグる
• 少しだけ限定する
• 142 点から増えない
• やめた