JOI
IOI Manju | Aizu Online Judge なんか難しいものから逃げてばかりな感じで不安。。。 #include <bits/stdc++.h> using namespace std; const int MAXM = 1e4 + 4; const int MAXN = 500 + 2; const int MAXPCE = 1e4 + 4; const int INF = 0x3f3f3f3f; int m, n; int p[ MA</bits/stdc++.h>…
Treasures | Aizu Online Judge It's easy to see that we will have to split them into two equal size sets and update the answer for each set to set. Since there are three options for each item, we will have to enumerate all 3 ^ |s| possible …
Sandcastle | Aizu Online Judge 更新されたマスだけまたqueueに入れる。バグ取るのに手間取った。 #include <bits/stdc++.h> using namespace std; const int MAXH = 1e3 + 3; const int MAXW = 1e3 + 3; typedef pair<int, int> pii; const int dx[] = { 0, 1, 0, -1, -1, 1, -1, 1 </int,></bits/stdc++.h>…
Silk Road | Aizu Online Judge dp[ i ]: now on city i, minimum cost #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 3; const int MAXM = 1e3 + 3; const int MAXC = 1e3 + 3; const int MAXD = 1e3 + 3; const int INF = 0x3f3f3f3f; void upmi</bits/stdc++.h>…
Gifts | Aizu Online Judge kagamiz.hatenablog.com kagamizさんの記事見て分かりました、ありがとうございます。 重要な考察は、最大3歩しか戻れないという事は、6歩前までの状態としか関係ないという事だ。なので今までの最後の6歩の方向を記録します。…
Hot days | Aizu Online Judge dp[ i ][ j ]: After considering clothe for day i, which is of c_i = j, maximum value #include <bits/stdc++.h> using namespace std; const int MAXD = 200 + 2; const int MAXN = 200 + 2; const int MAXT = 60 + 6; const int MAXAB =</bits/stdc++.h>…
banner: 横断幕 (Banner) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 問題:h ≤ 400, w ≤ 400 の長方形が与えられる。全てのマスにはそれぞれ 0 ~ 2の色のどれかが付いている。その中四つの隅で確定する長方形で、四つの隅の中に全ての色が付いてる選…
Shopping in JOI Kingdom | Aizu Online Judge 店のある町からMSSPをして店のない町から一番近い店への最短経路を計算する。そうしたあと、答えは max{ round( dis[ i ] + dis[ j ] + weight[ i ][ j ] / 2 ) } Ɐ e( i, j ) ∈ E だとわかる。 #include <bits/stdc++.h> usin</bits/stdc++.h>…
Books | Aizu Online Judge ナップサックするだけ。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e3 + 3; const int MAXK = MAXN; const int MAXC = 1e5 + 5; const int MAXG = 10 + 2; void upmax(int &x, int v){ if( x < v ) x = v; } int n, k; i</bits/stdc++.h>…
Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …
Bug Party | Aizu Online Judge 很容易想到,如果固定最小值b,那麼我們必須由小到大拿進所有a,直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和,條件形式複雜,如果不加功夫用持久化線段樹亂搞…
Planetary Exploration | Aizu Online Judge なにも考えずに一番先に頭から出たのが二次元BIT。普通にprefix sumでもいけるけど、BITは応用が効くからこれで。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1000 + 3; const int MAXM = 1000 + 3; const</bits/stdc++.h>…
Night Market | Aizu Online Judge ナップサック問題に変換するまでは簡単に見破れるが、問題はどう実装するかだ。愚直に解こうとするとO( n ^ 2 * t )になってしまうので、セグメント木を使いました。実は左からと右からとそれぞれ1回ずつナップサックをす…
Card Game is Fun | Aizu Online Judge Aに対して全てのindexからすぐに次の数字にジャンプできる様にする、O( a ^ 2 )。そうするとBでどこから始めるのか枚挙し、いちいちどこまでいけるかをクエリしてもO( a * b )になる。 #include <bits/stdc++.h> using namespace std;</bits/stdc++.h>…
http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day2.pdf guess: 数当て (Guess Them All) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 首先可以用 O( N )把 1的位置給找出來,接著對其他每個數字分別做區間的二分搜,找出它的位置。例如要找…