0w1

JOI

JOI 13 本選 IOI Manju ( DP )

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

JOI 14 予選 Treasures ( MLE Discretized Segment Tree )

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 …

JOI 14 予選 Sandcastle ( BFS )

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

JOI 14 予選 Silk Road ( DP )

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

JOI 12 本選 Gifts ( DP )

Gifts | Aizu Online Judge kagamiz.hatenablog.com kagamizさんの記事見て分かりました、ありがとうございます。 重要な考察は、最大3歩しか戻れないという事は、6歩前までの状態としか関係ないという事だ。なので今までの最後の6歩の方向を記録します。…

JOI 12 本選 Hot days ( DP )

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

JOI 11 Day1 Banner ( DP )

banner: 横断幕 (Banner) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 問題:h ≤ 400, w ≤ 400 の長方形が与えられる。全てのマスにはそれぞれ 0 ~ 2の色のどれかが付いている。その中四つの隅で確定する長方形で、四つの隅の中に全ての色が付いてる選…

JOI 10 本選 Shopping in JOI Kingdom ( Dijkstra )

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

JOI 10 本選 Books ( DP )

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

JOI 11 本選 Festivals in JOI Kingdom ( MSSP Dijkstra + Kruskal + Doubling LCA )

Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …

JOI 10 本選 Bug Party ( Binary Search + MLE Persistent Segment Tree / AC Priority Queue )

Bug Party | Aizu Online Judge 很容易想到,如果固定最小值b,那麼我們必須由小到大拿進所有a,直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和,條件形式複雜,如果不加功夫用持久化線段樹亂搞…

JOI 10 本選 Planetary Exploration ( 二次元BIT )

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

JOI 11 本選 Night Market ( 区間DP )

Night Market | Aizu Online Judge ナップサック問題に変換するまでは簡単に見破れるが、問題はどう実装するかだ。愚直に解こうとするとO( n ^ 2 * t )になってしまうので、セグメント木を使いました。実は左からと右からとそれぞれ1回ずつナップサックをす…

JOI 11 本選 Card Game is Fun ( Adhoc )

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

JOI 2011 春合宿 Guess Them All ( Binary Search, Interaction )

http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day2.pdf guess: 数当て (Guess Them All) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 首先可以用 O( N )把 1的位置給找出來,接著對其他每個數字分別做區間的二分搜,找出它的位置。例如要找…