CodeFestival2016本戦の問題 - kazu0x17’s diary

この前Code Festival2016に行ってきました．問題はこんな感じでした．

A問題 Where's sunuke まあ，A問題なのでやるだけ問題です．

#include<iostream>
using namespace std;
 
int main(){
  int h, w;
  std::cin >> h >> w;
  string s;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      std::cin >> s;
      if(s == "snuke"){
        std::cout << (char)(j + 'A') << i + 1 << std::endl;
      }
    }
  }
  return 0;
}

B問題Exactly N points
どうせB問題もやるだけだろうと思って適当に貪欲解を投げたらWAでびっくり．一応一瞬考えたらにぶたんでできそうだけど，B問題でにぶたんが出るわけないと思い，貪欲解を適当にいじって2回提出してもなおWA．しょうがないからにぶたん書いてACしました．（B問題でにぶたんが出るようになったんだなぁ）

#include<iostream>
using namespace std;
 
bool check(int n, int maxi){
  for (int i = maxi; i > 0; i--) {
    if(n >= i){
      n -= i;
    }
  }
  return (n == 0);
}
 
int main(){
  int n;
  std::cin >> n;
  int l = 0, r = n, mid = (r + l)/2;
  while(r - l > 1){
    if(check(n, mid)){
      r = mid;
    }else{
      l = mid;
    }
    mid = (l + r)/2;
  }
  for (int i = r; i > 0; i--) {
    if(n >= i){
      std::cout << i << std::endl;
      n -= i;
    }
  }
  return 0;
}

C問題Interpretation
$M$種類の言語があり，$N$人の人がいます．それぞれの人が喋れる言語が与えられるので任意の人が喋れるかどうかを判定しろという問題です．通訳を頼んでもいいのである人AとBが共通に喋れる言語がなくても，AともBとも喋れるCさんがいればOKという問題です．
これは$N + M$のサイズの二部グラフ作って，グラフの連結性を判定すれば良いので結構簡単．

#include<iostream>
#include<vector>
using namespace std;
 
void dfs(vector<vector<int> > &g, vector<bool> &used, int v = 0){
  used[v] = true;
  for (int i = 0; i < g[v].size(); i++) {
    if(used[g[v][i]] == true)continue;
    dfs(g, used, g[v][i]);
  }
}
 
int main(){
  int n, m, k;
  std::cin >> n >> m;
  vector<vector<int> > l(n + m);
  for (int i = 0; i < n; i++) {
    std::cin >> k;
    for (int j = 0; j < k; j++) {
      int tmp;
      std::cin >> tmp;
      l[i].emplace_back(tmp - 1 + n);
      l[tmp - 1 + n].emplace_back(i);
    }
  }
  vector<bool> used(n + m, false);
  dfs(l, used);
  bool flag = true;
  for (int i = 0; i < n; i++) {
    flag &= used[i];
  }
  std::cout << ((flag == true)?"YES":"NO") << std::endl;
  return 0;
}

D問題 Pair Cards
この辺から結構難しく感じました．ある種の最大マッチング問題としても解けるけど，一般のグラフの最大マッチングは頂点数$N$に対して，$N^{2.5}$が最速だったと思うので，どう考えても無理．（しかも1，2時間で実装できるわけがない）．なので，制限されたグラフクラスのマッチングなのかと思い，グラフを書いてたりしてたら，整数の和が$M$になるようなペアを作りたいので，与えられた整数を$M$でmodをとって，その値が同じなら同じ整数と考えてもいいことに気づく．なので，後は$M$でmodとった値が$i$の整数と$M- i$の整数をペアにしていけばいいことがわかる．ただし，まだ同じ整数のペアの数は考慮できていないので，この方法でペアを作って，余った整数で同じ整数があったらそのカード同士をペアにする必要がある．

#include<iostream>
#include<vector>
#include<set>
using namespace std;
 
int main(){
  int n, m, maxi = 0;
  std::cin >> n >> m;
  vector<int> x(n);
  for (int i = 0; i < n; i++) {
    std::cin >> x[i];
    maxi = max(maxi, x[i]);
  }
  vector<int> mod(m, 0);
  for (int i = 0; i < n; i++) {
    mod[x[i]%m]++;
  }
  int ans = 0, tmp;
 
  for (int i = 1; 2*i <= m; i++) {
    if(2*i == m){
      tmp = mod[m/2]/2;
      ans += tmp;
      mod[m/2] -= tmp*2;
    }else{
      tmp = min(mod[i], mod[m - i]);
      ans += tmp;
      mod[i] -= tmp;
      mod[m - i] -= tmp;
    }
  }
  tmp = mod[0]/2;
  ans += tmp;
  mod[0] -= tmp*2;
  vector<int> s(maxi, 0);
  for (int i = 0; i < n; i++) {
    s[x[i]]++;
    if(s[x[i]] >= 2 and mod[x[i]%m] >= 2){
      s[x[i]] -= 2;
      mod[x[i]%m] -= 2;
      ans++;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}

E問題Cookies
この問題はコンテスト中は部分点しか取れなかったです．制約を見て，dpなら部分点は取れると思い，dpの方針で考えてました．考えたいたdpは「ちょうど$k$枚のクッキーを焼くのにかかる時間は何分か?」というdpを考えました．コードはこんな感じです．

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long int lli;
 
int main(){
  lli n, a;
  std::cin >> n >> a;
  vector<lli> cost(n + 1, 1e9);
  cost[0] = 0;
  cost[1] = 1;
  for (lli i = 2; i <= n; i++) {
    cost[i] = min(cost[i], (lli)i);
    for (lli j = 2*i; j <= n; j+=i) {
      cost[j] = min(cost[j], cost[i] + j/i + a);
    }
  }
  lli ans = n;
  for (int i = 1; i <= n; i++) {
    ans = min(ans, (lli)(ceil(n/double(i)) + cost[i] + a));
  }
  std::cout << ans << std::endl;
  return 0;
}

とりあえずこれで$O(N log N)$にはなっているとおもいます（計算量解析はあまりきちんと考えていないけど多分あっている気がする．）コンテスト中はここまでしかわかりませんでした．

コンテスト後，解説を見ながら「頭いいなぁ」と感心しながらコードを書いて次のコードでACしました．コードがpythonなのはC++でオーバーフローを機にするのが面倒だったのでpythonで書きました．

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
def pow(a, b):
    if b == 1:return a
    if b%2 == 0: return pow(a*a, int(b/2))
    return a*pow(a*a, int(b/2))
 
def binaryOne(n, multi):
    l, r = 0, n
    mid = (l + r)/2    
    while r - l > 1:
        if pow(mid, multi) >= n:
            r = mid
        else:
            l = mid
        mid = (r + l)/2
    return r;
 
 
def binaryTwo(n, maxi, multi):
    l, r = 0, multi
    mid = (l + r)/2
    while r - l > 1:
        if pow(maxi, (multi - mid))*pow(maxi - 1, mid) >= n:
            l = mid
        else:
            r = mid
        mid = (r + l)/2;
    return l
 
n, a = map(int,raw_input().split(" "))
ans = 1e18
for i in xrange(0, 40):
    maxi = binaryOne(n, i + 1);
    subt = binaryTwo(n, maxi, i + 1)
    ans = min(ans, a*i + maxi*(i + 1) - subt)
    
print ans

今年もパーカーをゲットできたので非常に良かったです．今年はパーカーラインが去年より高めで，半分くらいの人しかパーカーをもらってなかったぽいです．