■
ARC038-C 茶碗と豆 -Segment Tree上の二分探索-
才能がないね。悔しい
https://beta.atcoder.jp/contests/arc038/tasks/arc038_c
100点解法
grundy数を使い、遷移は i - C[i] ~ i - 1だけ注目すればOK
104点解法
高速化すべきは遷移にO(N)かかる部分である
ここでseg[i]を「grundy数がiである茶碗の番号の最大値」とする
そして、†Segment Tree上の二分探索†を行う
わけがわからないので、概略を言うと
seg[k * 2 + 1]とseg[k * 2 + 2]の値を見て、深く進んでいく
というイメージです(は？)
seg[i]を求めたいとします
grundy数は[0,N)の中にあるので順番に絞っていきます
もしこのようなgrundy数が[0,N / 2)の範囲にあるとすれば,どのような条件を満たすでしょうか
それは
[0,N / 2)の範囲でのseg最小値がi-C[i]より小さい
です
grundy数の求め方を考えると、範囲に無い数で最も小さい数がgrundy数になるので、この条件になります
これを繰り返し,l + 1 == r を満たしたら終了です
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) vector<int> grundy; struct Segment{ vector<int> node; int n = 1; Segment(int sz){ while(n < sz) n <<= 1; node.resize(n * 2 - 1,-1); } void update(int i,int x){ i += n - 1; node[i] = x; while(i > 0){ i = (i - 1) / 2; node[i] = min(node[i * 2 + 1],node[i * 2 + 2]); } } int get(int limit,int k = 0,int l = 0,int r = -1){ if(r == -1) r = n; if(l + 1 == r) return l; if(node[2 * k + 1] < limit){ return get(limit,2 * k + 1,l,(l + r) / 2); } return get(limit,2 * k + 2,(l + r) / 2,r); } }; int N; vector<int> C; vector<int> A; int main(){ cin >> N; C.resize(N); A.resize(N); rep(i,1,N - 1){ cin >> C[i] >> A[i]; } int gs = 0; Segment seg(N + 10); seg.update(0,0); rep(i,1,N - 1){ int ok = seg.get(i - C[i]); if(A[i] & 1) gs ^= ok; seg.update(ok,i); } if(gs == 0){ cout << "Second" << endl; } else{ cout << "First" << endl; } }
ほかの例題があったら練習したいねこれ
AtCoder青色になるまでにやったこと
ありがとうございます ありがとうございます ありがとうございます
水色から青色になるまでにやったことメインで書きたいと思います
緑後半、水色前半の方に届いたらいいなーという気持ちです
終始適当なテンションなのでご了承下さい
絶望のJOI本選
100点台....ここで自分の無力さ、努力のしなさ、ゴミであることを知りました(無知の知)
このころからTwitterが病んできます
700点が解けなくなって風呂場で泣いてしまった
— おもちもちもちくちもちとくら (@Kutimoti_T) February 18, 2018
春休みの精進
一週間で約100ACを生やす精進生活を送っていました()
AtCoderで精進するのも良いですが、CodeForcesやICPCにも手を出しました
ライブラリ作成
すごくいい経験になります(C++が書けるようになる)
GitHubのいい練習です(これは嘘でpushしかしない)
どんなお気持ちで精進していたか
精進し始めは、コーディング力も何もかも足りない状態だった(緑、水色前半とか抱えてるかもしれない問題)ので、克服するべく、ABC-C,D,ARC-Bを埋めました
実装力も付いてきたところで、典型力のNASAを感じるようになりました
ここでCodeforcesに手を出します
すごくお勉強になります(問題を理解すると簡潔な問題になる＝典型的な考察,テクの必要性)
ICPCにも取り掛かりました(実装問題は捨てて、考察問題を解きました)
何回も「考察を意識して」繰り返してくるうちに、考察力も付いてきて、AGCが解けるようになってきました(個人差、経験で頭を磨いた感じ)
そのうちに青になることが出来ました
正直、僕は周りに比べて「天才」じゃなかった
(ポエム要素)
僕のFFには「青になるまでに特にしたことが無いから記事書けねぇ」とか、「青は通過点」みたいな人がいて、そういう人が青になるのかと感じてはいました
正直、そういう人たちを見て悔しかったし、何回も病みました.
週末のARCの結果が悪いと、一週間病みっきりです()
「あーなんで解けるんだろう...」
そのたびに憧れて努力をし続けようと思い、今に至る感じです(要は嫉妬で強くなった)
まあ、「努力の量で実力が変わるなんて思うな」ってエアリプが来た時は正直萎えましたが((((
人から否定されても、それが未確定要素ならそれを自分で確かめたほうがいいです(親にPCの前で座っているだけとか言われても気にするんじゃないぞ)
これから
codeforces詰める
区間DPを勉強してみた
精進してるとやっぱり出てきた区間DP...
避けてきたけど、今回は少しコツをつかもうと思って勉強してみました
What's 区間DP?
....
は？
訳がわからんから取り敢えず問題解いてみよう
だるま落としぃ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp
どのようにブロックの対を取り出せばいいのか....っていうところなんですが...
まずはdpの保持する値を決めてしまいましょう
dp[l][r] := 区間[l , r)で取り除くことのできるブロックの数
どのように求めるか
２つパターンがあって、今見ている区間を[l,r)とすると
1.lのブロックとr - 1のブロックが対になれる
2.[l,mid) , [mid , r)に区間を分ける
1.が満たすのはどういう状況か...
それは
・w[l]とw[r - 1]の差が1
・[l + 1,r - 1)が完全に取り除ける
-> dp[l + 1][r - 1] が r - l - 2
という条件にあたりますね
[l] [......] [r]
という配置のとき
[......]
が弾き出すことができて,かつ
[l][r]
をはじき出せるかということになります
2.を考えると
//左側で取り除けた量 + 右側で取り除けた量
dp[l][r] = dp[l][mid] + dp[mid][r]
というふうに出来ます
これをDPすればできちゃいそう！
どうやって書こう
再帰で書く方法と,ボトムアップ(for文だけのやつ)で書く方法,
どちらもありますが、再帰で書いたほうがわかりやすいかも(個人差)
int rec(int l,int r){ //既に計算済み？ if(dp[l][r] != -1) return dp[l][r]; //これ以上取り除けない？ if(abs(l - r) <= 1) return 0; int res = 0; //パターン1. if(abs(w[l] - w[r - 1]) <= 1 && rec(l + 1,r - 1) == r - l - 2) { //[l , r)がはじき出せるので res = r - l; } //パターン２.区間を分ける for(int mid = l + 1;mid <= r - 1;mid++) { res = max(res , rec(l,mid) + rec(mid,r)); } return dp[l][r] = res; };
こんな感じ
あとはrec(0,n)で求められるね
ひゃい
ボトムアップはこんな感じです
for(int W = 2;W <= n;W++) { //left for(int l = 0;l < n;l++) { int r = l + W; if(r > n) continue; if(dp[l + 1][r - 1] == W - 2 && abs(w[l] - w[r - 1]) <= 1) dp[l][r] = W; for(int mid = l;mid <= r;mid++) { dp[l][r] = max(dp[l][r] , dp[l][mid] + dp[mid][r]); } } }
幅を広げていくイメージです
コツ？？
結局、遷移が大事だったね(ア)
どのように小さな区間に遷移していくかが問題っぽい...
今回は基本的なことしか書いてないからまだわからないけど
また違う問題で書こう
ARC090-E Avoiding Collision
何するか分かるけど、どうしたらいいのか分からないことが多かったので 書いておく
解法
1.S から各頂点への距離をDijkstraで求める
2.S から各頂点への経路数
各頂点からTへの経路数を求める
3.(全経路の組み合わせ) - (すれ違ってしまう組み合わせ) が答え
計算方法が分からず
1.は分かる
最短経路は必ずDAGになる(これは分かる)
dpをすれば経路数が分かるのだが
簡単に計算する方法があり
vector<P> vec; for(int i = 1;i <= n;i++) vec.push_back({dist[i] , i}); sort(vec.begin(),vec.end());
とすることで、Sから近い順に頂点を取り出すことができるので
この頂点順に沿って
for(int i = 0;i < n;i++) { for(auto & e : edges[vec[i].second]) { if(dist[e.to] == dist[vec[i].second] + e.cost) (dp_t[e.to] += dp_t[vec[i].second]) %= MOD; } }
としてやれば経路数が分かる
また各頂点からTまでの経路数は逆からやっていけばいい
for(int i = n - 1;i >= 0;i--) { for(auto & e : edges[vec[i].second]) { if(dist[vec[i].second] == dist[e.to] + e.cost) (dp_s[e.to] += dp_s[vec[i].second]) %= MOD; } }
全経路の組み合わせは
dp_t[t] * dp_s[s]
すれ違う可能性のあるのは
頂点か辺
頂点...
出会うタイミングのあるのは
dist[v] * 2 = dist[t];
となっている頂点v
経路の組み合わせの数は S -> v -> T と T -> v -> S の組み合わせなので
dp_t[v] * dp_s[v] * dp_s[v] * dp_t[v]
辺...
出会うタイミングは
辺の両端の頂点をu,vとすると
2 * dist[u] < dist[t] && dist[t] < 2 * dist[v]
&& dist[u] + cost == dist[v]
を満たす辺である
経路の君合わせの数は S -> u -> v -> T と T -> v -> u -> S の組み合わせなので
dp_t[u] * dp_s[v] * dp_s[v] * dp_t[u]
これらを引いてやればいいですね
初心忘れるべからず..
ARC083-E Bichrome Tree
dp解けなくて悲しいね...
解法
要するに、「根をそれぞれの色で塗った時の合計がX_i以下になる」を満たせば 頂点に重みをつけることで満たすことができる
じゃあどうやって求めるのか、ということですが...
根をどちらかに塗った時の値は
X_iの値(定義から自明)
か
片方の色の値
じゃあ、この「片方の色の値」を最小化していけば、
効率のいい塗り方が求められるのでは
となります
この値をdp[i]...(頂点iで片方の色で総和をX_iにした時のもう片方の色の総和)
とすれば
ナップサックで解けますね
たどり着けなくて悲しいね
WindowsのVSCodeにC++を書く環境を作る
VSCodeにC++の環境を作るのに手こずっている人をいっぱい観測して
このままじゃ広がらない(宗教的)と思ったので書いてみました
環境はSurface Pro 2017 , Windows10です
VSCodeインストール
ここから
一番左を選択
インストーラーがダウンロードされるのでそれを実行
気長に待ちましょう
起動できました
MinGWとLLVM-clangのインストール
こちらのページがとても参考になりますね
ここからが本題です
まずMinGWです
MinGWのインストールについては情報がありふれまくっているので
そちらを参考にしたほうがいいと思います
C言語入門 - MinGW - gcc のインストール - Windows環境 - Webkaru
ここで、MinGWのbinフォルダにパスを通しておいてください
次にLLVM-clangです
ここに飛んで LLVM Download Page
windows 64bitの方はこれ
これもインストーラーがダウンロードされるので実行しましょう
インストールしたLLVM/binにパスを通しておいてください
VSCodeに拡張機能を入れる
とりあえずこれでも書けて実行できるのですが
補完欲しいじゃないですか...
拡張機能を入れます
検索欄に「C++」と入力すると
いろいろ出てきますが
この二つを入れてVSCodeを再起動してください
次に、VSCodeでフォルダを開きます
ここをクリックして
適当な自分の作業フォルダを開いてみてください(プログラムを書く場所とか)
開いたら新しいファイルを作ってみましょう
適当にhello.cppとかでOKです
拡張機能の設定
設定を開きます
Ctrl+, でもいけます
するとこんな画面が開きます
これの右側が自分の設定ファイルで左側がデフォルトです
右側を編集して
このように設定します
設定が書けたら保存して、 hello.cppに戻りましょう
書いてみてください
感動
おそらくまだ補完が出ない方もいらっしゃると思います
問題はインクルードパスのデフォルトの設定が
visual studioのインクルードパスになっているせいです
visual studioのC++を入れていない方は多分補完が出ません
直しましょう
インクルードパスの設定
Ctrl+Shift+Pでコマンドパレットを開きます(これ便利)
「cpp」と入力すると
「Edit Configurations」
というのがあるので選択
デフォルトの設定ファイルが出てきます
いじるのはここ(winなので)
ここにMinGWのインクルードパスを追加します
,
"C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include/c++/x86_64-w64-mingw32",
"C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include/c++/backward",
"C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include",
"C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include-fixed",
"C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/../../../../x86_64-w64-mingw32/include",
"C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include/c++"
追記
keymoonさんからご指摘をもらいました！ありがとうございます
"/bin"から左のパスはmingwをインストールした場所に各自して下さい...
これで補完が出ると思います
実行する
統合ターミナル(?)を起動して
コマンドを打てば
できましたーー
お疲れ様ー
Dinic法を書いてみた(まだ使えない)
とあるツイートが流れてきたので勉強してみた
参考になった記事
流れ
level graph(Sからの最短距離)をつくる(BFS)
このとき必ず、まだflowを流せる辺(許容範囲が0より大きい辺)を選ぶ
2.level graphでのpathをすべて探索(DFS)
あと2 あと3
========> ========>
[1] [2] [3]
<-------- <--------
あと0 あと0
という経路(===>)をとった時
このpathに流せるflowは2
2を引き、逆向きの辺に2を足す
あと0 あと1
========> ========>
[1] [2] [3]
<-------- <--------
あと2 あと2
3.level graphがTに到達できなくなるまで繰り返す
実装してみる
上の参考にしたページとほぼ同じ(参考にしたから当たり前)
#include <iostream> #include <queue> #include <vector> using namespace std; struct Dinic { struct edge { int to; int cap; int rev; }; vector<vector<edge>> G; int N; vector<int> level; vector<int> itr; Dinic(int n) : N(n) { G.assign(N,vector<edge>()); } void add_edge(int from ,int to,int cap) { G[from].push_back({to,cap,(int)G[to].size()}); G[to].push_back({from,0,(int)G[from].size() - 1}); } //tに到達できない...falseを返す bool g_level(int s,int t) { level.assign(N,-1); queue<int> que; que.push(s); level[s] = 0; while(!que.empty()) { int v = que.front(); que.pop(); for(edge& e : G[v]) { if(e.cap > 0 && level[e.to] == -1) { level[e.to] = level[v] + 1; que.push(e.to); } } } return level[t] >= 0; } //辿った経路での最小の容量を返す int dfs(int v,int t,int f) { if(v == t) return f; for(int& i = itr[v];i < G[v].size();i++) { edge& e = G[v][i]; if(e.cap > 0 && level[e.to] > level[v]) { int mi_f = dfs(e.to,t,min(f,e.cap)); if(mi_f > 0) { e.cap -= mi_f; G[e.to][e.rev].cap += mi_f; return mi_f; } } } return 0; } int max_flow(int s,int t) { int result = 0; int flow; while(g_level(s,t)) { itr.assign(N,0); while((flow = dfs(s,t,1e9)) > 0) result += flow; } return result; } }; /* checked: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2722839#1 */
まだ書いただけなので実際にどんな問題に使えるかを勉強しなきゃ
