639.1
TopCoderってこんなにつまらなかったっけ？(出題センス的な意味で)
250
1,3,5,7,9,...を二人に分けたときの、合計値として正しいか答えよ、という問題。正しいときには、一人目はいくつの数字を割り当てられているか、その可能な最小値を答えよ、という問題。
残りが2にならないように、大きい方から割り当てていく問題。だそうです。これはとても難しい問題である。
500
白黒に塗られた紙を折っていく。折るときは同じ色が重なるようにしか折れない。折るときは小さい方から折らないとダメ。最後に残るマスの可能なパターンは何通りか答えよ、という問題。
縦と横が独立なので、それぞれ探索するだけだと思う。やるだけ。
1100
見てない
638.1
Adminは問題の難易度をもう少しまじめに把握した方が良いと思う。
300
N*N*Nの領域に1*1*1のキューブが適当に連結に詰んである。各方面から見たときに、見える見えないの情報が与えられるので、そんな積み方は可能か答えよ、という問題。
取り敢えず明らかにない場所を潰して、連結領域すべてについて、そういう見え方があるか調べるだけ。領域が分割されたりとかもあり得るので、注意が必要。
600
整数配列が与えられる。和がK以下のペアのみswap可能とするとき、最終的に可能な並び順は何通りか答えよ、という問題。
大きい順に移動可能かどうかで分割しても解けなくはない。小さい順に移動できる範囲を決めて、後は残りを計算、というのが正しいらしい。頭いいね。
800
木が与えられる。葉を適当に選ぶとき、葉から一番遠い点までの距離として可能なものは何通りあるか答えよ、という問題。
葉から葉までが一番遠いか、葉と葉の中間点が一番遠いかのいずれか。葉を全パターン試すのはさすがにムリなので、葉のペアを選らんで、それぞれについて、中間点か自分達かが一番遠くなるような葉の選び方が可能かを調べていく。(多分求めるのが可能な距離のパターンなので、こういうのでもうまく行く気がする。)
637.1
実装大変な問題。
250
1から2Nまでの整数をN個ずつ二人に分ける。自分の持っている整数が分かっていて、相手がどういう風に並べているかも部分的に分かる。自分の持ってる整数を並び替えて、相手の並べている整数と順番に比較して、大きくなる回数をできるだけ多くしたい。その期待値を求めよ、という問題。
要は相手の分かっている数字に、それよりも大きい数を置いて、大きいのなければ手持ちの一番小さいのを割り当てて、みたいにした上で、後はランダムに期待値計算するだけ。
500
2*Nの盤面に白または黒の色が塗られている。任煮の白いマスを黒に塗るという操作を交互にして、左端から右端までを白いマスだけの遷移で移動できなくした方が負け、というゲームをするとき、先手必勝か答えよ、という問題。
真ん中付近では、黒く塗れるマスの偶奇は変えられない(塗りにくくしようとすると両隣に影響が出る)ので、結局両端をどうするか、になる気がする。なので適当に判定してやれば長さによらず終わるような気がする。
1000
見てない。
636.1
500が解けるか解けないか。
250
2次元テーブルに整数値が入っているので、矩形領域の和を高速に求める下準備をしなさい、という問題。
やるだけ。コピペの人が多いんだろうな。
500
二次元平面上に、ランダムにK個の点を配置して、一番近い点同士に辺をはって無向グラフを作る。強連結成分の個数の期待値を求めよ、という問題。
知らない。
1000
1からNまでの整数が一度ずつ使われて構成される整数配列のうち、いくつかが伏せられている。任意の2個を選んだときに、並び順が正しい箇所の個数が与えられるので、元の整数配列として正しいものの個数を答えよ、という問題。
全探索は当然のごとくTLEするので、こういうときは半分ずつに分けて頑張ると良いらしい。なるほどね。そこから先は実装ゲーなので、気付いた人には実装ゲー。気付かない人もTLE確定の全探索までは実装ゲー。
