ACM-ICPC 2016 Asia Tsukuba Regional 参加記

${5}$ 完で ${45}$ チーム中 ${27}$ 位でした...><
事前に対策していれば ${6}$ 完は出来たなぁという感じ.

結果はアレですが, 面白い問題がたくさん出題されて, ジャッジも安定していて良かったです.

とても前

国内予選は ${17}$ 位(学内 ${2}$ 位) を取って通過.

少し前

はじめてなので, 地区予選の参加フェーズをクリアするための段取りがよくわからない.

運営から英語のこわいメールが来て, どうやら Team Introduction Document と Team Introduction Slide を作って出す必要があるらしい. 辛いけどこれだけやればクリアした.

${1}$ 日目

${11}$ 時ごろ浜松駅を出発して ${14}$ 時過ぎにつくば駅に着く長い道のり. 東京駅まではそれはそう. そこからはじめて TX に乗った. さすがエクスプレスなだけにエクスプレス, 速い(それはそう

会場に着くと英語なのでつらい. 一応 ${1}$ 日目は電子機器は持ち込めた. 地区予選では公用語が英語なので任意のアナウンスやスライドやテキストは英語. hello world! を打つのが大変そう.

そのあと practice で ${3}$ 問解く. ここで気づいたのは, US 配列のキーボードということ(知ってたけど.

+や=を打ち間違えた回数∞に収束しそう
— しょし (@ei1333) October 15, 2016

みたいなUS 配列初心者＋数学初心者みたいなつぶやきをする. はじめて触ったので慣れない. あと practice の問題が難しくて解けない.

practice をしていると途中でスタッフがチーム紹介写真を撮影しに来た.

僕は既にTシャツ着用フェーズで間WAを生やしてdisqualifyなのでつらい
— しょし (@ei1333) October 15, 2016

ここで既に ${1}$ Wrong Answer を生やす.

終わるとバスで筑波大学へ移動し Welcome Party. 中でチーム紹介が行われるけど面白いチームは面白い.

ホテルに戻って ${1}$ 泊.

あああお風呂オーバーフローしてた＞＜
— しょし (@ei1333) October 15, 2016

そんなあなたに AIZU ONLINE JUDGE

ホテル初心者. ARC やろうとしたんだけど ${1}$ 問目からわからず提出が出来ない.

${2}$ 日目

起床時間にTLEが設定されているので気をつけて起きる. 8:45 からコンテストなの眠い.

A 問題

英語を読めない(絶望
しばらくするとチームメートが訳してくれたのでそれを聞く. 聞くと 3 秒考えて分かったので, 解法を @uoo38 さんに伝えて投げる. ~~予選の @uoo38 さんならバグらせると思ったけどすぐ通していてプロだった.~~ ここまで ${10}$ 分.

これは僕が後日書いたけど方針は同じ. 最後に先頭に持ってきた時刻を保存しておいて最後にソート.

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int N, M;
  scanf("%d %d", &N, &M);
  vector< int > ss(N);
  iota(begin(ss), end(ss), 1);
  for(int i = 0; i < M; i++) {
    int E;
    scanf("%d", &E);
    ss[--E] = -i;
  }
  vector< int > idx(N);
  iota(begin(idx), end(idx), 0);
  sort(begin(idx), end(idx), [&](int a, int b)
  {
    return (ss[a] < ss[b]);
  });
 
  for(int i = 0; i < N; i++) {
    printf("%d\n", idx[i] + 1);
  }
}

C 問題

ここから ${1}$ 時間なにもしてなくてこわい. なにしてたのか覚えていない. 寝てたのかな...><

C は問題概要を聞いてすぐDPだとわかったんだけど, これは伝達ミスで違う問題だったらしい. 1 WA. その後察して直して提出すると配列サイズが少なくて RE. すぐ直して AC(ここで引退を決断する(ここまで ${80}$ 分)

上限下限を持ってDP.

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int N, M;
  int dp1[200000], dp2[200000];
  vector< int > line[100001];
  iota(dp1, dp1 + 200000, 0);
  iota(dp2, dp2 + 200000, 0);
 
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    line[a].push_back(b);
  }
  for(int i = 0; i < 100001; i++) {
    for(auto& j : line[i]) {
      dp2[j - 1] = dp2[j];
      dp1[j] = dp1[j - 1];
    }
  }
  for(int i = 0; i < N; i++) {
    if(i > 0) putchar(' ');
    printf("%d", dp2[i] - dp1[i] + 1);
  }
  puts("");
}

B 問題

これは全探索するしかなさそうなのでする. サンプルが合わない. 入れ替えても同じ数字のときとか全然考えてなくてはまっていた(ここまで ${103}$ 分).

#include <bits/stdc++.h>
 
using namespace std;
 
int board[10][10];
 
char getE(string s)
{
  int now = s[0] - '0';
  for(int i = 1; i < s.size(); i++) {
    now = board[now][s[i] - '0'];
  }
  return (now + '0');
}
 
int main()
{
 
  for(int i = 0; i < 10; i++) {
    for(int j = 0; j < 10; j++) {
      cin >> board[i][j];
    }
  }
 
  int ret = 0;
 
  for(int i = 0; i < 10000; i++) {
    stringstream sss;
    sss << i;
    string s = "0" + sss.str();
    while(s.size() <= 4) s = "0" + s;
    s += getE(s);
 
    vector< string > kk;
    for(int j = 1; j < 6; j++) {
      for(char c = '0'; c <= '9'; ++c) {
        swap(c, s[j]);
        kk.push_back(s);
        swap(c, s[j]);
      }
      if(j > 1) {
        swap(s[j - 1], s[j]);
        kk.push_back(s);
        swap(s[j - 1], s[j]);
      }
    }
    sort(begin(kk), end(kk));
    kk.erase(unique(begin(kk), end(kk)), end(kk));
    bool f = false;
    for(string& t : kk) {
      if(t == s) continue;
      if(getE(t) == '0') f = true;
    }
    ret += f;
  }
  cout << ret << endl;
}

ここらへんでトイレに行きたくなった気がする. 英語がよくわからないけど Can I go to the toilet ?? って行ったら OK. っていわれた.

D 問題

${2}$ つの文字列の同じ長さの区間の文字種別の和をすべて同じにできるかどうかを判定する問題. 愚直に書いても間に合うでしょみたいな感じで ${O(N^3)}$ を出すと TLE(当たり前ソースを眺めていると ${O(N^2 \log N)}$ にできるのでする. 定数が 26 かかって, vector に set を突っ込んでいるので TLE かなぁとか思っていると通る(ここまで ${141}$ 分).

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
  string S, T;
  int sum1[4001][26] = {{}}, sum2[4001][26] = {{}};
 
  cin >> S >> T;
  for(int i = 0; i < S.size(); i++) {
    for(int j = 0; j < 26; j++) sum1[i + 1][j] = sum1[i][j] + (S[i] == j + 'a');
  }
  for(int i = 0; i < T.size(); i++) {
    for(int j = 0; j < 26; j++) sum2[i + 1][j] = sum2[i][j] + (T[i] == j + 'a');
  }
 
  vector< int > array(26);
  for(int i = min(S.size(), T.size()); i >= 0; i--) {
    set< vector< int > > sets;
    for(int j = 0; j <= S.size() - i; j++) {
      for(int k = 0; k < 26; k++) array[k] = sum1[j + i][k] - sum1[j][k];
      sets.insert(array);
    }
    for(int j = 0; j <= T.size() - i; j++) {
      for(int k = 0; k < 26; k++) array[k] = sum2[j + i][k] - sum2[j][k];
      if(sets.find(array) != sets.end()) {
        cout << i << endl;
        return (0);
      }
    }
  }
}

G 問題

順位表を見てみると G がよく解かれているので読む. 嘘解法のソースを ${4}$ 個生やして WA する. 闇だけど考え続けているとなんかAC(270 分).

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int N;
  scanf("%d", &N);
 
  multiset< int > sets;
  sets.insert(0);
  for(int i = 0; i < N; i++) {
    int depth;
    scanf("%d", &depth);
    auto p = sets.upper_bound(depth);
    if(p == sets.begin()) {
      puts("No");
    } else {
      int q = *--p;
      sets.erase(p);
      puts("Yes");
      for(int j = q + 1; j <= depth && sets.size() <= N; j++) {
        if(sets.size() == N && *--sets.end() > j) sets.erase(--sets.end());
        sets.insert(j);
      }
    }
  }
}

