問題 を満たすx, y, v を求める 解法 maxの項が存在しない場合は、各軸で考えて、中央値を選べば良く、Nが偶数のときは、中央の2つの値の間の値であればどれでもよい。Nが奇数のときは一意に定まる。 maxの項が存在する場合の解は、上の問題の解のどれかであ…

解法 固有値が2の時の固有ベクトルを求めて、適当にグラフを作ると、後ろから辿ることで状態を復元できる #include <iostream> #include <string> #include <map> #include <algorithm> using namespace std; typedef pair<char, int> State; map<pair<State, int>, State> f; map<pair<State, char>, pair<State, int> > g; #define M 9 int deg[M] = {3, </state,></pair<state,></pair<state,></char,></algorithm></map></string></iostream>…

LPであることと、フローっぽいことはなんとなく分かるけど、最小費用流のLP双対の形にするのが少し難しいので、1100妥当だと思う。 解法 最小費用流の双対なので、変形してから流す。 ネットワークが少し特殊な形をしてるけど、蟻本とかで調べるとやり方が書…

解法 木のサイズに関する自明な枝刈りをすると計算量が落ちるから、頑張って実装する。 木を作ったり判定したりするのが大変なので工夫すると比較的楽に実装できる。 判定するときは、queueを3つくらい使うと綺麗に実装できる。 #include <iostream> #include <string> #includ</string></iostream>…

解法 包除原理+DP包除原理に気づかずbitDPしようとしたら複雑すぎて無理だった(解説スライド見ても解けるとしか書いてなかった) あと、解説スライド見ると包除原理だけで良いらしい(ちょっと読んでもよく分からなかった) #include <cstdio> #include <cstring> #include <algorithm> #inc</algorithm></cstring></cstdio>…

競プロで解いた問題が最近1000問を超えたみたいですが、未だに苦手が大量にあるので。 知らない or 実装したことがない or 苦手 実装 あまりできるようにならない 幾何 全部 DP 本質的に難しい問題が多い 木 Segment Tree 遅延 永続 SttarySkyTree 2D 平衡二…

解法 cuteでソートするとDPできて、cuteの最大値が定数で、dp[鍋の種類][重さ] := max{cuteの最小値}となるようなテーブルがO(NW)で作れる。 できたテーブルは尺取法でO(W)で走査できる。全体で、O(NW) #include <iostream> #include <algorithm> #include <map> #include <cstring> using names</cstring></map></algorithm></iostream>…

解法 dp[index][分割する個数] := min{右端に来る数} とするとO(N^3)でDPできるが、これでは間に合わないので、工夫して dp[index][右端に来る数] := max{分割する個数} として、j #include <iostream> #include <cstdio> #include <vector> #include <map> #include <algorithm> using namespace std; </algorithm></map></vector></cstdio></iostream>…

考察要素が大きく、実装パートも面白いので良問だと思う。 解法 完全グラフK_nのときは、自明 そうでないとき、他の全ての点と接続しているような点が存在しているから、その点を取り除く。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef lon</vector></algorithm></cstdio>…

解法 sort+累積和+setで解こうとするとsetのメモリの定数倍が大きくMLEするので、 尺取法みたいな感じ(？)で次数を1つずつ順に見ながら、最小カットを考えるとO(n)で解けて、メモリも足りる。 #include <iostream> using namespace std; typedef long ll; #define N 25</iostream>…

解法 想定解は、後ろからUnionFindらしい。賢い。この問題は(実装が重くなるが)平方分割でも解けて、 MクエリがB回来るたびにO(N)で全部の頂点を更新すると、Qクエリをダブリングを用いてO(BlogN)で処理でき、全体でO(Q*(N+BlogN))となるので B = √(NlogN)程…

解法 SRM607Med CombinationLockDiv1と同じように考えると、直ぐ解ける。 まず、to - from を計算して、回転数を求めて、差分を求めることができる。 「(複数の)ダイアルを1回回す」 ⇔ 「差分を任意に2つ選び、それぞれ +x, -x する」 であるから、差分を総…

解法 直近の順列に着目して、DPする #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; #define chmax(X,Y) X=max(X,Y) #define N 200 map<vector<int>, int> dp[N]; int main(){ int n; cin>>n; vector<int> d(n), a(n); for(int i = 0; i < n; i++) cin>>d[i];</int></vector<int></algorithm></map></vector></iostream>…

良問 解法 nが3^*のときは解を二分探索すると解けるから、ダミーの貴族を追加する。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 401000 int d1[N], p[N], d2[N], d[N], s[N]; int n, m, n2; int rest, off, lm; int rec(int l, int r){ </algorithm></cstring></cstdio>…

解法 できるだけ状態をまとめるようにして、場合分けする。 n=1のコーナーケースはm=1のケースに帰着できる。 正しいコード(下のと同じ)http://ideone.com/gFCDZv 場合分けしすぎてTLEするコードhttp://ideone.com/s13jcw #include <iostream> #include <algorithm> #include <cstring> usi</cstring></algorithm></iostream>…

Easy 綺麗にかけた (自画自賛) #define N 200 int d[N]; class YetAnotherCardGame { public: int maxCards( vector <int> a, vector <int> b ) { int n = a.size(); sort(a.rbegin(), a.rend()); sort(b.rbegin(), b.rend()); vector<int> c(2*n); for(int i = 0; i < n; i</int></int></int>…

解法 基本的にはさほど難しくない考察をひたすら続けるだけなので省略.Wikipediaやuwicoderを見ながら考察する. ただし、(1+q+q^2+...+q^*)の周期はpより大きくなることがあることに注意する. 再帰するとスタックオーバーフローでREが出るので、TopCoderのス…

Person responsible for problem description don't w 解法 grundy数のベクトルで考える. ある頂点 u から出る辺が存在しないとき r(u) := 0 と定義し, u の子が存在するとき, r[u] := 「r(uの子の集合) に含まれない最小の自然数」 として, grundy数のベク…

Easy 最大値は(N/2)*((N+1)/2) Aを最初にN/2個並べておいて、Bをできるだけ右側に置いていけば良い int b[100]; class AB { public: string createString( int N, int K ) { memset(b, 0, sizeof(b)); string res = ""; for(int i = 0; i < (N+1)/2; i++){ i…

問題 となるようなA, Bの組の個数を1,000,000,007で割ったものを求める. (A, Bの条件については問題文参照) 解法 まず にを代入し整理すると、となる. を求めれば良い. ただし、 は N次元ベクトルで、 で、置換の大きさは同じであるとする. 置換の大きさは、…

解法 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…