前の練習会

もう一週間たっていますが、
当時あんまり詳しいことを言っていなかったような気がするので、
一応書いておくことに。
結果は…GNCがんばれ。


http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1198
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1199
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1200
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1201
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1202
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1203
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1204
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1205
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1206


この日は私とM氏と二人でのスタート。
来るって言ってたのに…。
まず最初に、当然のごとく回答数チェック。
1200と1201が多いらしい。
1200を聞く。問題のサイズがでかすぎるために一時保留。
NCが何でわざわざ与えられているのか分からない。スキャンすりゃ分かるのに。
1201を聞く。たくさんの人が解いているはずなのに、分からない。考える。
三十分経過。
1201はいわゆる中国人だけが得意なタイプの問題だと言うことで、捨てることに。
1201をnc^n<16Mであると仮定して解くことにする。
どこにもそんなこと書いてないけど、そうじゃないと解きかた分からないし、
どっちにしろ書くの簡単だし、投げやりに書く。
予想に反して問題なく通過。
1198はM氏が両側から探索だと言っていたが、
本当に両側から探索でいけそうなので、作ることに。
盤面をintにエンコードして持ってて、毎回エンコードとデコードを
かける実装になったので、ちょっと重いかな、と思ったら、かなり高速に終わった。
ちなみに、8手以内と書いてあるから、両側から探索かな?
と思ったけど、普通にBFSでよかったかもしれない。
というのも、盤面が64C4通りしかないから。
次に1205。漸化式がすぐに思いついて、すぐに終わった。
長整数のために、久しぶりにJavaを使う。
次に1199をやる。
問題は迷路が解けるかどうかという単純なものだが、
問題の記述に明らかな誤りがあるので困った。
問題には通路とは、少なくとも二辺に壁が面しているところ、
とあるが、それでは十字路が通路じゃなくなってしまう。
と言うわけで、自分を含む2*2マスが全て壁じゃないようなものがあれば、
通路ではない、と言う条件を適当にでっち上げて書いたら通った。
次にやったのは1204。
これも問題はマトリックスの中から単語を探すと言う簡単なものだが、
問題サイズがめちゃくちゃでかい。
あと、答えが二つ以上あった場合の記述が無い。
Discussを見ている限りでは、そういうものはあるらしい。
まぁ、左上、時計回りで調べれば大丈夫だろ、と言うことで実装。
普通に実装したら遅そうなので、先頭一文字でハッシュ。
見事にTLE。
仕方が無いので、先頭二文字でハッシュ。
これでもTLE。
この辺でようやくK氏が来る。遅いって。
1201番を考えてもらう。
1204はもはや怪しげだが、入力に大文字英字しか来ないと仮定して
先頭三文字ハッシュで力技で高速化。
送ってみると、ぎりぎり通過。やった。
次に1206をやることに。
この日はじめてのまともなアルゴリズム問題かもしれない。
最初ダイクストラ30000回だね、間に合わないね、
と言うことで考えていたが、
M氏がよりレベルの高いものが近くにあった場合、
それ以降を探索しなくてもいいことを発見したので、
なんと30000回ダイクストラしても間に合うことが判明した。
まさに驚愕だ。
でも、ダイクストラごとにテーブルを初期化していたら
オーダがあがってしまったり、cinが遅いので、scanfに変えたりで、
いろいろはまりどころはあるので、
そんなこんなで残り10分ほどになってようやくアクセプト。
もう残りは無理だし、一位も確定なので、
速攻で昼ごはんを買いに行く。
終了。
1201の解き方は結局分からず。
多分中国の教科書とかに載ってるんだろうなあ、
ということでDiscussを見ると、
差分約束系統(日本語:差分制約システム)と言うものを使うらしい。
そんなの知らんて。
とりあえず検索してアルゴリズムを調べる。
分かったけど、速度がまにあわんのでは、
と思ったけど、一晩考えたら線形時間で解ける応用が分かった。
というわけで後日アクセプト。
これもライブラリに追加した方がいいのかな。
残りの二問は訳を聞いていないので手付かず。


今回の問題はあいまいなのが多すぎ。
あと、問題サイズがでかいのが多すぎ。
もうちょっとしっかりした問題の方がうれしい。