ICPC 国内予選 2016 - ei1333の日記

Mellorine というチームで ICPC国内予選2016に参加しました.

ABCDEを解いて5完で17位. 学内2位. おそらく通過できそうです. 6完セットだよね><

追記ー

順位と結果 | ACM-ICPC 2016 Asia Tsukuba Regional

通過しましたー.

前日まで

何をすればいいのか分からなかったので, Codeforcesに出たり, AOJ-ICPCの400までを上から埋めてました. 実装力の底上げに繋がったような気はしますが, Reading Englishの比重が大きかったり, 難易度的にも高くはなかったりとこれが役立ったかどうかは未知数.

Codeforces のレート推移. Div1に上がったのは偶然なのかよくわからない. このあと山を形成, 丘を形成どちらも有り得そう.
これ埋めたのは前日. 解法は分かるけど, 面倒な問題が多い...
AOJ-ICPCの400を埋めた図 pic.twitter.com/oYNgUgpMDZ
— ししょー (@ei1333) 2016年6月23日

当日開始前

さらに, 何をすれば分からなかったので, とりあえず飲み物を買ったり, TLを眺めてたりしました. 30分前くらいから環境を整え始める.

まだB1(初めての参加)でN回チャンスがあると思うと少しは気が楽.

3時間後の僕 pic.twitter.com/r5M7PyrOC1
— ししょー (@ei1333) 2016年6月24日
はい
.@ei1333 が携帯を手にしながらうろうろしている
— うおお (@uoo38) 2016年6月24日

本番

作戦

A, B, C くらいは流石に個人で解けるだろうということで, 3人でそれぞれ分担するように決めておきました. 僕はC.
D以降はその場の雰囲気でなんとかするという話でした.
環境は Cygwin + GNU Emacs.

問題文

http://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.html

ログみたいなもの

問題を印刷したかったので, 僕はプリンターくんのところへ向かう
プリンターくん, 競技室から微妙に距離があって部屋を出て20秒くらい
その裏で相方さんに A, B 問題を任せておく
きっと解いてくれるだろうと信じてるからね！？
C を読む
問題文の途中で, 「ん？難しそう...」とか思ったけど, 最後まで読むと, どう見ても”エラトステネスの篩”っぽくやれば良い
C があまりに自明で考察や実装方針がすぐ終わってしまったので D も読む
問題文はとてもわかりやすい
誰がどうみてもよくある区間DP
適当に再帰すれば解けるだろう... という感覚
E も読む
はい幾何つらい, 予選落ち
F を読む
日本語を理解する頭がないので問題が分からない
もう一回読む
分からない
はい予選落ち
A問題は難なく通されたらしい
B問題, うおおさん(仮名)が「エンバグのプロだなぁ」って言ってる
ちょっと整理してもらうことにして, 僕が Cを解く
瞬殺

#include <bits/stdc++.h>
using namespace std;
const int MAX = 7368792;

bool hogeeee[MAX] = {};
int main()
{
  int m, n;
  while(cin >> m >> n, m) {
    memset(hogeeee, false, sizeof(hogeeee));
    for(int i = m; ; i++) {
      if(!hogeeee[i]) {
        if(n == 0) {
          cout << i << endl;
          break;
        }
        for(int j = i + i ; j < MAX; j += i) hogeeee[j] = true;
        --n;
      }
    }
  }
}

D も実装する
実装が終わったところで, 数列をすべて消せるかどうかという問題に誤読していたことに気づく
諦めて再度相方に B を任せる
D 問題, 最大値でも同じような感じで行けそうだなぁということで漸化式を整理する
しばらくたつと B が通されたらしい
D を実装する
サンプルが通ったので出す
Wrong Answer(赤字)
ふぐーーーー
遷移が足りなかったみたい(悲しい
いらない遷移まで適当にやりすぎてバグる要素が多すぎ
ちょっとすると通る
以下は本番のソースより整理されています

#include <bits/stdc++.h>
using namespace std;

int N, A[300];
int dp[300][300];

int rec(int left, int right)
{
  if(left >= right) return(0);
  if(abs(A[left] - A[right]) <= 1 && rec(left + 1, right - 1) == right - left - 1) return(right - left + 1);
  if(~dp[left][right]) return(dp[left][right]);
  int ret = 0;
  for(int mid = left; mid < right; mid++) {
    ret = max(ret, rec(left, mid) + rec(mid + 1, right));
  }
  return(dp[left][right] = ret);
}

int main()
{
  while(cin >> N, N) {
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < N; i++) {
      cin >> A[i];
    }
    cout << rec(0, N - 1) << endl;
  }
}

