ACM/ICPC の問題を解いてみる

寝付けないので自前で考えた解き方を試しに実装してみた．解説聞いてないので合ってるかどうかは知らんけど．

A: LinkedList で普通に要素を抜いてくだけ．最大サイズでも一瞬で終わるのでこれで問題なさそう．

B: エラトステネスのふるいで素数求めたら終わり．与えられた数から前後の素数を探索するのは前後を順に見てくだけでいい．

どうせすぐ近くに素数があるだろうから．

C: 状態遷移行列を T乗すると考えるかT回の状態遷移を計算すると考えるか…　状態遷移行列が疎なのでグラフ上で状態遷移をシミュレートするイメージの実装．スタートに戻るマスへの遷移はスタートへ足しこむ．一回休みは一回休み用のノードを作って一度そのノードへ遷移するようにする．計算量は O((N+L)T) なので時間も問題ないでしょう．

D: 面倒なので考えてない．一つの三角形を決めたら他も決まるから全部の点を試せばいいのかな？

E: これもグラフを作るまでが面倒．グラフさえできれば最短路なので楽．

F: ソートした辺のリスト上で最大重み用のポインタと最小重み用のポインタをスライドさせてく．二つのポインタの間にある辺集合で全域木が作れるなら最小のポインタを進める．作れないときは最大側のポインタをするめる．全域木ができるかの判定は連結しているかの判定でできるので適当に Unon/Find でやった．これで全体としては O(E^2) だけど…　手元では最大サイズが一秒以内なのでギリギリオッケー．

G: 状態空間のサイズが 2^24 程度なので普通に幅優先でいい気がする．ただ最大サイズのサンプル入力で４秒かかるのでもう少しコードを特化した方がいいかもしれない．

H: 再帰下降で Exception なげて帰ってくる．Hashtable とか使わないとインデックスで困るけどそれだけだと思う．

I: 面倒なのでパス．多角形を周りから削っていって最後に残ったところか？何となく島が海に沈んでくイメージ…

J: 連立方程式立てて解けば終わりなのだけど…　有理数で一次方程式を解かねばならないし（doubleとかでもいいのかな？），そもそも方程式の係数を求めるのも面倒．コード書きたくないから二乗根の場合に関して手で解いてみただけ．久々に 4x4 の一次式を解いた．

とりあえず，ABCFGH の実装に（テレビ見をながらではあるけど）５時間ほど．やっぱ９問解いたチームってのはすごいなぁ．