ICPC2019 国内予選参加記

2019/07/12 に開催されたICPC国内予選に沖縄高専「NeMiKoji」チームの一員として参加した.

結果

3完114位.

チームメンバー

各ニックネームの一部を切り取ってくっつけたのがチーム名だ.

実施環境

  • 場所: 沖縄高専 2Fプログラミング演習室
  • OS: MacOS Mojave
  • マシン: MacBookPro(ディスプレイとキーボードとマウスをつなぐのでレギュレーション違反でない)
  • キーボード: HHKB US配列(チーム全員がUS配列触れるマンだったので)
  • 使用言語: C++17
  • エディタ: NeoVim(coc.nvim+clangdで補完が効くようになっている)

スタイル

この中でおそらくタイピング速度が一番はやいのと,HHKBに慣れているkurokoji(ぼく)がコーディングを担当.

基本的にぼくがコーディングしているときに,nemusouとmitoが考察をするスタイル.

コンテスト前

特別ICPCの対策をしているわけではなく,各々研究室で時間を潰した.

ぼくは寝ていて,mitoはAndroidStudioで遊んでいて,nemusouはベースの練習をしていた.

15:55くらいに起床して,「もう16:00なるやん!! 急ごう!!」と二人を急かしたが,開始が16:30であることに気づきウケた.

ライブラリはUnionFindだけ印刷した.ぶっちゃけ幾何とか出ても解けないので.

コンテスト中

A問題

A問題はやるだけだったので,やった.ぼくがコーディングしつつ2人はBの解読にかかる.

8:00でAC.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
  int n, m;

  while (std::cin >> n >> m, n != 0 || m != 0) {
    int v[n][m];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        std::cin >> v[j][i];
      }
    }

    std::vector<int> sum(n);

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        sum[i] += v[i][j];
      }
    }

    std::cout << *std::max_element(sum.begin(), sum.end()) << std::endl;
  }
}

B問題

「B問題のBはBFS」と思いながらコーディング.最近,全くといって競技プログラミングをしていなかったので蟻本を見ながら実装する.

ちょいちょいバグを埋め込んだので時間を食ってしまう.

34:30でAC.よく考えたらマンハッタン距離を足すだけなのに無駄なことをしてしまった.

#include <iostream>
#include <vector>
#include <queue>

const int INF = 100000000;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int h, w;

int bfs(const std::vector<std::string>& field, int sy, int sx, int gy, int gx) {
  using P = std::pair<int, int>;
  int d[100][100];

  for (int i = 0; i < 100; ++i) {
    for (int j = 0; j < 100; ++j) {
      d[i][j] = INF;
    }
  }

  P p = {sy, sx};

  std::queue<P> q;
  q.emplace(p);
  d[sy][sx] = 0;

  while (!q.empty()) {
    auto [y, x] = q.front();
    q.pop();

    if (y == gy && x == gx) break;
    for (int i = 0; i < 4; ++i) {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (0 <= ny && ny < h && 0 <= nx && nx < w && d[ny][nx] == INF) {
        q.emplace(ny, nx);
        d[ny][nx] = d[y][x] + 1;
      }
    }
  }

  return d[gy][gx];
}

int main() {

  while (std::cin >> h >> w, h != 0 || w != 0) {
    std::vector<std::string> field(h);
    std::string s;

    for (int i = 0; i < h; ++i) {
      std::cin >> field[i];
    }

    std::cin >> s;

    int sum = 0;
    int fy = 0, fx = 0;
    for (auto&& c : s) {
      bool flg = false;
      int gy, gx;
      for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
          if (c == field[i][j]) {
            gy = i;
            gx = j;
            flg = true;
            break;
          }
        }
        if (flg) break;
      }

      sum += bfs(field, fy, fx, gy, gx);
      fy = gy;
      fx = gx;
    }

    std::cout << sum + s.size() << std::endl;
  }
}

C問題

先に問題を読んでいた二人から説明を聞きながら考察.なんかDPみたいなことするんだろうか,ウーンと唸りながら考えていた.mitoが分銅のパターンを列挙できそうみたいなことを言っていた.

これ全列挙したら時間足りなくね? と思ったのでまた考察に入った.その間に二人にはD問題を見てもらっていた.

よくよく考えたら計算量は  O(3^ M \times 100) なので制約を考慮すると現実的な時間に終わるやんというのに気づき実装を始める.

2:21:28にAC.通ったときはみんなでハイタッチした.めっちゃ嬉しかった.(けど時間かかりすぎ!!!!)

#include <iostream>
#include <vector>
#include <map>
#include <cstdint>
#include <unordered_map>

using lint = std::int_fast64_t;
int n, m;
int a[100], w[10];
std::map<lint, int> cand;

void func(int i = 0, int sum = 0) {
  if (i == m) {
    cand[sum]++;
    return;
  }

  func(i + 1, sum + w[i]);
  func(i + 1, sum - w[i]);
  func(i + 1, sum);
}