25位
H問題を裏で考察していたらしいのでちょっと聞く
貪欲でうまくいかないかなぁという話になる
(貪欲というのは合ってたらしいけど, ) 問題文が短いし触れてはいけない問題と僕が断定してやめてしまった(ごめんなさい
G問題をちょっと考察する
どう見ても幾何要素がある
H問題以上に触れてはいけない問題なのでやめる
F問題も読む
相変わらず問題を理解できない
でも木の同型性判定だなぁという気はする(実はこれ合ってる
やはりE問題やるしかなさそう, 悲しい
一見やばそうな問題に見えるけど, ちょっと見てると枝分かれのないグラフになることがわかるので, 適当につながっているところを全通り見ればいいんじゃないかなぁぁという気持ち
(↑枝分かれのないグラフとかは選び方の制約だと思ってたけど, 入力でこのような制約を満たすものが与えられることを理解するまでにちょっと時間をかける)
表面積的な処理は相方さんに考えてもらって, それ以外の部分を実装する
何を考えたか強連結成分分解のライブラリを写経
前述の条件より明らかに不要, 焦ってるな....
消す
時間がないぽよ(残り45分くらい
ふと見ると相方さんによって共通部分の表面積の式が定義されている
あたふたしながら一応サンプル通った
ぼく「E問題だけにいーのでは」
ししょーさん「あっそういうこと言うと落ちるのでは」
っていう会話してたら本当にWrong Answer出てアレでした
— うおお (@uoo38) 2016年6月24日
はうーーー＞＜
血の気が引ける
一周して戻ってくることなどを失念していた(絶望
いろいろバグって諦める時間帯になって諦めたけど, なんかしらないけどいろいろやってたら終了 3 分前くらいにサンプルが通る
出す
Collect Answer
アツい
きたないけど当時のソースそのまま

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int N, K, S;
int x[2000], y[2000], z[2000];
bool used[2000];
vector< int > graph[2000];
bool connect[2000][2000];

const int Merge(int s, int t, bool sanopi = false)
{
  int xmin = INF, ymin = INF, zmin = INF;
  int xmax = -INF, ymax = -INF, zmax = -INF;
  bool flag = false;
  
  for(int l = 0; l < 2; l++) {
    swap(x[s], x[t]);
    swap(y[s], y[t]);
    swap(z[s], z[t]);
    for(int i = 0; i < 1 << 3; i++) {
      int xx = x[s] + S * ((i >> 0) & 1);
      int yy = y[s] + S * ((i >> 1) & 1);
      int zz = z[s] + S * ((i >> 2) & 1);
      if(x[t] <= xx && xx <= x[t] + S &&
         y[t] <= yy && yy <= y[t] + S &&
         z[t] <= zz && zz <= z[t] + S) {
        if(sanopi) flag = true;
        xmin = min(xmin, xx);
        ymin = min(ymin, yy);
        zmin = min(zmin, zz);
        xmax = max(xmax, xx);
        ymax = max(ymax, yy);
        zmax = max(zmax, zz);
      }
    }
  }
  if(sanopi) return(flag);
  return(((xmax - xmin) * (ymax - ymin)) +
         ((xmax - xmin) * (zmax - zmin)) +
         ((ymax - ymin) * (zmax - zmin)));
}

int first;
vector< int > ptrs;
int dfs(int idx, int sub)
{
  if(sub == 1) {
    int ret = 0;
    for(int i = 0; i < ptrs.size(); i++) {
      for(int j = i + 1; j < ptrs.size(); j++) {
        if(connect[ptrs[i]][ptrs[j]]) ret += Merge(ptrs[i], ptrs[j]) * 2;
      }
    }
    return(ret);
  }
  used[idx] = true;
  int ret = -INF;
  for(int to : graph[idx]) {
    if(used[to]) continue;
    ptrs.push_back(to);
    ret = max(ret, dfs(to, sub - 1));
    ptrs.pop_back();
  }
  used[idx] = false;
  return(ret);
}

main()
{
  while(cin >> N >> K >> S, N) {
    for(int i = 0; i < 2000; i++) {
      graph[i].clear();
    }
    memset(connect, false, sizeof(connect));
    for(int i = 0; i < N; i++) {
      cin >> x[i] >> y[i] >> z[i];
    }
    for(int i = 0; i < N; i++) {
      for(int j = i + 1; j < N; j++) {
        if(Merge(i, j, true)) {
          connect[i][j] = connect[j][i] = true;
          graph[i].push_back(j);
          graph[j].push_back(i);
        }
      }
    }
 
    int ret = -1;
    for(int i = 0; i < N; i++) {
      first = i;
      ptrs.push_back(i);
      ret = max(ret, dfs(i, K));
      ptrs.pop_back();
    }
    if(ret == -1) {
      cout << -1 << endl;
    } else {
      cout << 6 * S * S * K - ret << endl;
    }
  }
}

そのまま終わり
17 位を確認

まとめ

初めての参加だったのに予選を通過できたのは良かった
もう少しチーム戦っぽくやりたかったなぁといういつもの反省.
アジア予選までにもう少し力をつけなければ...
大室櫻子かわいい

追記

F解いた. 木の同型性, 文字列でソートしちゃえば簡単だった. どう見ても E より考える事が少ない...

#include <bits/stdc++.h>
using namespace std;
struct UnionFind
{
  vector< int > data;
  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }
  int find(int k)
  {
    if(data[k] < 0) return(k);
    else return(data[k] = find(data[k]));
  }
  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
};

int H, W;
string S[102];
vector< vector< int > > graph;
bool used[102 * 102];

string rec(int idx)
{
  vector< string > sss;
  for(int to : graph[idx]) sss.push_back(rec(to));
  sort(sss.begin(), sss.end());
  string s;
  for(string t : sss) s += t;
  return("(" + s + ")");
}

string getHash()
{
  cin >> H >> W;
  if(H == 0 || W == 0) exit(0);
  H += 2, W += 2;
  S[0] = S[H - 1] = string(W, '.');
  for(int i = 1; i < H - 1; i++) cin >> S[i];
  for(int i = 0; i < H - 1; i++) S[i] = "." + S[i] + ".";
  
  UnionFind uf(H * W);
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      const int p = i * W + j;
      if(j > 0 && S[i][j - 1] == S[i][j])   uf.unite(p - 1, p);
      if(i > 0 && S[i - 1][j] == S[i][j])   uf.unite(p - W, p);
      if(i > 0 && S[i - 1][j] == '#') {
        if(j > 0 && S[i][j - 1] == '#')     uf.unite(p - W, p - 1);
        if(j + 1 < W && S[i][j + 1] == '#') uf.unite(p - W, p + 1);
      }
    }
  }

  graph.resize(H * W);
  memset(used, false, sizeof(used));
  used[0] = true;
  for(int i = 0; i < H; i++) {
    for(int j = 1; j < W; j++) {
      int a = uf.find(i * W + j - 1), b = uf.find(i * W + j);
      if(a == b || (used[a] && used[b])) continue;
      if(used[a]) graph[a].push_back(b), used[b] = true;
      else        graph[b].push_back(a), used[a] = true;
    }
  }
  string hash = rec(0);
  graph.clear();
  return(hash);
}

int main()
{
  for(;;) cout << (getHash() == getHash() ? "yes" : "no") << endl;
}