473.1

難易度が大分低下した感じのセット。

250

直進、向きを変える(左右)、という命令の列が与えられる。このシーケンスを延々と繰り返すとき、無限に遠くまで行くかどうかを答えよ、という問題。

取り敢えず一つのシーケンスが終わったときに、同じ向きのままで初期位置と違う場所にいる場合だけ無限遠まで行く。向きが変わる場合は、90度だったら4回で、180度だったら2回でループする。

500

円上に等間隔にある点からいくつかを規則的に選んで赤く塗る。このとき赤い点三つを選んでできる三角形が直角三角形であるものは何通りか答えよ、という問題。

一辺が円の直径になっていれば他の点をどう選んでも直角三角形になるので、すべての赤い点について円の反対側にある点が赤いか調べ、残りの点の数を加算していくだけ。

1000

チェスのルークに相当するものが数色ある。違う色のルークにとられる位置にならないように、並べるとき、何通りの並べ方が可能か答えよ、という問題。

それぞれの色に対して矩形を割り当てる問題であり、矩形を割り当てたときにその中に何通りの配置ができるかを考える。このとき使っていない行や列があってはいけない。これは、N*Mの矩形の中にK個入れる方法は、N+MからK個選ぶものから、N-1*M,N-2*M,...,N*1,...,1*1の矩形の中にK個入れる方法をすべて引いたものになる。後は単純にメモ付き探索を使って、最初のいくつの色に対して盤面のどれだけを割り当て済みか、というのを状態にして調べるだけ。