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 */
まだ書いただけなので実際にどんな問題に使えるかを勉強しなきゃ
精進 ABC077D-Small Multiple
すごくいい経験になったと思う
これからも使いそうな考え方を書いておく
この問題の特徴
まず、目に付くのは
「Kの正の倍数」という制限
僕は、このような「上に無制限」な問題に慣れていなかったのがダメだった思う
じゃあどうするの
なんとかして、この「Kの正の倍数」という無制限さを
有限に置き換えたい
どうするか
Kの倍数ということは
すべてKで割った時の剰余が0になる
まずこれに目をつけなければならなかった
また、数同士の関係性についても考えてみる
1 -> 2
1を足すと桁の和が1増える
1 -> 10
10を掛けると桁の数は変わらない
これを mod K の有限の世界で考えると
K の倍数、つまり 0 (mod K)を目指せばいいということだ
これは 0~K-1について
上の関係性のグラフを貼れば求めることができる(これは01BFS)
世界を狭める方法を考えることが大事だった
このような経験がなかったので成長できたと思う
精進 ARC068E Snuke Line
何をしても時間がかかりそう...
と悩んでいたが解説見てー
あーなるほどってなった
わかってたこと
r - l + 1 > d を満たす区間は必ず１回以上通る
それ以外は通らない、または１回だけ通る(つまり分からない)
わからなかったこと
倍数の計算量の抑え方
方針
・dはループで1~mまで計算する
・r - l + 1 <= d を満たす区間[l,r]に1加算する
このようにすることで、
dの倍数全てについて総和を取ることで
通るか通らないか分からない区間について調べることができる
つまりdについて
N - (r - l + 1 <= d を満たす区間 つまり通るかわからない区間)
+ (駅[i]における分からない区間の名産品の種類の数 | i は d の倍数)
とできるね
あとはBITを使うだけ
とは言いつつBITとimos法を合体させてるの面白くないですか
僕は面白いなーと思った
精進 ARC074D - 3N Numbers
おおー500点とかびびってたけど
最近の精進が効いてきてるみたいで自力で解けた嬉しい
さて方針
吸収していく、というイメージを持ちました
入力例1 2 3 1 4 1 5 9
これを右側と左側で分けてみると
[ 3 1 ] 4 1 [ 5 9 ]
左側は大きく、右側は小さくしていくのが目標ですね
左から3番目の4を考えてみよう
左側を大きくすることだけを考えれば
左側のグループで最小の1を捨てて、4を吸収するのがいいですね
また、
右から３番めの1を考える
右側を大きくすることを考えれば
右側のグループで最大の9を捨てて、1を吸収するのがいいです
これを方針とします
ここからがちょっと問題
ただし、どこまでを左側のグループで考えるか、
どこまでを右側のグループで考えるかを
決めることは不可能です
これは、全部試さなきゃダメ(この方針が今の僕に大切だと思う)
よく考えると
それぞれのグループの和はDPで求めることができます
これを利用して計算すればすべて試すことができる
O(NlogN)で通りました
