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出たことなさそうだが)

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