int main() {
  while (std::cin >> n >> m, n != 0 || m != 0) {
    cand = std::map<lint, int>();
    for (int i = 0; i < n; ++i) {
      std::cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
      std::cin >> w[i];
    }

    func();

    int cnt = 0;
    bool ok[100] = {};
    for (int i = 0; i < n; ++i) {
      for (auto&& e : cand) {
        if (a[i] == e.first) {
          cnt++;
          ok[i] = true;
        }
      }
    }

    std::map<lint, int> cand2;
    if (cnt == n) {
      std::cout << 0 << std::endl;
    } else {
      for (int i = 0; i < n; ++i) {
        std::unordered_map<lint, bool> m;
        if (ok[i]) continue;
        for (auto&& [key, value] : cand) {
          if (m[std::abs(a[i] - key)]) continue;
          cand2[std::abs(a[i] - key)]++;
          m[std::abs(a[i] - key)] = true;
        }
      }

      bool flg = false;

      for (auto&& [key, value] : cand2) {
        if (value == n - cnt) {
          std::cout << key << std::endl;
          flg = true;
          break;
        }
      }

      if (!flg) {
        std::cout << -1 << std::endl;
      }
    }
  }
}

D問題

全然分からなかった.とりあえずそれっぽいやつを書こうとしたけどC問題に時間を掛けすぎてタイムオーバー.

コンテスト後

3人とも互いに「最近競プロやってない割には頑張ったじゃない?」と褒め称えた.

実は昨年もmitoとぼくと先輩で参加したのだが,1完に終わって悔しかった記憶が残っていた.それに比べると3完なので良いよね.

感想

役割をちゃんと分業できたので,チームワークは割と良かったと思う.

予選は通過出来なかったが,良い経験だった.PCKぶりにチームで競プロをしたので楽しかった.

来年からぼくは岐阜大学に進学するのでこのチームで出場出来ないが,岐阜大でも仲間を見つけてICPC出場したい.(岐阜大ICPC出たことなさそうだが)

競技プログラミング引退したはずだったけど楽しいので復帰しそう?

D言語のおはなし

※この記事は ICT Advent Calendar 2018 18日目の記事です.

昨日はICUに合格したらしいまなえです.

manaway1019.hatenablog.com

明日は,私が高専を去ることを心底悲しんでいるkurokojiです.

親しい人が離れていくというのは正直寂しいですよ.はい.

毎年私からの愛のこもったフリを受けるために,私の次の日に記事を書いちゃう可愛いやつです.

誤りがあるので言っておくと,僕のほうが先に18日に書く予定を入れていたのに,17日に後からわざと入れたのはあなたでしょ??? 事実を曲げることは良くないです.


D言語を流行らせたい

全人類が学ぶべき言語であるところのD言語.しかし実態はあまり知られていないように思います.

D言語くんは知っていますか?

D言語くん

Twitter等で一度は見たことがあると思います.何かと変なポーズなので,ほとんどの人が笑いの対象としか見ていないような気はしますが.

「変なマスコットキャラクターが存在する,ようわからん言語」

そのイメージを払拭するために,このD言語販促記事を書いてます.

あ,ちなみに今年の高専プロコン競技部門のソルバはD言語で書かれています.

https://github.com/kurokoji/procon29-kyogi/tree/master/nagatogithub.com

軽い文法の紹介

import std.stdio, std.array;

void main() {
  writeln("Hello, World!!");
  for (size_t i = 0; i < 10; ++i) {
    writeln(i);
  }

  /*
  上のfor文と同じ動きをする
  foreachの場合,iの型は何も書かなくても型推論してくれます
  */
  foreach (i; 0 .. 10) {
    writeln(i);
  }

  uint[] ar = [1, 2, 3, 4, 5];
  ar[0 .. 3] = 0; // [0, 0, 0, 4, 5]
  ar[0 .. $] = 6; // [6, 6, 6, 6, 6]
}

import std.stdio はC,C++でいう #include <stdio.h> みたいなもの.厳密には違うけど,まぁそれは置いておいて.

writelnprintf のような標準出力関数です.writeln は改行が最後に勝手に入ります.write なら入りません.

writelnprintf と違って書式文字列("%s %s" みたいな)は使えませんが,writefln で同様に出来ます.

一般的な for も使えますが foreach も使えます.

C,C++などと違って,unsigned intuint です.短くて良い.

で,ar[0 .. 3] = 0 みたいに配列のここから,ここまで0を代入する,みたいなのが一行で分かりやすく書けます.

if などは他の言語と大体一緒です.

面白い機能の紹介

D言語には面白い(しかも便利)機能がたくさんあります.

などなど.

いくつか紹介します.

UFCS(統一関数呼び出し構文)

import std.stdio;

int inc(int a) {
  return a + 1;
}

void main() {
  int n = 1;
  writeln(inc(n)); // 2
  writeln(n.inc()) // 2
}

writeln(inc(n)) は普通ですね. writeln(n.inc()) に注目していただきたい.

