bitDPでの集めるDPと配るDPについて
こんなツイートが
bitDPのほうが集めるイメージ強くない?(なんか結局bitの表現に慣れれるかどうかみたいなあれな気がしてきた)
— てんぷら (@tempura_pp) June 20, 2018
このときは「わかる」ってなってたんですけど
いざ問題を解いてみるとそんなこと無いな,なんでだろう,みないな記事です
以下の問題のネタバレを含みます 気をつけてください
https://yukicoder.me/problems/no/357
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263
考える問題1
https://yukicoder.me/problems/no/357
空白
集めるDP
で書くとこうなる
#include <bits/stdc++.h> using namespace std; using i64 = long long; int N,M; i64 score[14][14]; i64 dp[1 << 14]; int main(){ cin >> N >> M; for(int i = 0;i < M;i++){ i64 a,b,c; cin >> a >> b >> c; score[a][b] = c; } for(int s = 1;s < (1 << N);s++){ for(int p = 0;p < N;p++){ int t = s & ~(1 << p); if(t == s) continue; i64 res = 0; for(int i = 0;i < N;i++){ if(t & (1 << i)){ res += score[i][p]; } } dp[s] = max(dp[s],dp[t] + res); } } cout << dp[(1 << N) - 1] << endl; }
集めるbitDPは
int t = s & ~(1 << p);
としてやることでp番のアイテムを置く前の状態
を表現できる
このとき
if(t == s) continue;
とするのが重要で,置く前の状態
になっているかを確認する
配るDP
で書くとこうなる
#include <bits/stdc++.h> using namespace std; using i64 = long long; int N,M; i64 score[14][14]; i64 dp[1 << 14]; int main(){ cin >> N >> M; for(int i = 0;i < M;i++){ i64 a,b,c; cin >> a >> b >> c; score[a][b] = c; } for(int s = 0;s < (1 << N);s++){ for(int p = 0;p < N;p++){ int t = s | (1 << p); if(t == s) continue; i64 res = 0; for(int i = 0;i < N;i++){ if(s & (1 << i)){ res += score[i][p]; } } dp[t] = max(dp[t],dp[s] + res); } } cout << dp[(1 << N) - 1] << endl; }
配るbitDPは
int t = s | (1 << p);
としてやることでp番を置いたあとの状態
を表現できる
if(t == s) continue;
も同様である
ここはあんまり差が無い
まあなんとかなるかなぁみたいな
本題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263
もち
遷移
i回目の点灯の前の状態をstateとします
するとi回目の点灯があったあとはstate | A[i]
という状態になります
その後、プレイヤーがjのパターンでボタンを押すと(state | A[i]) & ~B[i]
という状態になります
このとき押したボタンの数は(state | A[i]) & B[i]
のビットの立っている数です
つまり遷移は
dp[i + 1][(s | A[i]) & ~(B[j])] = max(dp[i + 1][(s | A[i]) & ~(B[j])] , dp[i][s] + __builtin_popcount((s | A[i]) & B[j]));
これは配るDPですね
集めるDPは?
遷移が思いつきにくい
なんで?
ゲームはすすめるイメージが強いのかなぁ...
でもしっかり配るDPでできたし、こっちのほうが素直
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) int N; int C; vector<i64> A,B; int dp[31][1 << 16]; int solve(){ rep(i,0,30){ rep(j,0,(1 << 16) - 1) dp[i][j] = -1e9; } dp[0][0] = 0; cin >> N >> C; if(N == 0 && C == 0){ return 0; } A.assign(N,0); B.assign(C,0); rep(i,0,N - 1){ rep(j,0,15){ int a; cin >> a; A[i] += a * (1LL << j); } } rep(i,0,C - 1){ rep(j,0,15){ int a; cin >> a; B[i] += a * (1LL << j); } } rep(i,0,N - 1){ rep(s,0,(1 << 16) - 1){ rep(j,0,C - 1){ auto & to = dp[i + 1][(s | A[i]) & ~(B[j])]; to = max(to , dp[i][s] + __builtin_popcount((s | A[i]) & B[j])); } } } int ans = 0; rep(s,0,(1 << 16) - 1){ ans = max(ans,dp[N][s]); } cout << ans << endl; return 1; } int main(){ while(solve()); }
まだ議論の余地がアリそうですね...(気分っていうのもあるかもしれない)
AtCoder 天下一プログラマーコンテスト0216予選A D グラフィカルグラフ
chokudaiしゃんに投げられたので解きましたー
問題
https://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_d
いわゆる構築
解法
常に最高効率で構築するのはとても大変
無駄があったり制約を満たさない解法であっても、必ず成立させられる構築方法を考えるのはとても重要
今回の場合であれば、「点の位置を必ず辺に到達できないようにする」ことで達成できるので
2^n >= 2^(n-1) + 2^(n-2) + ... + 1
を使って、
辺の長さを2^n,2^(n-1),2^(n-2)
というように変化させることで
辺が交差しないように構築できます
が,H,W<=100
を達成できません
これは座標圧縮をすることで解決できます
コード
https://tenka1-2016-quala.contest.atcoder.jp/submissions/2702775
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) vector<vector<int>> G; i64 X[100]; i64 Y[100]; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int vis[100]; void rec(int v,int n,int before_cnt){ vis[v] = 1; int cnt = -1; for(int to : G[v]){ if(vis[to]) continue; cnt++; if(cnt == (before_cnt ^ 1)) cnt++; X[to] = X[v] + dx[cnt] * (1LL << n); Y[to] = Y[v] + dy[cnt] * (1LL << n); rec(to,n - 1,cnt); } } char ans[100][100]; void rec2(int v,int n,int before_cnt){ ans[X[v]][Y[v]] = v + 'A'; vis[v] = 1; int cnt = -1; for(int to : G[v]){ if(vis[to]) continue; int ddx = (X[to] - X[v] > 0 ? 1 : -1); int ddy = (Y[to] - Y[v] > 0 ? 1 : -1); if(X[to] == X[v]) ddx = 0; if(Y[to] == Y[v]) ddy = 0; for(int x = X[v] + ddx,y = Y[v] + ddy;x != X[to] || y != Y[to];x += ddx,y += ddy){ ans[x][y] = (ddx != 0 ? '|' : '-'); } rec2(to,n - 1,cnt); } } int main(){ rep(i,0,99){ rep(j,0,99) ans[i][j] = '.'; } int N; cin >> N; G.resize(N); rep(i,0,N - 2){ char c,d; cin >> c >> d; int a,b; a = c - 'A'; b = d - 'A'; G[a].push_back(b); G[b].push_back(a); } rec(0,N,10); vector<i64> xs,ys; rep(i,0,N - 1){ xs.push_back(X[i]); ys.push_back(Y[i]); } sort(xs.begin(),xs.end()); sort(ys.begin(),ys.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end()); rep(i,0,N - 1){ X[i] = lower_bound(xs.begin(),xs.end(),X[i]) - xs.begin(); Y[i] = lower_bound(ys.begin(),ys.end(),Y[i]) - ys.begin(); X[i] *= 2; Y[i] *= 2; vis[i] = 0; } rec2(0,N,10); cout << 100 << " " << 100 << endl; rep(i,0,99){ rep(j,0,99){ cout << ans[i][j]; } cout << endl; } }
感想
・2進数ってすごいなぁ...
・制約以上のを考えたときは圧縮を考える
LinuxにC++を快適に書く環境を作る(Visual Studio Code + cquery)
経緯
結構前にclang Adaptaを使ったvscodeの環境構築方法の記事を書きました
が、これ最悪ですね???
・重い ・エラーチェック遅い ・重い ・VSじゃん()
LSPのcqueryを使えばバク速です!!!
(Windowserはおとなしくclangdを使いましょう)
(MacOSの記事も書きたいけど環境がない...)
僕の環境構築テスト環境
Xubuntuなのでapt
を乱用していますが、それそれ読み替えれば大丈夫だと思います
VSCodeインストール
ここから自分のプラットフォームに合わせてインストールしましょう
Archの方はAUR https://aur.archlinux.org/packages/visual-studio-code-bin/ からインストールしてください
cqueryのビルド
sudo apt-get install clang clang-tools llvm llvm-6.0-tools libclang-6.0-dev
を入れておけばできるはずです
これと同じように進めます
僕はホームディレクトリでやりました
git clone https://github.com/cquery-project/cquery --single-branch --depth=1 cd cquery git submodule update --init ./waf configure --variant=system --llvm-config=/usr/bin/llvm-config build
ビルドされたcqueryにパスを通します
~/.profileにこれを書き加える
PATH="$HOME/cquery/build/system/bin:$PATH"
vscodeセットアップ
vscodeは基本フォルダを開いて作業します(Atomにも同じようなのがあるはず)
ディレクトリでcode .
とコマンドを打つと、vscodeがそのディレクトリを開いてくれます
C++を書く用のディレクトリでcode .
とやってみてください(僕は適当に~/C++/でやりました)
左のバーの一番したをクリックをすると拡張機能を選ぶことができます
今回入れるのはC/C++
とcquery
です
それぞれC++
,cquery
と検索欄で打つと出てくるのでinstall
を押してreload
をします
これで完了です!!
コードを書く
フォルダを開いていないとエラーチェックとか補完とか出してくれないので注意です!
使い方
これについてはまた書こうかなと思ってます><
AtCoder Biginner Contest 099 C Strange Bank
なかなかおもしろい問題が出たので、主な考察の流れを書いておこうかなと思います
問題
https://abc099.contest.atcoder.jp/tasks/abc099_c
ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかとなっています。 1 円 6 円、6^2(=36) 円、6^3(=216) 円、… 9 円、9^2(=81) 円、9^3(=729) 円、… この銀行からちょうど N 円を引き出すには少なくとも何回の操作が必要か求めてください。 ただし、一度引き出したお金を再び預け入れてはならないとします。 1 <= N <= 100000
考察
自分が意識していることの一つに、
「一気に二つのことをしようとするな」
なので、これも
「一気に6nと9nを扱おうとするな」
と考えて解きました(状態をうまく縮約できるときもありますが、難しい場合が多い(それはAGC))
それぞれで考えます
6nだけ使える場合
このときは N を6進数で表示したときの桁の総和が答えです
9nだけ使える場合
このときは N を9進数で表示したときの桁の総和が答えです
これを踏まえると....
6進数で扱う分と9進数で扱う分で分けてそれぞれの総和を足せばイケそう...?
となるのでそれをします
O(NlogN)で解くことができましたね
https://abc099.contest.atcoder.jp/submissions/2649449
クソコード
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) int N; int main(){ cin >> N; int result = N; for(int n = 0;n <= N;n++){ int nn = n; int m = N - n; int ans = 0; int nine = 1; while(nine * 9 <= nn) nine *= 9; while(nine != 1){ ans += nn / nine; nn %= nine; nine /= 9; } ans += nn; nn = m; nine = 1; while(nine * 6 <= nn) nine *= 6; while(nine != 1){ ans += nn / nine; nn %= nine; nine /= 6; } ans += nn; result = min(ans , result); } cout << result << endl; }
もちろんDPでも解けますね...
vimでC++書くんだったら vim-lsp + cquery 使おうぜ
つい最近clangdについて記事を書きました
なんか矛盾してませんか
clangd,とっても優秀なのですが
・別ファイルにある定義先に飛べない ・メモリ消費量がエグい(6GB...)
などの欠点がありました
実はclangdを導入する前にcqueryを使う予定でしたが、そのときはうまく行かなかったので、ここに記したいと思います
cqueryの導入
brewやaurを使ってインストールすると、バージョンが低いためにvimでエラーを吐きまくる事態になっていたので、直接 build したいと思います
基本ここの、"Build the language server" に従って行きますが
clangとllvmがインストールされているなら
ここにあるように
1 $ git clone https://github.com/cquery-project/cquery --single-branch --depth=1 2 $ cd cquery 3 $ git submodule update --init && ./waf configure --variant=system --llvm-config=/usr/bin/llvm-config build
としたほうが良さそうです
あとは,cquery/build/system/bin
にパスを通します
vimに導入
ひゃひゃ
[[plugins]] repo='prabirshrestha/async.vim' [[plugins]] repo='pdavydov108/vim-lsp-cquery' hook_add=''' autocmd FileType c,cc,cpp,cxx,h,hpp nnoremap <leader>fv :LspCqueryDerived<CR> autocmd FileType c,cc,cpp,cxx,h,hpp nnoremap <leader>fc :LspCqueryCallers<CR> autocmd FileType c,cc,cpp,cxx,h,hpp nnoremap <leader>fb :LspCqueryBase<CR> autocmd FileType c,cc,cpp,cxx,h,hpp nnoremap <leader>fi :LspCqueryVars<CR> ''' [[plugins]] repo='prabirshrestha/vim-lsp' hook_add=''' if executable('cquery') au User lsp_setup call lsp#register_server({ \ 'name': 'cquery', \ 'cmd': {server_info->['cquery']}, \ 'root_uri': {server_info->lsp#utils#path_to_uri(lsp#utils#find_nearest_parent_file_directory(lsp#utils#get_buffer_path(), 'compile_commands.json'))}, \ 'initialization_options': { 'cacheDirectory': '/tmp/cquery/cache' }, \ 'whitelist': ['c', 'cpp', 'objc', 'objcpp', 'cc'], \ }) endif let g:lsp_signs_enabled = 1 " enable signs let g:lsp_diagnostics_echo_cursor = 1 " enable echo under cursor when in normal mode let g:lsp_signs_error = {'text': '✗'} let g:lsp_signs_warning = {'text': '‼'} let g:asyncomplete_completion_delay=10 ''' [[plugins]] repo='prabirshrestha/asyncomplete.vim' [[plugins]] repo='prabirshrestha/asyncomplete-lsp.vim'
compile_command.json
今話題の†json†
これを見てやってもらうとプロジェクト内でもいい感じにcqueryが動いてくれます
単一ファイルで補完が出したい
競プロerの僕は一個のファイルだけを編集するので
それに合わせてcompile_command.jsonを構成しないといけません
いちいち書くのは面倒なので
function MakeCquery() let temp = expand('%:p') echo system('echo ''[{"directory": "/home/kutimoti/contest","command": "/usr/bin/c++ ' . temp . ' -std=c++11","file": "' . temp . '"}]'' > compile_commands.json') endfunction
とinit.vimにしてやって
call MakeCquery()
としてセッティングしています
楽しいLSPコーディング生活を!
vim8,neovimで補完使うならdeopleteよりvim-lsp使おうぜ
vscodeのMicrosoftが作ったC++拡張機能にはLanguage Server Protocol(LSP)という技術が使われています
LSPは他の言語にももちろん対応しています(C#のOmniSharpとか)
これが補完などの処理を行ってくれます
neovimのC++補完
今まで僕は,deoplete-clangやdeoplete-xclangを使ってきましたが,
「(多分)毎回"clang"の呼び出しを行っているのが原因で補完などの動作がvscodeに比べて遅い」
印象を受けていました
vimでもLSPを使うものが無いかと調べると出てきました
(作ってる人がMicrosoftの方)
ここを見れば簡単に導入できると思います
install
まずclangdをインストールします
sudo pacman -S llvm clang-tools-extra
deinを使ってインストールしています(それぞれの環境に合わせてインストールしてください><)
[[plugins]] repo='prabirshrestha/async.vim' [[plugins]] repo='prabirshrestha/vim-lsp' hook_add=''' if executable('clangd') au User lsp_setup call lsp#register_server({ \ 'name': 'clangd', \ 'cmd': {server_info->['clangd']}, \ 'whitelist': ['c', 'cpp', 'objc', 'objcpp'], \ }) endif let g:lsp_signs_enabled = 1 " enable signs let g:lsp_diagnostics_echo_cursor = 1 " enable echo under cursor when in normal mode let g:lsp_signs_error = {'text': '✗'} let g:lsp_signs_warning = {'text': '‼'} <i></i> ''' [[plugins]] repo='prabirshrestha/asyncomplete.vim' [[plugins]] repo='prabirshrestha/asyncomplete-lsp.vim' [[plugins]] repo='prabirshrestha/asyncomplete-neosnippet.vim' hook_add=''' call asyncomplete#register_source(asyncomplete#sources#neosnippet#get_source_options({ \ 'name': 'neosnippet', \ 'whitelist': ['*'], \ 'completor': function('asyncomplete#sources#neosnippet#completor'), \ })) imap <C-k> <Plug>(neosnippet_expand_or_jump) smap <C-k> <Plug>(neosnippet_expand_or_jump) xmap <C-k> <Plug>(neosnippet_expand_target) '''
補完
Rename
エラー表示
vim-lsp + clangdの恐るべきエラー表示の速さ(obsで撮ったら色落ちした) pic.twitter.com/05aJ7xZEas
— おもちもちもちくちもちとくら (@Kutimoti_T) May 20, 2018
bits/stdc++11.hをインクルードしても全く重くならなかったのですごい(すごい)
他にもコマンドはあるのでぜひ使ってみてください
格子状に座標が分けられて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
僕のコード