656.1
世間の人と価値観が違いすぎるのかも知れない。
250
N個のものからランダムに1個選ぶ操作を繰り返していく。前のよりもindexが後ろのを選んだら失敗で終了。このとき、選んだもののスコアの合計値の期待値を答えよ、という問題。
普通にメモ付き探索するだけ、だと思います。そしてそうでした。
500
1からNまでのpermutationのうち、指定された関係になっているものの個数を答えよ、という問題。
なっていないのを除去して回ればいいそうです。
1000
なんかN個のものを高さがばらつかないようにスタックしていって、最終的に一つのスタックにしたい。連続領域をまとめてスタックするしかできない。何回必要か、という問題。
普通に探索すれば良さそうな気もする。
655.1
適度にやる気なくしていたら、比較的いい問題がきた。
250
N*Nの盤面をK*Kの区画を塗る操作を延々と繰り返して、目的の塗り方にできるか答えよ、という問題。
とにかくK*Kの同じ色の区画があれば、そこをそう塗る前はどんな状態でもいいので、そんな感じで一つずつステップを戻していって、全体がどんな状態でも良くなったら終わり、というような感じ。
500
とあるM桁の整数をN回スキャンしたら、なんか読み落としがあったけれど、9で割った余りがどれも0だったらしく、そんな元の数字は何通りあるか答えよ、という問題。
とにかく、読み落としのパターンは2^N通りしかないので、それを適当にまとめて、9で割った余りを各試行ごとに覚えておいてDPやるだけ。
1050
見てない。
654.1
本当に飽きてしまった...。
250
文字列の一部が伏せられていて、特定の文字である確率が与えられる。部分文字列が全部同じ文字からなるものの個数の期待値を答えよ、という問題。
実装やるだけ。やっただけ。
450
整数配列が与えられるので、二つの連続領域の和の合計値の最大値を答えよ、という問題。ただし、整数配列はN回更新されるので、その都度答えよ、という問題。
いつものあれ。まじめにライブラリ作ろうかねぇ...。
850
木が与えられる。根を2個定義するので、葉から適当に順序付けする方法は何通りあるか答えよ、という問題。
組み合わせやるだけっぽくみえるが？多分大分面倒。
653.1
ちゃんとした問題が出ても解けない。
250
同じ数字がその数字の数だけ並んでいるのを結合して作られた整数配列がある。一部が伏せられているので、元の数列を復元できるか答えよ、という問題。
適当に探索して複数通りにならないのを確認すれば良さそう。探索なのでDPでもいける。打ち切りが結構早いので、探索の方がいいっぽいけれど、どうにもうまくいかず...。
450
整数配列を二人に分ける。同じ数字は同じ人がもらうようにするのと、一部は既に割り当てが終わっている。最終的に割り当てた結果、二人の人のものが並んでいる箇所を最小にしたいので、その個数を答えよ、という問題。
なんか適当に割り当てをグラフにしてやればいいそうです。考える気力がない。
900
見てない。
651.1
眠いので途中だけれど、メモして去ります。
250
縦横移動に相当する操作列を与えたときに、それぞれが無視される可能性がある状況で、盤面の外に出ないような最長操作列の長さを答えよ、という問題。
要は現在位置から盤面の外に出ない四方向のそれぞれの距離の合計値を求めてやればいいだけ。
500
6個のブロックをスライド移動してくっつけたいので、最終的な移動距離の合計の最小値を答えよ、という問題。
最初の位置は、x座標とy座標を独立に計算して、中央値付近になるはず。後は、順番にそこに近付けるような感じで配置していく。貪欲にくっつけるのがいいはず。順番を全パターン試してもたかが知れているし、くっつく場所を数パターン試してもたかが知れているはず。
1100
見てない。
650.1
純粋につまらないから人が減っている？悪循環ですかね？
250
AとBのどちらかからなる文字列の指定された位置がAかBか与えられるので、できるだけ同じ文字が連続しないようにするとき、何通りできるか答えよ、という問題。
取り敢えず、交互に並べるのが良いはずなので、指定された文字の間隔に適当に埋めていく。交互にするか、どこか一回だけ連続するか、のどっちかなので、後は適当に決めていけば良さそう。
500
木に3本枝を追加させたグラフかどうか答えよ、という問題。
本当にそうなら、大半のノードがランク1になるはずなので、葉っぱが決まるので、ある程度は決まりそうですね。
900
見てない。めんどくさいのの後に簡単なの置いて、順番逆にやるのが正解、みたいなセットはやめようよ、とは思う。なので、そうでないことを祈る。