UFCSとは関数の第1引数を関数の前に持ってきて,まるでメンバ関数のように振る舞うことが出来る構文です. これによりメソッドチェーンがやりやすくなり,見た目もよりキレイになります.

CTFE(コンパイル時関数実行)

import std.stdio, std.string, std.conv;

bool[] Eratosthenes(ulong N)() {
  bool[] is_prime = new bool[N + 1];
  is_prime[2 .. $] = true;

  for (ulong i = 2; i * i <= N; ++i) {
    if (is_prime[i]) {
      for (ulong j = i * 2; j <= N; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return is_prime;
}


void main() {
  // enumをつけることで,強制的にCTFEを発動させることが出来ます
  enum tmp = Eratosthenes!100000;
  write(">> ");
  auto n = readln.chomp.to!uint;
  writeln(tmp[n]);
}

readln.chomp.to!uint は標準入力から一行文字列を受け取って,改行を取り除き,uint に変換しています.

このプログラムはエラトステネスの篩という素数を列挙するアルゴリズムです. 通常,この計算はN が大きくなると計算が遅くなります.そこで,CTFE(コンパイル時関数実行)を用いると高速化が見込めます.

名前の通り,この機能はコンパイル時に関数を実行,つまり計算を行っています. これにより,実行時は列挙部分の計算は行わないため,高速化が可能です.

ただし,計算結果を埋め込むことになるので吐いたバイナリのサイズは大きくなります.

mixin

void main() {
  mixin("writeln(1);");
}

見慣れないものが出てきました. これをコンパイルして実行すると,1 と出力されます.

mixin は渡された引数の文字列をその場所にDのコードとして埋め込むことが出来ます. (条件がありますが,詳しい説明は省きます)

例えば,四則演算をする関数を作りたいと思ったとき.

int calc(string op)(int lhs, int rhs) {
  // Dでは~(チルダ)で文字列の連結が出来る
  return mixin("lhs" ~ op ~ "rhs");
}

void main() {
  writeln(calc!"+"(1, 2)); // 3
  writeln(calc!"-"(3, 1)); // 2
  writeln(calc!"*"(3, 4)); // 12
  writeln(calc!"/"(8, 2)); // 4
}

このようにすると関数を4つも書かなくて済みますね.

D言語に興味を持ったそこのあなた

D言語の公式ページでコードを実行して遊べます.ここ

Windows/Mac/Linux に対応してるので今すぐインストール. ここ

Windowsは上記のURLから飛んでインストーラ使って.

LinuxMacならスクリプトを叩く.

curl -fsS https://dlang.org/install.sh | bash -s

これらのD言語の魅力は使ってみて体感してください.特にC++ユーザーは気にいるはず.


明日はバターくんです.(誰かわからんぞ)

// ここに記事を貼る

Ubuntu18.04でneovim(or vim8)+LanguageClient-neovim+clangdでC++の補完をする

普段はMacで使ってますが,TwitterUbuntuで上手くいかなかった人がいるみたいなのでやってみました.

必須なやつ

インストール手順

dein.vimとneovimのインストール手順は省きます.(他に書いてる人がたくさんいるので)

clangd

clangも一緒にインストールしておきます

sudo apt install clang-6.0 clang-tools-6.0
sudo update-alternatives --install /usr/bin/clang++ clang++ /usr/bin/clang++-6.0 100
sudo update-alternatives --install /usr/bin/clang clang /usr/bin/clang-6.0 100
sudo update-alternatives --install /usr/bin/clangd clangd /usr/bin/clangd-6.0 100

LanguageClient-neovim

tomに書いてください.tomlに書いてない場合,適宜読み替えてください.

[[plugins]]
repo = 'Shougo/dein.vim'

# vim8用
[[plugins]]
repo = 'roxma/nvim-yarp'
if = "!has('nvim')"

# vim8用
[[plugins]]
repo = 'roxma/vim-hug-neovim-rpc'
if = "!has('nvim')"

[[plugins]]
repo = 'Shougo/deoplete.nvim'
hook_add = '''
let g:deoplete#enable_at_startup = 1
'''

[[plugins]]
repo = 'autozimu/LanguageClient-neovim'
rev = 'next'
depends = ['deoplete.nvim']
build = 'bash install.sh'
hook_add = '''
set hidden
let g:LanguageClient_serverCommands = {
      \ 'cpp': ['clangd'],
      \ }
let g:LanguageClient_loadSettings = 1
let g:LanguageClient_hasSnippetSupport = 0

set completefunc=LanguageClient#complete

nnoremap K :call LanguageClient#textDocument_hover()<CR>
nnoremap F :call LanguageClient#textDocument_formatting()<CR>
'''

結果

同様に,prabirshrestha/asyncomplete-lsp.vimを使ってもできます. これに関してはkutimoti氏が記事を書いてくれているのでどうぞ.

kutimoti.hatenablog.com

また,cquery-project/cqueryなどでも同様です.

kutimoti.hatenablog.com