格子状に座標が分けられてDFS,BFSするとき
絶対既存(調べ方がわからない)
なんかよくわからないタイトルになってしまったけど()
ちょっとしたテクも書いていこうかなみたいな備忘録
問題
問題概要
W * Hの大きさの板チョコがあり、格子に沿って切ろうとしている
(xi1,yi1)から(xi2,yi2)に切り、必ず一つのピースが2つのピースに分かれるように切る
N回切ったときに存在するN + 1個のピースの大きさをソートして出力する
見られた解法
進む方向に切った部分があるのか、無いのかを判定して進む方法
O(WHn)なので十分間に合うけど...
判定めんどい(これが実装力のなさ)ので
2 * 2 の
oo oo
のような板チョコを
+++++ +o+o+ +++++ +o+o+ +++++
のようにしてやると、
+は辺
oはチョコみたいにできるので、カットがかんたんにできますね(+の対応する部分を通れないようにする)
あとは座標(x,y)の2つの値がどちらも奇数のところがチョコの部分なので、それをカウントすればOKですね
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) int W,H; int N; vector<vector<int>> fie; using P = pair<int,int>; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int bfs(int sx,int sy){ int ans = 0; queue<P> que; que.emplace(sx,sy); fie[sx][sy] = 0; while(!que.empty()){ int x = que.front().first; int y = que.front().second; que.pop(); if((x % 2 == 1) && (y % 2 == 1)) { ans++; } for(int i = 0;i < 4;i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(!(1 <= nx && nx <= W * 2 - 1)) continue; if(!(1 <= ny && ny <= H * 2 - 1)) continue; if(!fie[nx][ny]) continue; fie[nx][ny] = 0; que.emplace(nx,ny); } } return ans; } int main(){ cin >> W >> H >> N; fie.resize(W * 2 + 1,vector<int>(H * 2 + 1,1)); rep(i,0,N - 1){ int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; if(x1 == x2){ rep(y,y1 * 2,y2 * 2){ fie[x1 * 2][y] = 0; } } else{ rep(x,x1 * 2 ,x2 * 2){ fie[x][y1 * 2] = 0; } } } vector<int> ans; rep(i,1,2 * W - 1){ rep(j,1,2 * H - 1) { if (fie[i][j]) { ans.push_back(bfs(i, j)); } } } sort(ans.begin(),ans.end()); for(int i = 0;i < ans.size();i++){ cout << ans[i] << " \n"[i + 1 == ans.size()]; } }
(実はもっとうまくかける(外枠を通れないようにしておけば、範囲の指定なんて要らない))
ICPCのこの問題も同じようにして解いてますねー
Amazing Mazes | Aizu Online Judge
僕のコード
■
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)で取り除くことのできるブロックの数
どのように求めるか
2つパターンがあって、今見ている区間を[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; } //パターン2.区間を分ける 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をインストールした場所に各自して下さい...
これで補完が出ると思います
実行する
統合ターミナル(?)を起動して
コマンドを打てば
できましたーー
お疲れ様ー