JOI2012 本選

とりあえずPCをいま付けてないので、簡潔に書きます逃げ。あとで詳しく書くかもしれないし書かないかもしれません。数オリはないです。

2/11
プラクティスに駆け込む。残り7分くらいだったが、snukeに問題名を教えてもらいブラウザ直打ちで全完する。
講演は解かなかったが聞かずにPKUかんがえてた。
懇親会でC++初心者をアピールした。hogloidとバトルをしていた。kyuridenamidaが標的となった。残念。
夜は適当なぎにJubeatをして0:30くらいの比較的早い時間に寝るなど。ありほんたわーができる。みんなありほん2買いすぎ。財力かてない(図書カードがもらえたのに)
りんごさんは「うさぎDASH」を「うなぎの呪文」と称していた。

2/12
ふつうに起きてふつうになんかやる毎年の流れで競技をする。
1:JJavaOOII
J,O,Iの数を累積テーブルにもっといて後ろから見てIの連続ごとに判定した。O(n)
2:たのしいカードゲーム
Reading-Hard
とりあえずnextのリンクをAnnaの各カードについて1000個(ばんごうが1〜1000)もっておき、Brunoでm^2の素朴なDP。O(1000×n+m^2)
3:夏祭り EXT Lv.8 FULL COMBO
式を読むのは不可能なので日本語を読む。
みたらやるだけだしやる。配列長とか最後の答え見るところとかを間違えると面倒。O(nt)
4:きゅうりに釘をさす問題
kyuridenamidaにたくさん釘をうつ。
典型。適当にimos法やるだけ。メモリ制限512MBとかわらえる域。でもかなり使う。O(n^2+m)
5:祭り
まずDijkstraするのは必須。
10%:二分探索してBFSやるとわかる。O(log ほげ+(m+n)q)
30%:UFしてUFするまえのものを何処かに持っておくと、たくさんメモリを使えばn^2の空間でなんとかなる。O(n^2+m log m