Codeforces 1000B Light It Up
http://codeforces.com/problemset/problem/1000/C
問題概要
時間 0,a1,a2,...,aN,M のタイミングで明かりがON,OFFを繰り返す.
ここで最大1個,タイミングを増やすことができる.
明かりがついている時間を最大化せよ.
解法
onの区間にXを挿入する
a_i-2 [off] a_i-1 [on] a_i [off] a_i+1
のような区間を
a_i-2 [off] a_i-1 [on] X [off] a_i [on] a_i+1
とすることを考えると,このときの明かりがついている時間の合計は,Xを挿入する前の状態を考えて
(a[i]より左側のonの時間) - 1 + (a[i]より右側のoffの時間)
となる.なぜなら,なるべくonの区間を長くしようとするとX = (a_i) - 1
となるからである
offの区間にXを挿入する
a_i-2 [on] a_i-1 [off] a_i [on] a_i+1
のような区間を
a_i-2 [on] a_i-1 [off] X [on] a_i [off] a_i+1
とすることを考えると,このときの明かりがついている時間の合計は,Xを挿入する前の状態を考えて
(a[i - 1]より左側のonの時間) + (a[i - 1]より右側のoffの時間) - 1
となる.なぜなら,なるべくonの区間を長くしようとするとX = (a_i - 1) - 1
となるからである
Xの挿入する区間がonかoffかはindexの偶奇によって決まるので,それを実装してやれば良い.
source code
#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; i64 M; vector<i64> A; int main(){ cin >> N >> M; A.resize(N + 2); A[0] = 0; rep(i,1,N) cin >> A[i]; A[N + 1] = M; vector<i64> on; vector<i64> off; on.push_back(0); off.push_back(0); rep(i,1,N + 1){ if(i % 2 == 1){ on.push_back(A[i] - A[i - 1] + on.back()); off.push_back(off.back()); } else{ off.push_back(A[i] - A[i - 1] + off.back()); on.push_back(on.back()); } } i64 ans = on.back(); rep(i,1,N){ if(i % 2 == 1){ ans = max(ans , on[i] - 1 + off.back() - off[i]); } else{ ans = max(ans , off.back() - off[i - 1] - 1 + on[i]); } } cout << ans << endl; }
こういう問題をきれいに早く実装したいなぁ...
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をインクルードしても全く重くならなかったのですごい(すごい)
他にもコマンドはあるのでぜひ使ってみてください