E 問題

Gと並列に E もやってた. こっちはチームメートが頑張ってたんだけど時間切れ＞＜構文解析を書けない.

#include <bits/stdc++.h>
 
using namespace std;
string temp = "01+-*()=";
 
int A(string&, int&);
 
int B(string&, int&);
 
int C(string&, int&);
 
int C(string& S, int& idx)
{
  int ret = 0;
  if(isdigit(S[idx])) {
    if(isdigit(S[idx + 1]) && S[idx] == '0') throw (0);
    while(isdigit(S[idx])) ret = ret * 2 + S[idx++] - '0';
  } else if(S[idx] == '(') {
    ret = A(S, ++idx);
    if(S[idx] != ')') throw (0);
    ++idx;
  } else if(S[idx] == '-') {
    ret = -C(S, ++idx);
  } else {
    throw (0);
  }
  return (ret);
}
 
int B(string& S, int& idx)
{
  int ret = C(S, idx);
  while(S[idx] == '*') {
    ret *= C(S, ++idx);
  }
  return (ret);
}
 
int A(string& S, int& idx)
{
  int ret = B(S, idx);
  while(S[idx] == '+' || S[idx] == '-') {
    if(S[idx] == '+') ret += B(S, ++idx);
    else ret -= B(S, ++idx);
  }
  return (ret);
}
 
