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について

こんなツイートが

このときは「わかる」ってなってたんですけど

いざ問題を解いてみるとそんなこと無いな,なんでだろう,みないな記事です

以下の問題のネタバレを含みます 気をつけてください

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の環境構築方法の記事を書きました

kutimoti.hatenablog.com

が、これ最悪ですね???

・重い ・エラーチェック遅い ・重い ・VSじゃん()

LSPのcqueryを使えばバク速です!!!

(Windowserはおとなしくclangdを使いましょう)

(MacOSの記事も書きたいけど環境がない...)

僕の環境構築テスト環境

Xubuntuなのでaptを乱用していますが、それそれ読み替えれば大丈夫だと思います

VSCodeインストール

code.visualstudio.com

ここから自分のプラットフォームに合わせてインストールしましょう

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

を入れておけばできるはずです

kutimoti.hatenablog.com

これと同じように進めます

僕はホームディレクトリでやりました

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++/でやりました)

左のバーの一番したをクリックをすると拡張機能を選ぶことができます

f:id:Kutimoti:20180302100535p:plain
Extension

今回入れるのは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について記事を書きました

kutimoti.hatenablog.com

なんか矛盾してませんか

clangd,とっても優秀なのですが

・別ファイルにある定義先に飛べない
・メモリ消費量がエグい(6GB...)

などの欠点がありました

実はclangdを導入する前にcqueryを使う予定でしたが、そのときはうまく行かなかったので、ここに記したいと思います

cqueryの導入

brewやaurを使ってインストールすると、バージョンが低いためにvimでエラーを吐きまくる事態になっていたので、直接 build したいと思います

github.com

基本ここの、"Build the language server" に従って行きますが

clangとllvmがインストールされているなら

github.com

ここにあるように

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

github.com

これを見てやってもらうとプロジェクト内でもいい感じに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使おうぜ

つい最近,vscodeC++導入の記事を書きました

kutimoti.hatenablog.com

vscodeMicrosoftが作ったC++拡張機能にはLanguage Server Protocol(LSP)という技術が使われています

qiita.com

LSPは他の言語にももちろん対応しています(C#のOmniSharpとか)

これが補完などの処理を行ってくれます

neovimのC++補完

今まで僕は,deoplete-clangやdeoplete-xclangを使ってきましたが,

「(多分)毎回"clang"の呼び出しを行っているのが原因で補完などの動作がvscodeに比べて遅い」

印象を受けていました

vimでもLSPを使うものが無いかと調べると出てきました

github.com

(作ってる人が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)
'''

補完

f:id:Kutimoti:20180520105926p:plain

Rename

f:id:Kutimoti:20180520110006p:plain

f:id:Kutimoti:20180520110020p:plain

f:id:Kutimoti:20180520110030p:plain

エラー表示

bits/stdc++11.hをインクルードしても全く重くならなかったのですごい(すごい)

他にもコマンドはあるのでぜひ使ってみてください