ZOJ Monthly
http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=314
なんかあったので参加してました．ACがとても出にくい問題が多くてなかなか難儀した記憶が．．
以下，参加記録
START
大学で練習会として参加することにしていたのですが，着いたとき(12:55くらい)にはもうすでに始まっていた．向こうのサーバの時計がちょっと早いのかななんなのかな．
とりあえずノートPCを起動してAを読む．うーん，いくつか電話が与えられるからそれを全部繋ぎたい? (勘違い) 最小全域木? (これも勘違い)
先輩に聞く．あ，3つのノードを繋ぐ最小の木を求めるのか．
なんかダイクストラとかすればできそうな気がする．先輩に聞くとWarshall Floydでいいんじゃねとかいってる．えー，500^3ってどうなん．
とりあえず後回し．
続いてBを読む．うーん，大学に専攻があって，専攻を移動させたい人が19人くらいいるのだけど，移動に制約があって，GPAの高い人しか移動できない．
なんかイメージがよく掴めない．これも後回し．
思い切ってJとか開いてみよう．問題文短い．
ある数を積によって2分木として表すとき，それは何通りあるか求めよ，か．数値的に求められそうではあるけど，適当にDPすればいいんでない? 書く．
適当に書いた．TLE．
ギョエー．手元だと一瞬なんですが… ちょっと頑張って高速化とかしてみるも，TLETLETLETLETLE．うーむ．
納得がいかないので問題文をもう1回読むと，テストケースは1万個くらいあるとか書いてある．なるほどそれはたしかに重い…．
ためしに素因数分解のところだけ送ってみると，1秒強掛かっているっぽい．DPが支配的なのか．確かに，素因数分解なら，Nの約数の個数をσ(N)としたらO(σ(N))程度だけど，単純なDPだとO(σ(N)^2)程度掛かるから，DPが支配的になる．え，これどうすんの… ちょっと放置．
しゃーないのでA適当に書いて，なにかを間違えてTLEをもらうも修正してACもらう．
A Accepted
さて，Iをどうするか…． 先輩と相談すると，葉のノードの個数は常に一定だから，葉じゃないノードの個数も常に一定であるし，あらかじめ葉じゃないノードは何も書かれていない状態にして葉のノードに素数を書き込むと，木を対応させることができる(木全体は葉のノードの書き込み方と1対1対応する)ので，全体では (値を書き込んでいない木の構成方法)×(葉に値を書き込む場合の数) とかでできるんでは… という結論に至る．なるほど…!
前者は適当なDP，後者は組み合わせ係数を使えば可能．書いてsubmit，AC．
J Accepted
StandingsをみるとHが結構とかれている．というか某社のインターンに行ってるはずの先輩がなぜか参加して上位にいるんですが，どういうことなの…．
読む．うーん，カレンダーの日付系? 12*11年周期で考えればいいし，やるだけのように見える…．Jよりこっちのが簡単．
H Accepted
再びStandingsをみるとGがそこそことかれているのでGを開く．ギターがどうのこうの書いてある．よく知らない単語いっぱいあってよくわからんけど，なんか演奏のシミュレートするだけ?
…問題文読んで実装するだけじゃないのかこれ．ｳｪｰ('A`)
うおーだりーと思いながら書く．提出．WA．ギョエ．
よく読む．2回目以降初期化してなかった．書き直す．AC．
G Accepted
さてあと45分ほどあるわけだが，解くならEかBってところだろうか．
Eは1000本くらいの線分集合と，格子部分の交差部分の個数を求めよ，というもの．なんかやればできそうだけどAC率3%とかになってんのがキモい… やめる．
Bをもう1回よく読む．よくわからんけど，ハノイの塔で，最初の状態と目標の状態が与えられるから，最小手数で目標の状態にしろ，というものらしい．なるほど．
ハノイの塔はたしか振る舞いがかなりよかったはずなので，考えればさっくり解けそうな気がする，気がするのだけど，もうなんかめんどい…
とりあえずN<=19だしBFSでも書くか〜と思って書いてTLEもらってたら終わってた．
結果
http://acm.zju.edu.cn/onlinejudge/showContestRankList.do?contestId=314
4ACで44位でした．Bは探索とかしなくてもふつうに解けると思うので後で解きたい．
あと，Eも先輩がO(N^2logN)の解法にたどり着いてはいたので，それも後で試してみたい… かも．TLEになる可能性あるけど．
B解いて20位くらいになりたかったなー ('ー`) にしても学内の赤い先輩方2人が並んで1桁順位取っててなかなかぱないです．
誰もやってないから難しいはず，とか思ってはいけないのだと思いました．
