kyuridenamidaのブログスマートフォン用の表示で見るkyuridenamidaのブログこの広告は、90日以上更新していないブログに表示しています。029最近言語能力がかなり低下している自覚があるので、物を書いて感覚を取り戻そうと思います。Cを解いて304位でした。Bでハマりまくった上にDを誤読してしまい、めちゃくちゃでした。レーティングは下がるし悲しい。二回連続でAGCひどい順位取ってる気がする。B->Wの順で隣接するオセロの色を反転させることを繰り返すとき、最大で何回操作ができるか。最大というのは実は無視できる。どんな順番で反転させても回数は変わらない。あるような組の数に等しくて、これは転倒数そのもの。N)のものを使っても良いがそれは明らかに牛刀なので、値が2種類なことを利用してO(N)で解くと良い。具体的には、転倒数は普通に左から配列を舐めて、'W'が現れたときにそれまでに現れた'B'の数を足して上げる。N(≦2*105)コの要素が与えられる。各要素は1以上109以下の整数である。要素X,Yの和が2べきのときだけその要素同士のペアを作れる。同じ要素が複数のペアに使われないようにペアを作るとき、作れるペアの数はいくつか。本番では重複する数を一つにまとめてから、ペアが作れるかどうかでグラフを作るとそれは森になることを利用して解いた。基本的には、葉の要素から貪欲に親とマッチさせていくことで最大のペア数が達成できる。2べき要素(1,2,4,8,...)については、同じ数同士でマッチさせるという追加の選択肢があるので困る。2べき要素を根とした木を考えると、その選択肢について最後に考えても良いことが分かる。従って、この木で普通に葉から貪欲して、最後にその2べき要素が2つ以上余ったらそれらをペアにする。二つの異なる2べき要素は1つの木に含まれないことを確認したいが、これは2で割る回数が一致していないとペアに出来ないことから問題ない。実際はグラフとかを意識しなくて良い方法があり、ソートして最大要素から貪欲にペアを作っていけば良かったらしい...作れるペアを列挙するパートと、それを実際に使うか使わないか決めるパートを分けて考えることにする。X≦Yとなるペア(X,Y)だけを考えても一般性を損なわないので、それを全て列挙することを考える。実は、各数に対してペアとして考える数は1つ(2べきを達成する最小の正整数)で、それで全てのペアを列挙できる。なんで1つを考慮するだけでいいかを説明する。2Y)を考えるとすると、選び方からX≦Yなので(X,Y)はペアになりうる。Yとなってしまうため、考えなくて良い。Yが大きい順にペア(X,Y)を使うか使わないか決定していくと最大数が求まる。使えるなら必ず使って損はない。いうのは以下の理由に基づく。使わなかったらそのYは未来永劫使われないので損をする可能性がある。使うとして、Xを含む別のペア(X,Z)を作るのを妨げてしまう可能性はあるが、それによる損失は高々1つの別のペア(X,Z)が作れなくなるだけなので、少なくとも損はしない。文字列{Si}がN(≦2*105)コある。Snという関係が成り立っている。i番目の文字列の長さAiのみを知っているとき、文字列に使われる文字の種類数として最小としてあり得るのは何か。シミュレーション文字の種類数の最小は、二分探索で見つけます。Snが存在するかどうかを判定すれば良い。存在するかどうかを判定するのはシミュレーションを用いれば良い。できるだけ辞書順で小さい文字列を貪欲に割り当てて行けば良い。これは以下のアルゴリズムで行える。n-1}と表すことにする。明らかに、S_1は0をA_1コ繰り返したものを考えれば良い。対してどうするか考える。とき、S_iをS{i-1}の末尾に0を必要数足したものにすれば良い。とき、S_iから必要数末尾を削った後、末尾の文字を一つアルファベット順で大きいものにしてあげればよい。その文字がアルファベット順で最大なときは、繰り上がりが発生するのでそれをシミュレーションする。このシミュレーションは連長圧縮をしておくことで文字種類数が2以上のときは愚直にやっても高速に動作する。N)桁くらいしか繰り上がりの影響を受けないため。繰り上がりに失敗して長さA_iが達成できなくなったらシミュレーションは失敗、そうでなければ成功となる。Anのときかつそのときに限り達成できる。日本国内予選お久しぶりです。ブログ書く習慣を忘れて7~8ヶ月くらい経っ...2012-11-11PCK本戦2012最後のPCKでした。結論から言うと4位/32ちーむでした。負けまし...2012-03-03CTPCお疲れ様でした。参加ありがとうございました。月別アーカイブ参加グループプログラミングはてなブログをはじめよう!kyuridenamidaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。