JOI2009-2010 予選報告

高校2年なので今年が最後のチャンスなのですが、参加しました。
一応全部解けました。
何とかして本戦でも頑張って、春合宿に行きたいものです。


とりあえずソースはそのうち載せるので今は解法だけ。

Q1

最初の入力から、あとの入力を引いていくだけ。

Q2

サイコロの目とすごろくのマス情報を配列に保存して交互に足していくだけ。

Q3

各生徒の友達リストを作って、1さんの友達の友達まで招待リストに加えるだけ。
入力例2「あなたには友達が居ない。」

Q4

nPkの順列を生成して、出現リストに加える。
最大99が4つ並ぶだけ(99999999)なのでint型に変換しても良い。

Q5

座標と元居た座標の方向(西or南)と直前に曲がったかの4つのパラメータでdp。
100*100*2*2=40000なので余裕で間に合う。
要素間の依存関係がちょっと面倒。

Q6

始点からの降り立った家のリスト(ビットで管理)と最後に降り立った家の番号でdp。TSPの変形。
ある家aから他の家bに渡るまでに上空を通過する家のリストをビットで保持しておき、
そのビットと降り立った家のビットでANDして0でなければ枝刈りとか。
あと23・2^23 * 4byte=736MBを確保するのは(PCによっては)難しいので、map,int>で保持するのも手(入力5でも20MB位になる)。


なんかすごい偉そうに書いてるけど、予選中は結構悩みました。