hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

蟻本練習問題解説 Part1 (2-1)

みなさんは、蟻本の「練習問題」を解いたことはありますか?本の中で掲載されている例題は見たことがあっても、練習問題までは手を出していない、という人はそれなりにいるのではないでしょうか (要出典)

というわけで、今日から不定期で蟻本の練習問題を解説していきます。学習の一助になってくれれば幸いです。わからないところがあれば Twitter などで気軽にきいてください。

英語の問題は簡単に和訳しています。分量が多いので何回かに分けてやっていきますが、なんとか完走したいです・・・!

シリーズ目次はこちらからどうぞ。

tsutaj.hatenablog.com

すべての基本 "全探索"

深さ優先探索

POJ 1979: Red and Black

問題リンク

問題概要については、AOJ に全く同じ問題が日本語で掲載されているので、そちらを参照してください。

▶表示する

POJ 3009: Curling 2.0

問題リンク

問題概要については、AOJ に全く同じ問題が日本語で掲載されているので、そちらを参照してください。

▶表示する

AOJ 0118: Property Distribution

問題リンク

概要は日本語なので省略します。

▶表示する

AOJ 0033: Ball

問題リンク

概要は日本語なので省略します。

▶表示する

幅優先探索

AOJ 0558: Cheese

問題リンク

概要は日本語なので省略します。

▶表示する

POJ 3669: Meteor Shower

問題リンク

隕石が  M 個落ちてくる。 i 番目の隕石は、座標  (X_{i}, Y_{i}) に時刻  T_{i} に落ち、落ちた直後からその座標とそれに隣接する 4 つの座標には立ち入ることができなくなる。あなたは最初に座標  (0, 0) におり、そこから単位時間あたり 1 マス分進んで安全な場所 (隕石による影響がない場所) まで移動したい。このようなことが可能であれば最短の時間を、不可能であれば -1 を出力せよ。

▶表示する

AOJ 0121: Seven Puzzle

問題リンク

概要は日本語なので省略します。

▶表示する

全列挙

POJ 2718: Smallest Difference

問題リンク

相異なる 10 進数の 1 桁の数字の集合が与えられる。この集合を 2 つの部分集合に分ける (空集合は許されない)。同じ集合に属する数字どうしを全て組み合わせて、数字を 1 つ作る。例えば集合が  \left\{ 0, 2, 5\right\} である場合、 250 502 などが作れる。ただし、leading zero は許されないため、  25 は作れない。このとき、それぞれの集合で作った 2 つの数字の差の絶対値の最小値を求めよ。

▶表示する

POJ 3187: Backward Digit Sums

問題リンク

長さ  N の順列が与えられる。1 行目にはその順列そのものを書き下す。2 行目以降は、前の行において隣接している要素同士を足しあわせたものを書き下すという操作を行う。この操作によって、最後の行は 1 つの数字からなる。順列の長さ  N と、最後の行に書かれた数字  K が与えられるので、順列を復元せよ。なお、答えが複数ある場合は、辞書順最小のものを出力せよ。

▶表示する

POJ 3050: Hopscotch

問題リンク

1 マスにつき数字 1 桁が書かれている  5 \times 5 のが盤面がある。適当な位置からスタートし、上下左右に移動して 6 桁の数字を作るとき、何種類の数字が作れるか?

▶表示する

AOJ 0525: Osenbei

問題リンク

概要は日本語なので省略します。

▶表示する

全探索できるかどうかは、あり得るパターン数がどれくらいあるのかをざっくりと計算すれば良いです。大まかな計算量の見積りができるようにしましょう。

次回は、貪欲法のトピックを扱っていきます。