CODE FESTIVAL 2016 Final 参加記

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

楽しかったです！！

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

会場到達フェーズ

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

コンテスト本番

パーカーを目標にします
— すし (@ei1333) November 25, 2016

${1600}$ 点までがパーカーで, 要するに ${4}$ 完 + 部分点.
高望みするような実力がないのでパーカーを目標.

A 問題

FA を狙いたかったんだけどね, サンプルが合わない.
snuke を sunuke と打っていてその挑戦は終わり.

#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);
  }
}