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)に切り、必ず一つのピースが２つのピースに分かれるように切る
N回切ったときに存在するN + 1個のピースの大きさをソートして出力する
見られた解法
進む方向に切った部分があるのか、無いのかを判定して進む方法
O(WHn)なので十分間に合うけど...
判定めんどい(これが実装力のなさ)ので
2 * 2 の
oo oo
のような板チョコを
+++++ +o+o+ +++++ +o+o+ +++++
のようにしてやると、
+は辺
oはチョコみたいにできるので、カットがかんたんにできますね(+の対応する部分を通れないようにする)
あとは座標(x,y)の２つの値がどちらも奇数のところがチョコの部分なので、それをカウントすれば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)で取り除くことのできるブロックの数
どのように求めるか
２つパターンがあって、今見ている区間を[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]); } } }
幅を広げていくイメージです
コツ？？
結局、遷移が大事だったね(ア)
どのように小さな区間に遷移していくかが問題っぽい...
今回は基本的なことしか書いてないからまだわからないけど
また違う問題で書こう
