Zig-Zag Numbers ■問題 2947や71946などの各桁が増加、減少、増加…およびその逆となってる数字をジグザグ数とする。 A以上B以下のMの倍数であるジグザグ数の個数を求めよ。 ■解法 制限が 1 A以上B以下はx以下のジグザグ数の個数をf(x)とすると、f(B) - f(A-1…

Cleaning Robot ■問題 部屋の盤面が与えられ、スタートからすべての汚れたマスを通るように移動するときの最小距離を求めろ。 ■解法 すべてのマスを通ってという巡回セールスマン問題のような問題だがスタートと各汚れとの距離は障害物があるため、先にBFSし…

方向音痴のトナカイ ■問題 教会と家の情報がn*mの盤面で与えられます。 トナカイは上下左右に直進しかできず、一度止まった家の上は通過できなくなります。 教会からスタートし、すべての家に訪れてまた教会に戻ってくるルートは何通りあるか求めよ。 ■解法 …

Gather the Maps! ■問題 n人の子孫がそれぞれ宝の地図の断片を１枚ずつ持っています。 n人の日程はわかり、その日が暇な人同士なら誰かにその断片を渡すことができます。 誰かがすべての断片を手にするまでの最小の日数を求めなさい。 ■解法 誰かの断片を別…

Traveling by Stagecoach ■問題 m個の街がp本の道路でつながれている。 道路を利用するには券が必要で、移動にかかる時間は距離/券の数字だけの時間が掛かる。 また、券は１枚につき１回しか使えません。 あなたはn枚の券を持っていて街aから街bに行きたい時…

Rearranging Seats ■問題 r*cあるものを、それぞれ上下左右に移動させたとき場所がかぶることなく全て移動できるかどうか求める。 ■解法 すべてを上下左右に移動できるかどうかは、ある一点から上下左右に移動し、他のすべての点を通って最初の点に戻ってこ…

Patisserie ■問題 幾つかの円を任意の順番で並べたとき必要な幅の最小が箱の幅より小さいかどうかを求める。 ■解法 dp[直前に度の円を使ったか][使った円の集合]で横幅を求めて、それがはこの大きさより小さいかを判定する。 2円の中点を繋ぐ線分はr1+r2、2…

Princess, a Cryptanalyst ■問題 入力されたすべての文字列を部分文字列として含む最小の長さの文字列SSSを求める。 複数あったら辞書順で小さいものにする。 ■解法 SSSの後ろの10文字と、使ったかどうかをビットで表現したやつを引数に持たせてDPする。 使…

Circles Intersection ■問題 2つの円の中点の座標と半径が与えられる。 1つの円がもう一つの円の中にあるか、円周が交わっているかいないかという2つの円の関係を求める。 ■解法 2つの中点との距離hを求めて、 Br+h>Ar だったら円Aの中にBがある。 Ar+h>Br …

Maximum Sum Sequence ■問題 整数nとn個の整数が与えられます。 その中の連続する値の合計の最大値を求めなさい。 ■解法 累積和を求めて連続の前と後ろをループで全通り試す。 ■ソース #include<cstdio> #include<algorithm> using namespace std; int d[5005]; int main(void){</algorithm></cstdio>…

Treasure Hunt ■問題 幾つかの移動歩数と回転角度が与えられます。 座標(0,0)地点で北向きに立っている状態から移動歩数分前に進み、回転角度分右に（負の値なら左）向きます。 それを入力が"0,0"になるまで続けた時の座標の整数部分を答えなさい。 ■解法 移…

Stray Twins ■問題 もう一方と上下左右反対に移動する双子がいます。 二人の座標とデパートの情報が与えられた時二人が巡り合えるまでの最短距離を求めなさい。 最短距離が100以上になるときは"NA"と出力しなさい。 ■解法 現在の距離、2人のx,y座標を持たせ…