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

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

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

MooFest ■問題 直線上にいるN匹の牛の聴力と座標が与えられる。 異なる2匹の牛の座標の差の絶対値と聴力の大きい方を掛けたものをすべての組み合わせに対して求めその総和を出力せよ。 ■解法 すべての組み合わせを試す際、聴力に対して昇順ソートすることで…