ei1333の日記

ぺこい

CODE FESTIVAL 2016 Final 参加記

CODE FESTIVAL 2016 Final に参加してきました.

楽しかったです!!

関係者, 参加者の皆さんありがとうございました!!

会場到達フェーズ

  • 浜松東京間はさすがに自明. 自由席だったけどちゃんと座れた.
  • 東京で山手線に乗り換え. これも自明.
  • 東京新橋間がよく見聞きする都会の満員電車のアレ. 位置がよかったので簡単に乗り降りできた.
  • 着いたら交通費精算してまもなくコンテスト本番.
  • 参加賞の T シャツを得た.
  • 昼食が用意されていてかなり嬉しかった.

コンテスト本番

  •  {1600} 点までがパーカーで, 要するに  {4} 完 + 部分点.
  • 高望みするような実力がないのでパーカーを目標.
A 問題
  • FA を狙いたかったんだけどね, サンプルが合わない.
  • snukesunuke と打っていてその挑戦は終わり.
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int H, W;
 
  cin >> H >> W;
 
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      string S;
      cin >> S;
      if(S == "snuke") {
        cout << (char) ('A' + j) << i + 1 << endl;
        return (0);
      }
    }
  }
}
B 問題
  • 一分くらい考えた.
  •  {1} から  {i} までの和について, 最初に  {N} を超えた  {i} を難易度が最大の問題とすればいいことがわかる.
  • あとは適当に大きいほうから順番に使っていけば, いい感じに存在するのでOK.
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int N;
  cin >> N;
  for(int i = 1; i <= N; i++) {
    if(1LL * i * (i + 1) / 2 >= N) {
      for(int j = i; j >= 1; j--) {
        if(N - j >= 0) {
          N -= j;
          cout << j << endl;
        }
      }
      return (0);
    }
  }
}
C 問題
  • これはすぐわかった.
  • どこかで何度か似たものを見たことありそう.
  • 言語と人に対してグラフを張れば連結判定なので UnionFind.
#include<bits/stdc++.h>
 
using namespace std;
 
struct UnionFind
{
  vector< int > data;
 
  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }
 
  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 find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k)
  {
    return (-data[find(k)]);
  }
};
 
int main()
{
  int N, M;
  cin >> N >> M;
 
  UnionFind uf(N + M);
  for(int i = 0; i < N; i++) {
    int K;
    cin >> K;
    for(int j = 0; j < K; j++) {
      int L;
      cin >> L;
      uf.unite(--L, M + i);
    }
  }
  int root = uf.find(M);
  for(int i = 0; i < N; i++) {
    if(root != uf.find(M + i)) {
      cout << "NO" << endl;
      return (0);
    }
  }
  cout << "YES" << endl;
}
D 問題
  • とりあえず  {\mod M} でえいってやりそう.
  • 頭を失ったので, 条件の  {2} 枚のカードに書かれた整数が同じである を,  {2} 枚のカードに書かれた整数  {\mod M} が同じである と同値だと思ってしまった.
  • さらに無思考で二部グラフの最大マッチングのライブラリをコピペして提出.
  • 無限にWA.
  • わからず(完)
  •  {20} 分くらい頭がないつらい><ってなってたと思うんだけど, さすがに同値じゃないことに気づく.
  • これに気づいたら勝ち.
#include<bits/stdc++.h>
 
