解法 bitDP(の別解)で解きました. 下から見ていき、Iになっている場所と、直前がJでその下がIという状態を持つことでも解ける. JOが隣り合う状態を持つ方が状態数が少なくなるが, この解法でもO(n^2*2^n)なのでAOJでは間に合う. #include <iostream> #include <string> #includ</string></iostream>…

解法 音程の最小値と最大値の間は、単調にすべきである。(単調で無かったらswapしてよりよい状態にできる) 音程をソートして、最小値から考えることにする。常に、左が右に追加していけばよいが、実はgreedyでよいことが分かる。floor(スコアの和/L)の部分は…

問題 二人完全情報ゲームをする。 グラフが隣接行列で与えられる。交互に辺を追加していき、グラフを連結にしたほうの負けである。 解法 N( とりあえず、Union-Find木を用いて、既に連結になっている部分を調べる。 少し考察すると、(既に連結である部分の頂…

-n日目 予選 予選Aに出ました。 1日目 本選前 弁当があるので食べる。 本選 とりあえず、ABCDEを通し、Fを通す(デバッグに無限に時間を掛かっていたような気がしていたが、最初にsubmitしてから30分程度で通ってた) Fは円環を切った後、後ろに付け足すのを忘…

問題 http://main.edu.pl/en/archive/oi/11/zga 0と1の間の小数が9個来るから、小数が来る度に、全体の何番目か推測する。全部当たる確率をできるだけ大きくする。 解法 数学(確率(と組み合わせ)、積分)+DPで解いた。より具体的には、下に書いてあるようにし…

中央の','を見つけるのは簡単(左から見て、'('が一つ多い時に来る','が中央の',')なので、簡単な構文解析で解けます。get_i()とget_u()はほとんど同じだから、まとめても良さそう。 #include <iostream> #include <string> using namespace std; int center(string& s){ int co</string></iostream>…

k番目の値を求める。(クエリが複数ある場合は以下の方法では効率が悪い。(e.g. POJ 2104 k-th Number)) アルゴリズム ソート マージソート等の効率のよいソートの計算量はO(nlogn)であるから、O(logn)で求めることができる。 実装略 パーティションベースの…

250 周期がlcm(1,..10)なので2520分後までシミュレーションする。sleepyが減ったら必ず起きられる。 (自分のは実装が少しだけ違います。) int maxSleepiness( vector <int> p, vector <int> s, vector <int> v, int D ) { ll res = 0,t = 0; int n = p.size(); for(int i = </int></int></int>…

250 最初は、文字が1文字だけ書かれている。(クリップボードにはなにもコピーされていない) 書かれている文字を全てクリップボードにコピーする。 クリップボードに書かれている文字を貼り付ける。 1文字削除する。 の3つの操作を任意の順番で実行して、文字…

まずは去年の反省から PKU300問以上 solvedが18なんですがそれは... TCで黄色以上 いつの間にか黄色になっていました。 合格体験記 合格することが本質なので、達成したことにします。書き忘れていただけなのであとで書くかもしれません。 今年の目標 TC(SRM…