■
順調降下中。意外と落ちなかったので次もまだ黄色ラインかも。
250
三角形と四角形が適当に配置されている状況で、三角形を四角形に変換するという処理を行える回数が与えられる。このとき、三角形と四角形を組み合わせてできる最大の三角形の大きさを答えよ、という問題。できなければ-1を返す。(0にすればいいのに...。)
三角形の向きが決まっているので、可能な三角形は50^3通りしかないので、全部試してやれば良さそうな感じ。
500
NxMの盤面に1x1のブロックがいくつか置かれている。2x2のブロックは最大いくつ置けるか答えよ、という問題。
N=25でM=10だから2^10を覚えておいて次の2^10を更新するという作業を25回やれば終わりそうな気がする。
1000
N桁の整数のうち、4が4つ連続で並ばなくて、44の倍数桁でも444の倍数桁でも4444の倍数桁でも...でもないものを答えよ、という問題。
Nは4e11程度なので、気にすべきは44の倍数桁でも444の倍数桁でも44444の倍数桁でも4444444の倍数桁でもないもの。この包含関係をうまく処理しつつ、行列乗算使ってカウントするだけだと思う。行列は今4が連続している数を状態にしてやれば良さそう。先頭の0をどうやって処理しましょうかね、といったところ。行列が作れない症候群。