356.1

double誤差を意図している感じの悪さを除けば、比較的良いセット。

250

0点から10点までの1点刻みの点数で答えるアンケートを行ったときの、各質問における点数の平均値が小数点以下4桁目以降を切り捨てる書式で与えられるので、何人にアンケートを行ったか答えよ、という問題。

取り敢えず1000人以内であることは分かっているので、全部試せば良い。試すときに、まず総合得点が何点であったかを、試している人数をかけて、1000で割って(端数があれば+1)調べる。この人数から逆に何‰になるか確認して、一致するかどうかをチェックする。doubleでやると誤差が出る可能性が大きいので、整数でやると安心、という問題。

550

男女のグループがあり、男性1対女性1以上または、男性1以上対女性1のグループに分割することを考える。一緒のグループになって良いかどうかのフラグが与えられるので、最低何グループに分割することになるか答えよ、という問題。

まず、誰ともグループになりたくない人がいる場合、これは答えがないので無視する。グループの筆頭(複数の異性と同じグループになる側の人)となる男性女性の組み合わせについて全部試す。これは2の人数乗通り。人数は24人までなので、問題ない。これらの人のいずれかとペアになりたいことを他の人について確認し、全員がどこかしらのグループに入るようなことができれば、筆頭の人の数だけグループができる。

このときにできるグループ分けは解として適切でないものも含んでいるが、筆頭の人とグループになる人全員が筆頭の人である(誰ともグループにならない状況は除去済み)状況なので、そのうち誰かのグループに入れてもらえば良い。これはグループの数を小さくする処理であると同時に、そのようなグループは別途探索されるはずなので問題ない。

950

迷路をランダムに歩いてゴールまでいくことを考える。移動回数の期待値を答えよ、という問題。

ライブラリゲー。一度はやっておきましょう。

現在位置からかかる期待値は、隣接マスの期待値の平均値(ランダム移動なので)に(隣接マスへの移動コストである)1を加えたもの。これをすべてのマスについて立式すると、タダの連立一次方程式になるので、ガウスの掃き出し法なりなんなりで答えを求めるだけ。ゴール出来ない場所がいくらかあるので、ランクが足りなくならないように注意。(使う値はスタートのところの値だけなので、適当にx=0のような式を入れておいて問題ない。)