using namespace std;
 
 
int main()
{
  int N, M;
  map< int, int > xs[100001];
  int sum[100001] = {};
 
  cin >> N >> M;
 
  for(int i = 0; i < N; i++) {
    int X;
    cin >> X;
    xs[X % M][X]++;
    sum[X % M]++;
  }
 
 
  int ret = sum[0] / 2;
 
  for(int i = 1; i <= M - i; i++) {
    if(i == M - i) {
      ret += sum[i] / 2;
      break;
    }
 
    int one1 = 0, one2 = 0;
 
    priority_queue< int > p, q;
 
    for(auto &a : xs[i]) {
      if(a.second / 2 > 0) p.push(a.second / 2);
      one1 += a.second % 2;
    }
    for(auto &a : xs[M - i]) {
      if(a.second / 2 > 0) q.push(a.second / 2);
      one2 += a.second % 2;
    }
    while(one1 > 0 || one2 > 0) {
 
      if(one1 == 0) {
        if(p.empty()) break;
        int k = p.top() - 1;
        p.pop();
        if(k > 0) p.push(k);
        one1++;
      } else {
        --one1;
      }
 
      if(one2 == 0) {
        if(q.empty()) break;
        int k = q.top() - 1;
        q.pop();
        if(k > 0) q.push(k);
        one2++;
      } else {
        one2--;
      }
 
      ++ret;
    }
 
    while(!p.empty()) {
      ret += p.top();
      p.pop();
    }
    while(!q.empty()) {
      ret += q.top();
      q.pop();
    }
  }
  cout << ret << endl;
}
E 問題
  • パーカーを得るためには E の部分点.
  • 頭を失ったまま戻ってこないので分からない(もうちょっと冷静になろうね><
  • とりあえず深さの全探索を書く, TLE.
  • dp[時刻]:= 最大のお菓子生産量みたいに定義すると, 気合で漸化式を立てることができるため出すと  {O(N^2)} のため TLE.
  • 漸化式をよく見るとお菓子生産量が時刻に対する一次式になっている, すなわち直線なので Convex Hull Trick が使えないかなぁってなる(今まで使ったことないけど.
  • 適当にライブラリを貼り付けて提出するとやっと部分点.
  • 満点までは 2ケース TLE.
  • このまま終了.
  • 想定解は dp[お菓子]:= 最小時間 を改善するらしくてそれはそうという気持ちになったけど, こっちでもちょっと頑張れば一応通るらしいね.
#define long long
signed main()
{
  int N, A;
  cin >> N >> A;
  if(N == 1) {
    cout << 1 << endl;
    return (0);
  }
  if(N <= A) {
    cout << N << endl;
    return (0);
  }
 
  ConvexHullDynamic cht(1);
  cht.addLine(1, 0);
 
  for(int j = A; true; j++) {
    if(cht.getBest(j) >= N) {
      cout << j << endl;
      return (0);
    }
    int val = cht.getBest(j - A);
    cht.addLine(val, -val * j);
  }
}
  •  {96} 位でした...
  • これはもう歳ですね><周りについていけない.
  •  {2000} 点のため目標としていたパーカーはゲット.

tourist 氏によるトークライブ

  •  {7} 歳から始める競技プログラミング.
  • tourist というハンドル名はスキーの板が原点なのか.
  • メールで書いてあった質問例をそのままコピペして投稿した「どうやって強くなったの?」が採用されてた.
  • "gifted" brain は不要.
  • 当然僕は "gifted" blain を持ち合わせていないので参考になる(?
  • などなど...

秋葉さんによる続・ペアプロ

  • 今年のICPCの企業ブースでみた問題.
  • 最後流れが変わってACするところがアツい.

夕食

  • 寿司!ピザ!!肉!!!

エキシビジョンマッチ

  • すごい(すごい.
  • 異常な速度でプログラムが書かれている...
  • 海外勢はこわいエディタ.

ホテル

  • セットしたはずの目覚ましが鳴らなかったので, 気持ちよく寝ることができた.
  • ここまで書けば気づける罠なんだけど, 受付時間TLEと隣り合わせ.
  • 受付時間の  {8} 時に奇跡的に目が覚めたのでよかった.

トーナメント

  • トーナメント思っていたより面白い
  • 但し疲れる...
Round 1
  •  {30} 分コンテストってどんな感じだろう(わくわく
  • B は二分探索で頑張ればいけそうだぞい!!ってなったので二分探索を実装する.
  • 無限にバグる(そもそも値で二分探索は出来ないことに気づいていなかったので
  • あたふたしていると残り  {10} 分.
  • 正の点を得ないとまずいと思い, とりあえず 10 秒でコードを書いて残り  {10} 分で  {100} 点を得る.
  • 諦めて A を全力で実装するものの間に合わなかったよねー.
  •  {100} 点しか得られなかった(ウケる.
  •  {4} 位で通過(マジか...
  • 僕も致命的にアレだけど, 皆も慣れてなさそう.
Round 2
  • 通過したので Round2.
  • 自分の知能の程度を学習したので自明な部分点だけを得ることにする.
  • A を見たけど苦手そうだったので B を見ると実装するだけで  {200} 点を得れそう.
  • 途中で順位表を見ると, 僕以外の皆が A の部分点を得ていて焦る.
  • 結局 A と B の部分点を得て  {400} 点.
  •  {3} 位で通過.
Round 3
  • 通過したので Round3.
  • A のDPを無限にバグらせていたら  {20} 分くらい経過.
  • 部分点  {200}.
  • 見るとセグ木にできるので直す.
  • 部分点  {500}.
  • 見るとスライド最小値なので直そうとする.
  • わからない.
  •  {4} 位.

休憩時間

  • (どのイベントと対応するかは察してください)
  • 某D社は山で強いらしい.
  • 擬人化すき.
  • 動いた.
  • 投影機に嫌われていそう.
  • ハンドスプリングは自然にできる!
  • ハンドスプリングつよい!
  • 座布団が持ち込まれている.
  • 本家サイトが間違っている...
  • RGB.
  • 競プロが強い人は, 地理にも詳しい.
  • 座布団が積まれている.
  • いくらが乗ったごはんおいしい.

チームリレー

  • Team D.
  • チームメンバーで明らかに強い人が  {n} 人いる.
  • 海外の方は FatalEagle 氏. やはり明らかに強い.
  • まず文字 E が書かれた問題が入った封筒が配られた.
  • Team D なので D じゃなくていいのかみたいに一瞬なった.
  • 後に文字 J が書かれた封筒も来るわけだが Japaanse と English の略らしい.
  • 作戦タイム中に, ABCDE問題, FGH問題, IJK問題を解く小グループ(5人, 3人, 3人) に分割された.
  • 僕は真ん中のグループで他に siotouto 氏, beet 氏が小グループのメンバーだった.
  • とりあえず G 問題を読んだら誤読した(ごめんなさい><.
  • 解法はすこし考えるくらいで難しくないのでGを実装してAC.
  • beet 氏が「えいってやる」って言ってたのだけしか覚えてない.
  • F 問題と H 問題も読んだけどあまり貢献できなかった...
  • 一方でチーム全体では非常に素晴らしくて, 全体では  {2} 位(プロ)!

f:id:ei1333:20161128193215p:plain

閉会

  • 腕立て伏せ.
  • 劣モ.

帰宅フェーズ

  • 雨><.

来年も参加できたら!!(これは罠で厳しい競争社会に生き残れないため予選落ちする.