int main()
{
  string S;
  int conv[32];
  memset(conv, -1, sizeof(conv));
 
  cin >> S;
 
  vector< char > num;
  for(char& c : S) {
    if(isalpha(c)) num.push_back(c);
  }
  sort(begin(num), end(num));
  num.erase(unique(begin(num), end(num)), end(num));
  for(int i = 0; i < S.size(); i++) {
    if(isalpha(S[i])) conv[i] = lower_bound(begin(num), end(num), S[i]) - begin(num);
  }
 
  if(num.size() > temp.size()) {
    cout << 0 << endl;
    return (0);
  }
  sort(begin(temp), end(temp));
 
  vector< string > ss;
  do {
    string T = S;
    for(int i = 0; i < S.size(); i++) {
      if(~conv[i]) T[i] = temp[conv[i]];
    }
    if(count(begin(T), end(T), '=') == 1 && T.front() != '=' && T.back() != '=') {
      ss.push_back(T);
    }
  } while(next_permutation(begin(temp), end(temp)));
  sort(begin(ss), end(ss));
  ss.erase(unique(begin(ss), end(ss)), end(ss));
 
  int ret = 0;
  for(string& al : ss) {
    string L = "", R = "";
    bool which = false;
    for(int i = 0; i < al.size(); i++) {
      if(al[i] == '=') {
        which = true;
        continue;
      }
      (which ? R : L) += al[i];
    }
    R += "$";
    L += "$";
    int idx;
 
 
    try {
      int ll = A(L, idx = 0);
      if(idx + 1 != L.size()) continue;
      int rr = A(R, idx = 0);
      if(idx + 1 != R.size()) continue;
      ret += ll == rr;
    } catch(int e) {}
  }
  cout << ret << endl;
}

ココらへんになると US 配列にも大分慣れた(遅い.

終わったら何やら解説っぽいやつをして結果発表. ${27}$ 位.

英語を読むのが遅い + 任意のコードにバグを埋め込んだみたいなことが反省点. チームの役割分担を明確にしたりとかしたいかなぁ. ICPC はそっちの方が重要な気がする. 来年以降まだ何回かチャンスがあるので修行します....

懇親会

ブースに企業が並んで色々やってる. 本とかグッズとかたくさん. 頭が悪いので任意の問題を解けない.

ei1333の日記

ぺこい