649.1
思考に椅子が必要なのかな？とは思っています。
250
指定された文字列から、任意のK文字を除去したときの結果がユニークになるか答えよ、という問題。
連続するK+1文字の中に同じ文字が2個以上あればダメ、という風に置き換わる。後はやるだけ。
550
整数配列が与えられるので、適当な数字をXORして、各要素について大きい順に並んでいるペアの個数を最大化せよ、という問題。
上位ビットから決めていく。上位ビットが同じグループの中では、次のビットをどうするかで大小が決まる。グループを並行に走査できればなんでもいいらしい。グループの数を覚えておこうとすると結構大変。要素数が少ないので、グループ自体がスパースになるのを使えば、グループ自体を全部把握しておくことができるらしい。ふ〜ん...。
850
見てない。
648.1
実装大変でしたね。
250
AとBからなる文字列のうち、文字数がNで、Aの後にBがくるというインデックスの組がK個の文字列を答えよ、という問題。
愚直に探索するのがいいと思うけれど、まずはAとBが半分ずつある文字列を作って、適当に隣接するA,Bをスワップしていくと良いらしい。余り確信が持てない...。
550
i番目のものの値段が買うたびに変動していって、i*2^jみたいになる商品があるので、安い順にK個買うときのK番目の値段を答えよ、という問題。ただし、iにも上限は一応ある。
取り敢えず、K以上になるのはどの商品か知らないけれど、1番目の商品を何個以上買う必要があるかを決める。そうすると、2番目の商品はそれよりも一個少なくしか買えない。3番目の商品はその時点では2個少ないけれど、それを1個少なく頑張るとしたらどうなるかを考える。もしそれでも足りないなら7番目の商品を増やす方向で頑張るし、そうでなければ5番目の商品を増やす方向で頑張る。みたいな感じで、何番目の商品が次に安いのかがなんとなく分かるので、頑張って探索しましょう、実装しましょう、という問題。問題自体は簡単だけれど、他人に説明するのが面倒。
要は、取り敢えず二進数で100...0の値段の商品を買うと個数が明らかにオーバーするけれど、一桁少ないと足りない、みたいなので桁数を固定して、後は上位ビットから順に0か1かを決めていくような感じでやれば良い。実装が大変、面倒です。
850
見てない。
647.1
本当に最近つまらないのでやめたい。でもやめると二度とやらない気がするので、義務として続けている感じ。
250
初期値が0で各ステップで高々1だけ値を変更して良い。指定されたステップでの値が指定された値以下になるように注意しつつ、Nステップ操作を繰り返すとき、途中経過を含めて可能な最高の値を答えよ、という問題。
各ステップごとに、他の制約すべてを満たしつつ可能な最大値を計算してやればいいらしい。
500
問題を理解していなかったらしい。
コストと性能が与えられるので、総コストが指定された以下になるその部分集合について、とあるルールで合算した性能の合計値を最大化せよ、という問題。
950
見てない。
646.1
配点詐欺。問題は簡単なのにそれが解けない原因は明らかに自分が劣化しているからだとは思う。
250
整数配列が与えられるので、適当に増減させて連続なK個の整数を作るとき、何回増減させる必要があるか答えよ、という問題。
取り敢えずどこか一個固定して、そこに集めていく感じでやるだけ。
1000
残り2試合ずつ残っているNチームの現在のポイントが与えられるので、最終的に可能な順位のうち最高のものを答えよ、という問題。
なんか、めんどくさいやるだけ問題。適当に状況別に分類して、組み合わせてやるだけ。自分は勝つ前提で、ポイント入っても関係ないところには極力勝たせ、それ以外のところは負けさせた上で、ドローなどでポイントを削っていく。同じチームが対戦しないようにだけ注意が必要。
645.1
前回はなかった。
250
区間が与えられて、隣接グラフができるので、それの最小点被覆問題のような気がする。
要は開始と終了があるので、接しているどれか一つを選ぶと接しているのも選ばれたことになるから、全体を選ぶように最小に選ぼうという問題。
区間なので、終わりの小さい順に、できるだけ遠くまで行ける範囲は選択済みにして、使用済みのも使いつつ、がんばればいいだけらしい。適当なDPをがんばっても通るとは思う。
500
点集合を指定された点のいくつかのうちの一つと点対称に移動するという操作を延々と繰り返して、目的の状態にできるか答えよ、という問題。
どうやら点集合の操作の回数の偶奇が同じなら相対位置は変わらないらしい。(回転操作だから当たり前っぽい。)で、ある点に注目したときに、移動できる点の集合は、点対称の中心へのベクトルの二倍の任意の組み合わせで決まる。問題はそれぞれについて移動回数の偶奇が分からない(考えていない)ことと、目的の点に移動できるか考えていないこと。
取り敢えず最初の点を決めて、全部の点を対象に偶数回で移動できるか奇数回で移動できるか調べて、後は他の点を相対位置から算出してやって、全部の点とマッチするのがあるか調べれば良さそう。
900
見てないけれど、素直な問題だったらしい。良く知らない。
643.1
貪欲に貪欲を出し続ける出題者...。
250
でかい素数が与えられて、部分的に素因数分解の結果が与えられるので、残りを復元せよ、という問題。
部分的に分かっているので割ってから、素因数分解するだけでいいらしい。やたらと大きい数が出てくる場合に、どこで打ち切るか、という問題。
500
2色に塗られている2*Nの盤面があって、1*MまたはM*1の領域をコピーしていく操作で、全部を同じ色にしたい。何回必要か答えよ、という問題。
取り敢えず1*Mの操作に注目したいので、上下同じ色のは無視する。で、上下が互い違いになっている回数を適当に数えて、上下を同じにする。後は横方向はどうやってもM*1でしか変化させられないので、塗りたい数だけ必要になる。
1050
なんか面倒な確率の問題。
いくつかの計算過程をメモするというのを何段階かに分けて適当に高速化しつつ、独立事象なので最後に足し合わせれば期待値になる、とかそういう感じじゃないの？
642.1
問題が枯渇しているからつまらないのかも知れないけれど、今日のは出題者の悪意しか感じない。
250
N個のものを確率に従って抽選するという操作を延々と繰り返す。抽選結果に応じて、次の抽選までの時間が決まる。抽選を開始した時刻から経過した時刻が与えられるので、次の抽選までの時間の期待値を求めよ、という問題。
確率はDPやるだけ。基本どおりですね。
500
木がN本ある。特定の高さ以上の木を特定の高さにする機械がM個ある。木の成長具合と日数が与えられるので、最終的に木の高さの合計値の最小値を答えよ、という問題。
状態が多すぎるので、マッチングしてはダメ。のはずなのだけれど、問題サイズが中途半端なので、多分頑張れば持っているライブラリと言語によっては通る。最終日の状態とそれまでの成長具合を適当にソートしたりとかして、うまいこと最小化すれば良いらしい。でもこれだと応用きかないので、やっぱりフローで解いた方がいいような気がする。
800
見てない。
