2日目の途中から参加した.
結果は,
2日目: 一人で参加. AとD の2完で20位.
3日目: @tokoharu_sakura さん, @mikecat_mixc さんと bugnyan で参加. A-D, F-H, K の 8完で6位.
4日目: @nsd_fb さん, @yuusti さんと Tera^nyan で参加. A-F の 6完で6位
でした. 楽しかったです. (小並感)
全体を通して, ワンチャンある問題が解けないという事が多かったように思う.
ワンチャンあると感じた問題が多いという事は, 強くなるチャンスであると信じて, 精進したいです.
あと, チーム戦楽しい. またいろんな人と組んでチーム戦してみたい.
チーム組んでくれた方々, JAGの方々, 某社の方々など, 色々ありがとうございました.
りんごさんセット.
問題文が簡潔で読みやすかった.
東京へ帰る新幹線中から参加し始め, 昼過ぎにオリセンに到着した感じ.
開始時とかトンネルの中でネット繋がらなくてつらみを味わった.
基本的に, ちゃんと考えるという事を放棄しすぎていた気がする.
G(Snake), 解きたかった. 凸包使おうとまでは行ったけれど, ちゃんとそこで止まって思考すべきだった. (適当に書きすぎ)
H(Distance Sum) は, 大体はやるべき事は解ってたし, 解けてもよかったなぁという気がした. ちなみに, 解説の場合分けは多分要らなくて, 偶奇どちらの場合も, 今の場所から追加された場所までの path 上でにぶたんすればよいハズ.
J(Hyperrectangle) は, 包除原理だろー -> d <= 300 (絶望) という感じだった. なるほど, こういうのもあるのか...
JAGセット.
リクルート社で行われた.
至れり尽くせりすぎてすごかった. 神社とか言われてた.
@tokoharu_sakura さん, @mikecat_mixc さんと参加した.
みけきゃっとさんが A を解いている間に B を読んで, まぁやれば出来るやつやなと思って詰めずに他のを読みだしたりしてしまって, ICPCルールでのチーム戦を完全に忘れた感じの戦犯だった.
B終わって, みけきゃっとさんが F はフローの問題だと言っていたので, 自分でも読んだら, 最小カット持ってくるだけだったので通した.
後, 色々問題を把握して, D は水の量で三分探索で出来そうだなぁとか, G は nCk と分割数でやればいいよねとか, K は 2近傍の全探索でいけるねとかいう話をした.
I は 1, 2彩色はやるだけで, 3 と 4 の判定は 3 を適当に枝狩り探索じゃないのという話とかもした. (もっと詰めた話をしておけばよかった. みけきゃっとさんには申し訳ない...)
とこはるさんが E の解法を教えてくれて, 合っているっぽかったので書いて提出するも, WA.
結局 WA が取れなくてつらかった. なんでなんだろう...
I と E はチャンスがあったなぁという感じがする.
阪大, 東工大セット.
@nsd_fb さん, @yuusti さんと参加した.
A, B をやるから好きな問題読んでという事を言われ, 最後に図が見えたので最後から適当に読み, その後共有する.
以下, 読んだり共有した時の感想.
C: 三次元幾何だけど, 点の線分への射影しか要らんのでやれば出来る
D: なんか DP っぽい問題. (入力でかいと指摘されて, 適当なテクで n log に落とす系じゃないのと言うけど, 全然わからん)
E: 実装ゲーっぽいけど無限ループとか大丈夫? (盤面サイズ x プログラム長メモ出来るし余裕でしょと言われる)
F: 文字列マッチやるだけっぽい. (文字列苦手勢としては, おまかせしたい)
G: 2^18 だし, bitDP とかしたけど, 壊すとかあるからどうしようね...
H: なんかこれは頑張れば出来る系の ad-hoc では???
I: これ面白いけどどうにかならんかねぇ... 最小有向全域木みたいな何かとか?
J: これは思いつきゲーっぽいけどやばげだ...
とりあえず, C を書く.
EPS 必要な所(接線)を EPS どっちに付けるんだっけ, 問題文にあったかなぁと思いつつ後で書く事にしたら忘れて提出, WA.
問題文に無かったけどサンプルにあったから書いて提出, WA.
問題文よく見てみたら, l <= 10^16 とかあって絶望.
無意味な long long 制約やめちくりー.
怒りの でふぁいん いんと ろんぐろんぐ してACした.
E, F は書いてもらえる事になって, D, H, I, J を考える.
J はしばらく考えて思いつかないので, 残念だけれど捨てる.
I はしばらく @nsd_fb さんと考えて, 最小有向全域木のアルゴリズム教えてもらったりしたけど, なんか steiner tree っぽい難しさな気がしてきてわからず, 悔し紛れに NP-hard じゃないのとか思いながら捨てる.
H は少し考えて, これ D の方が僕に合ってるなぁと思って, 保留する.
ひたすら D を考える.
メモを見ると, 「monge, 貪欲, データ構造, にぶたん, ダブリング, 平方分割, 分割統治, convex-hull trick」とか, 考慮するリストとしてメモってあった.
終了30分くらい前に, 更新する箇所が少なかったりとかは全然しなさそうだし, 二乗の DP を高速化する系じゃ不可能な気がして来て, 「これ貪欲でしょ」と言い出す.
一回目の選び方を計算して, 「i*P + C_i で貪欲だー」と言い出して, 頭冷やす為にトイレに行く.
帰ってきたら, 入力処理とか書いてくれていた(感動).
この貪欲でサンプル全部通るっぽいので, 書いてみる.
更新式を明示的に書き下さなきゃいけないので, 計算してみると, 貪欲が正しい事が式から出てきて歓喜する.
証明を一応書いておくと, k 回自炊している時, 更に i 番目を自炊にする時, 満足度の変化を考えると,
(i以降の自炊で得られる幸福度が増える) + (iで自炊した時の幸福度) - C_i
= 2 * (i以降の自炊) * P + (Q - i + 2 * (i以前の自炊)) * P - C_i
= 2 * ( (i以前の自炊)+(i以降の自炊) ) * P + P*Q - i*P - C_i
= 2*k*P + P*Q - i*P - C_i
となる. よって, k に関する累積和を考えると, i*P + C_i の和が小さくなる i を k 個選ぶ事になるから, 貪欲でよい.
提出して WA.
accumulate の第三引数に 0LL じゃなくて 0 渡していた(絶望).
気づけてよかった.
修正して提出, AC った. (終了10分前)
なんか, 危うい所で D 解けたけど, 2-3時間くらいこれ考えてたし, 実装重いの全て任せてしまったし, これで D が解けてなかったら完全に戦犯だった.
自分で書いたの 100 行もないし, ありがたやーという感じ.
合宿中も「疲れた」ばかり言ってたけど, コンテスト終わると更に疲れて, 口を開くと「疲れた」が出てきて非常にアレだった. (ごめんなさい)
疲れを取り除くべくがんばって休みます.