ACM/ICPC Asia Regional Contest Phuket Site
そろそろ書いてみることにします。
Practice Session
Problem B
よく覚えていないけど後輩Kが適切に通した。
Problem C
- 文字列のリスト w[1], w[2], ..., w[n] のうち、 w[i] < w[j] (i < j) かつ w[i], w[i+1] の編集距離が1であるものを word sequence と呼ぶ。与えられた文字列集合から最長の word sequence を構成せよ。集合サイズ N <= 25,000, 文字列長L <= 16.
各文字列に対して編集距離が1の文字列全列挙して頑張る問題に見えたけど、ちょっと思うところがあって、N^2回 EditDistance 求めてDPするダメ解法送ってみたら何故か通った。どう見ても O(N^2 * L^2) なんですが。
Problem A
- N個の彗星があって、それぞれ t[i] 年周期で地球に接近し、次の接近は n[i] 年後である。向こう M 年の間に、2個以上の彗星が接近する年はいくつあるか。
入力サイズをよく見てみたら愚直でもどうにかなりそうだったので、@romanchuがさっくり書いて通した。
本番
コンテスト開始
私が .emacs とか .xmodmap とか書いてる間に2人に簡単な問題を探してもらいました。ルールブックをよく見ると、「簡単な問題が2問あって、残りはガチ(意訳)」と親切にも書いてありました。
Problem C
後輩Kが紙の上で計算しまくった挙句、20行に満たないコードを打ち込んで通した。
Problem B
@romanchuによると書くだけだそうなので、さっくり通してもらいました。
Problem J
- コイン両替問題。ただし問題文に関数 T が与えられ、T(i) (1 <= i <= 90) がコインの額面。入力金額は 5*10^18ぐらい。
TをDPで計算しようと漸化式立てたらフィボナッチ数列になった。両替の方はDP出来ないけど、コインの額面は爆発的に増加するので、探索+枝狩りで良さそう。書いてみた。
long longをintに代入しててしばらく嵌った。-Wallも-Wextraも付けてるのになんでコンパイラは教えてくれないんだ・・・。
手元で最大ケース入れても一瞬で答えが出た。送った。通った。
Problem A
- N個の物体があるので、これを1個のstackに出し入れしたい。ただし、物体 i のpushは時刻 u[i] に、popは時刻 v[i] に行わなければらない。最大何個の物体をstackに出し入れできるか。
一緒に突っ込めない物体ペアを全部列挙してグラフに落として最大安定集合・・・だけど、N <= 300なので無理。あれ？この展開どっかで見たような気がする・・・。Neko's Treasureだ！
コンテスト開始直前までずっとねことれ考えていて、どうやら解法らしきものは浮かんだけれども確信が持てなかった。まだ講評も上がってなかったし、無理してでも模擬地区予選はオンサイトで出ておくべきだったなぁ・・・。
それはそれとして、この問題はさっぱり分からん。そのうち@romanchuがメモ再帰でいけそうとか言い出したので、任せて別の問題に逃げることに。
Problem F
- 平安京ウォーキング(UTPC2009::Problem B)。サイズは1,000*1,000程度。典型的DP・・・と見せかけて50,000ケースもある。
通れない辺を含まない長方形領域はコンビネーションで求めるようにしながら計算してみようとした・・・が、書いてみると思ったよりもずっと実装が泥臭くなって死に、組み上がりませんでした。想定解法はもっと別のアルゴリズムだったのかもしれません。
結局Aの方は原因不明のWAを食らい続けたままで、4問28位でした。27位と同ペナルティだけど。
閉会式の途中で、やっとAはただの範囲DPであることに気付きました。Fは・・・包除原理を使うのかな？と今になって思ってたりします。6問最速で解けば2位まで有り得たので、もったいない展開だったなと思います。きっとねこに対する愛情が足りなかったに違いありません。
コンテスト翌日は、ホスト校の学生さんに案内してもらって観光して来ました。彼はPh.D.を取ったら千葉大学に行きたいそうです。何故に千葉？と思いましたが、とにかく「もし日本に来たら、こちらの観光名所を案内しますよ」と言ってお別れしました。また会えるといいな。
