1671. Anansi's Cobweb @ Timus Online Judge If we simulate it from the back instead, thinking the original edge destroying operation as adding, it will be possible to solve using elementary union find. #include <bits/stdc++.h> using namespace std; const i</bits/stdc++.h>…

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

今日は簡単な問題のデバッグに手間取ってた。時間を無駄にした感じがある。 周りの人は一部が IOI'15の Teamを解いてるようだ。永続化セグメント木とかを言ってる。 とりあえず、やる事が沢山ある今、今週にふさわしい、いい加減なやりたいリストを作るか • …

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

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の色のどれかが付いている。その中四つの隅で確定する長方形で、四つの隅の中に全ての色が付いてる選…

PEG Judge - IOI '15 - Boxes with Souvenirs 実はそんなに難しくない Greedy。まず、どういう操作があるか考えてみよう。 １、時計回りに動いて逆時計回りに戻る ２、１の真逆 ３、一周する １をする場合は半周を過ぎないのは簡単に見える（そうする必要が…

2019 -- Cornfields ふぁぁ、初めての二次元セグメント木AC。楽しかったです。でも僕はポインタの書き方にしかなれないから、メモリを静態に宣告しなければTLEしてしまいます。でもMAXMEMをちゃんと十分( RE )で多すぎない( MLE ) ように工夫するのは難しい…

1631 -- Bridging signals tozangezan.hatenablog.com tozangezanさんのブログでセグメント木の問題をたくさんもらいました、ありがとうございます。でもこれだけは。。。LISだけじゃないの？と自分を疑いながらとりあえずか書いてみました。ACしました。ま…

1744 - [APIO '09] ATM | TIOJ INFOR Online Judge 題意：給你 n ≤ 5e5 個節點，每個節點都有權重，有些節點是酒吧，接著給你 m ≤ 5e5 個有向邊。給你一個起點，求最後停在一個酒吧( 經過的酒吧可以不要理會 ) 的經過的節點權重總和最大值。同一個節點可以被…

School of Killifish | Aizu Online Judge 二次元セグメント木をやるだけ、だと聞きました。でも当たり前にMLEしました。O( n * ( lg ^ 2 ) n ) で n ≤ 1e6。諦めますが、初めての二次元セグメント木で、色々勉強になったので一応MLEしたコードでも載せます…

Problem - 101B - Codeforces dp[ i ][ t[ i ] ] = sum{ dp[ i - 1 ][ s[ i ] .. t[ i ] - 1 ] }, Ɐ i: current bus bus需要先依據終點 t做昇序排序。 注意因為區間範圍可能很大，所以需要離散化。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e9 + 9</bits/stdc++.h>…

Problem - 52C - Codeforces Tag のちょっとした練習になる。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int MAXM = 2e5 + 5; const int MAXABSV = 1e6 + 6; typedef long long ll; const ll INF = 1e16; int n; int a[ MAXN ]; int </bits/stdc++.h>…

House Moving | Aizu Online Judge JOI 11 Day4 Bookshelf ( DP + Segment Tree ) - 0w1 とほぼ同じ。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; #define int long long struct itvt{ int maxv; int lb, rb; itvt *lc, *rc; itvt(int _l = </bits/stdc++.h>…

競技プログラミングで陥りやすい言語仕様の罠 - 情報オリンピック 問題と解説 1. これはなんか使えそう。 2. もし intがどこにもあるコードに突然 long longが要求されたら、一番上の行に #define int long long はしたい。しかし、これだと main()が変なも…

Bookshelf(本棚) - joi2011-day4 - 情報オリンピック 問題と解説 bookshelf: 本棚 (Bookshelf) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 「この本を動かすかどうか」を直接決めるのはできなさそう。なのでDPを考えてみる。しかし「今の本を動かす」…

1063 - 最大矩形(Area) | TIOJ INFOR Online Judge 跟這題很像的，不過這次是要求矩形面積。 UVA 12265 Selling Land ( Stack Monotonicity ) - 0w1 很容易注意到，如果先發生的( 左邊開始的 )矩形比後發生的矩形高，那只要先發生的矩形好好的，後面發生的矩…

UVa Online Judge 白訓練指南的一道經典的單調棧好題。思路是先想像我們大致會做一個高度單調遞增的維護，注意到要判斷一個左上角到當前的右下角構成的矩形周長是否足夠優，只需要知道它的高和當前的列的差( 寬 )。由於只有寬是動態增加的，所以只要能不斷的…

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

PEG Judge - IOI '13 - Dreaming 題目大意是給一個森林，希望用任意數量的長度為L的邊將他黏成一棵樹，使得最後這棵樹的直徑最小，求的是這樣的直徑。 很容易想到，最理想的方法一定是將所有樹折半，以他的樹心( 該點對於樹上其他點的最長距離最小 ) 連結，…