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

TTPC2015 参加記

11:00 頑張って起きる
12:20 六本木に着く
12:30 迷う,森タワー消滅
12:50 ついた
13:00 contestantが遅刻しすぎて延長
13:15 開始
流石にコンテスト中の順を追うのは面倒なので問題番号順で
A:やるだけ
B:やるだけ
C:めんどいやるだけ
D:めんどいやるだけ
E:やるだけ
F:0と9以外考えなくていい,下の位から貪欲.
G:何も考えずにコスト-1にしてmin_cost_flowしましたすみません(この方法だとどんな文字列でも行ける気がしたけど嘘かもしれない(例えば"tttt"とかだとダメ?))
H:はじめ凹四角形忘れててWAった.
I:1と2を動かしまくろうとしたけどめんどかった
賢い解法として,一番右(とそいつと自明にスワップ出来る左のやつ)を選択し続けるというのがある.これでちゃんと一番右(1-indexedでNとする)に正しい奴が出てくることの証明は,右に出てくるやつを順番に書いてくとNが出てこないかぎりswapは続けられるので,N未満がループせねばならないが,同じ値は2回出てこない(なぜなら,右端からxを送ったとするともう一度xが出てくるためには右端にxが必要になるがそんな状況はありえないため) よってループは起こらず,すなわちNが出てくる.
J:O(N^2logN)で普通にやったんだけどO(N^2)どうやるんだろう
K:2人ゲームの時の結果を知っていたのでどうせ一緒じゃねと思ったら一緒だったらしい.証明は知らない.
L:残余グラフでカット
M:気づかねー・・・ もうちょっと実験してたら気づいたかなあ 証明はまだちゃんと分かってない
N:にぶたんの解法だと普通にできそう
O:ほげ
P:ふが

全体:
おもしろかったです。でもぜんぜんとけなくてかなしかったです。実際十分に時間が与えられればNまでは解けそうだけどやっぱりコンテスト中は時間が一瞬で溶ける。