308.1

SRM

ICFPCが失格なので気分転換にSRMの過去問なぞ...。なのに実装問題とかいう悲しい状況...。

200

暗号化された文字列と曖昧ではない暗号化規則が与えられるので復元せよ、という問題。


単純に暗号化の辞書をなめるだけ。

500

ボードゲームをクリアするのに必要な最小ステップ数を答えよ、という問題。通れないマスと一つだけ飛び越えられるマスがある。自分のコマは四つあって、動かさないコマは飛び越えられるマスと同じ扱いになる。複数個飛び越えることはできない。


盤面は6x6なので状態を覚えつつBFSするだけ。コマの違いは識別できないので、左上から順にソートしておくと盤面数が小さく済む。(24倍くらいにはなるはずなので、計算量的にギリギリになるのかも？)