読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

ICPC 国内予選 2016

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

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

追記ー

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

通過しましたー.

前日まで

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

  • Codeforces のレート推移. Div1に上がったのは偶然なのかよくわからない. このあと山を形成, 丘を形成どちらも有り得そう.
    f:id:ei1333:20160625134707p:plain

  • これ埋めたのは前日. 解法は分かるけど, 面倒な問題が多い...

当日開始前

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

本番

作戦

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分くらい
  • ふと見ると相方さんによって共通部分の表面積の式が定義されている
  • あたふたしながら一応サンプル通った
  • はうーーー><
  • 血の気が引ける
  • 一周して戻ってくることなどを失念していた(絶望
  • いろいろバグって諦める時間帯になって諦めたけど, なんかしらないけどいろいろやってたら 終了 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;
}