■ [others]UTPC2012 
practice
4個目のケースの問題文を前から1文字ずつ推測しようとして、WAとREとTLEとMLEで分岐させようとしたらMLEを意図的に発生させるのが難しくて挫折した（単純にでかい配列取るとREになる）
というか3分岐でも4分岐でもアルファベット1文字決めるのに3回のサブミットが必要なのは一緒だから気にしなくてよかった
本番
オンサイトで参加した。隣の席だったりんごさんが2Lの緑茶をおもむろに取り出して威嚇してきた
- F
- 部分点が???になってて面白そうだったのでまず見てみたけどすぐには方針立たないので次へ
- E
- きっと反例あるんだろうけどとりあえず二分探索で投げてみた→やっぱりWA
- どうせ嘘解法なんだから時間制限いっぱいまで調べるようにしておけば良かった
- A
- やる
- B
- 後ろから
- C
- D
- G
- E
- 適当な上限から時間いっぱい調べるのを書いて部分点をもらう
- F
- なぜか最初a==26だと思い込んでて、任意のハッシュ値を持つ文字列を作るの可能やーん、とか思ってた。アホだ
- 半分全列挙に近いアイディアでやった
- 5文字の文字列を全部生成してハッシュ値とともにメモっとく。26^5≒10^8なので、最悪のb=10^9のときでも1/10くらいの確率で、ランダムに作った文字列をメモっておいた文字列のうちどれかと組み合わせて特定のハッシュ値にできる
- 実際は5文字を全生成するとTLEしそうなので、4文字だけ全生成しておいてあとの1文字の分は毎回調べれば良い
- これで提出したら190点になった
- （あとで）全体の文字列のハッシュ値が0になるものを探していたけれど、bがaの累乗の場合はどうやっても0にならない場合があると気づいた
- のでハッシュ値を1になるようにしてみたら今度は198点…
- あと1ケースが何なのかよくわからない
- D
- 一応部分点だけ取っとく
- L
- E
- 適当な下限から時間いっぱい調べるのを書くが、残り時間少なくて焦っていたので賢くない方法になってしまい正解できず
手を付けなかった問題について
- H
- ぱっと見ではなんか区間をlogNで処理するようなややこしいデータ構造使うのだろうかと思って重く見えてしまった
- I
- 部分点だけならDPすればできそうに思ったけど実装しようとする気力とか時間がなかった
- J
- 問題文長いし、見るからにwataさんの問題でどうせ最小費用流だろうと思ったので飛ばした
- K
- 図形がやばそうなので飛ばした
提出履歴：http://utpc2012.contest.atcoder.jp/submissions/all?user_screen_name=tomerun
結果
- 100 + 100 + 100 + 50 + 50 + 190 + 200 + 0 + 0 + 0 + 0 + 50 = 840
- 総合24位/170チームくらい
- 個人12位/150人くらい
