ICPC 2018国内予選

Posted on 6 mins read

2018/7/6にICPCという競技プログラミングの大会の国内予選に参加してきました。
記録がてら少し書いておこうと思います。

メンバー

チーム名: Girigiri
学科の友達と、その友達の3人で参加しました。
役割としては、一人が実装メイン(以下実装マン)、もう一人が考察メイン(以下考察マン)、
自分はその中間かつ応援係(笑)、という感じでした。

練習

3人で集まり、本番と同じ環境(PCは1台のみ、インターネット使用禁止、時間は3時間)で過去問を解く練習を何回かやりました。
やったのは以下。

  • 国内予選2016
  • 国内予選2015
  • 国内予選2014(途中まで)
  • 国内予選2013
  • 模擬国内予選2016A
  • 模擬国内予選2016B
  • 模擬国内予選2018

振り返ってみると結構練習してますね。
特に、自分は普段はめちゃくちゃググりながらプログラミングをする人なので、C++を空で書くいい練習になったと思います。
また3人がどのように振る舞うかという戦略も重要で、それも過去問をやっていくうちに固まっていきました。

目標

全部で44チームまで予選を通過できるのですが、同じ大学内で出られるチーム数に制限があり、東大のチームが予選を突破するには実質10位に入る必要がありました。
最低目標としては、自分たちより下の順位のチームで予選を突破しているチームがいるぐらいの順位は取りたいと思っていました。

また、練習の結果などから、本当に上手く行けば1割ぐらいの確率で予選突破できるのではないかなどと考えていました。

戦略

問題はAから始まり例年6-8問程度で、基本的に簡単な順に並んでおり、以下のような戦略をとりました。

まず問題を全部プリントアウト。
実装マンがA-Bを通す。
自分はCを読みやるだけかどうかを判断。
やるだけだったらD以降の考察に移り、実装マンがA, Bを通したらCの実装方法を伝える。
Cが大変そうだったら解法を詰めておき、PCが空き次第自分で実装。
考察マンはEから読み始め、解法がわかった問題について実装マンもしくは自分の空いている方に解法を伝え、PCが空き次第一緒に実装する。

これでうまく回れば(問題数-2)問程度正解できるのではと思っていました。

本番

開始直後に実装マンが問題のプリントに行くため、残った二人でまずCを読む。
考察マンが一瞬でCの解法を思いつく。
実装マンが帰ってくるのでA, Bを任せ、自分は考察マンから聞いた解法で紙上で実装を詰めておく。
Aは一瞬で通るが、Bで少し詰まっているようだったので、考察マンからDが全探索で通りそうという話を聞く。
Dの実装方針も紙上で詰める。
Bがバグっているらしくプリントデバッグへ。
その間にCを実装し、少しバグらせながらBとCを交代してパソコンを使いながらCをAC。
その後少しして実装マンがBを通す。
自分がDの実装に入り、その間に実装マンが考察マンからEの解法を聞いている。
Dをなんとか通し、残り45分程度。
2人がEを通してくれることを祈りながら自分はF以降の問題を読む。
Eは考察に少し欠陥があったこと実装中に気づいたようだが、それを修正しきれずにタイムアップ。
CとDのソースコードは末尾に添付しておきます。

振り返って

他のチームの結果なども見る限り、Bの実装が大変だったようですね。 一人にBとEの実装を担当させてしまったので大変そうでした、、 それでも全体的には、最低限の目標はクリアできたかなという感じです。
考察マンがCの解法を一瞬で思いついた(というか既知だった)のは本当に助かりました。
結論から言うと、自然数Nを連続した自然数の和で表す場合の数は、Nの奇数の約数の個数と一致します。綺麗ですね。

本番中のハプニングは2つあって、1つめは、問題文をプリントした際にテストケースがプリントされなかったことです。
実装中はPCを使って問題を確認できるので良いのですが、考察は印刷された紙を見て行うので、考察マンが辛そうでした。
これがなければEの考察も完全に進められてたのかなー、とは思います。

また、回答を提出する際にテストケースに対するアウトプットとプログラムを両方提出するのですが、一度プログラムを別のファイルを提出してしまうことがありました。
それを2回連続で一致させなければならず、3回以上失敗してしまうと用意されているテストケースがなくなりその問題を回答することができなくなってしまうという仕様でした。
どうやら2回目の提出が間違っていたようで、4回目に初めて前回とプログラムが一致したので(oxooという順番)やっとACになり、このときは焦りました。

感想

とにかく楽しかったです！！！
自分は一人で競プロのコンテストに参加してもあまりモチベーションが出ないのですが、友達と協力して問題を解くというのは本当に青春という感じがしてワクワクしました。
来年も参加したいです。

ソースコード

  • C問題
    bの奇数の約数について全部見ていきます。
#include <bits/stdc++.h>
using namespace std;

int b;
int l, r;

void check(int p, int q) {
  if (q - (p / 2) >= 1) {
    if ((r - l + 1) < p) {
      l = q - (p / 2);
      r = q + (p / 2);
    }
  } else {
    if ((r - l + 1) < 2 * q) {
      l = (p / 2) - q + 1;
      r = q + (p / 2);
    }
  }
}

void solve() {
  for (int i = 1; i * i <= b; i++) {
    if (b % i) { continue; }
    int j = b / i;
    if (i % 2) {
      check(i, j);
    }
    if (j % 2) {
      check(j, i);
    }
  }
  cout << l << ' ' << r - l + 1 << endl;
}

int main() {
  while (1) {
    cin >> b;
    if (b == 0) { return 0; }
    l = 1; r = 0;
    solve();
  }
}
  • D問題
    全探索します。
    各行について(空いているマス)C(必要な勝ち数)のコンビネーションを全列挙するという方針で実装しているのですが、
    2n2通り(対角成分と対象な成分を考えると実際は2((n-1)2) / 2通り)を枝刈りしながら全探索するという方針の方が単純に書けることに後で気づきました。
#include <bits/stdc++.h>
using namespace std;

void print(vector<vector<int>>& t) {
  for (auto x: t) {
    for (auto y: x) {
      cout << y << ' ';
    }
    cout << endl;
  }
  cout << endl;
}

int n, m;
int count (vector<vector<int>>& table, int i) {
  int zero = 0;
  int won = 0;
  for (int j = 0; j < n; j++) {
    if (table[i][j] == 0) { zero++; }
    else if (table[i][j] == 1) { won++; }
  }
  int more = n / 2 - won;
  // check
  if (more < 0 || zero < more) { return 0; }
  if (i == n - 1) { return 1; }

  if (more == 0) {
    vector<vector<int>> new_table(table);
    for (int j = 0; j < n; j++) {
      if (new_table[i][j] != 0) { continue; }
      new_table[i][j] = -1;
      new_table[j][i] = 1;
    }
    return count(new_table, i+1);
  }

  int comb = (1 << more) - 1;
  int ans = 0;
  while (comb < 1 << zero) {
    vector<vector<int>> new_table(table);
    int xx = 0;
    for (int j = 0; j < n; j++) {
      if (new_table[i][j] != 0) { continue; }
      if ((1 << xx) & comb) {
        new_table[i][j] = 1;
        new_table[j][i] = -1;
      } else {
        new_table[i][j] = -1;
        new_table[j][i] = 1;
      }
      xx++;
    }
    ans += count(new_table, i+1);
    //
    int x = comb & -comb, y = comb + x;
    comb = ((comb & ~y) / x >> 1) | y;
  }
  return ans;
}

int main() {
  while (1) {
    cin >> n >> m;
    if (n == 0) { return 0; }
    vector<vector<int>> table(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i == j) { table[i][j] = -100; }
        else { table[i][j] = 0; }
      }
    }
    for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      table[a-1][b-1] = 1;
      table[b-1][a-1] = -1;
    }
    cout << count(table, 0) << endl;
  }
}