Xmas Contest 2011

Xmas Contest 2011に出ました。
375点で16位でした。自分の実力を考えるとなかなかの順位だったと思います。
一風変わった問題が多くて面白かったです。
(と言うか典型問題がなかったと言ったほうが正しいかも)
難易度は高めだったと思うのですが、上位はほぼ全完に近い結果で実力の差を感じます。

以下各問題を解くときに考えてたこととか解法とかを時系列順に。

A: input

一番最初に開いて、早解きを意識するあまり問題文を読み間違える。
出力から入力を作るという問題だったのに、普通に入力から出力を作る解を提出。当然WA。
考えるも解法が分からないので飛ばす。

E: accepted

k_operafanさんが早くもEを解き終えていたので簡単な問題だろうと思い開く。
これ、「accepted」の数数えるだけじゃね?→WA。
どうやら問題名にacceptedが許されるらしい。
「なんか連立方程式のような気がするけど、探索でごまかそう」と思ってしまったのが運の尽き。
全く解けなくて非常に焦る。
とりあえず紙に書いて落ち着いて考えたら連立方程式がめっちゃ簡単だったのでそれで提出。AC。

#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
  map<string,int> cnt;
  set<string> bad;
  string str;
  int n, l; cin >> n >> l;

  cout << 3 * l - n << endl;

  return 0;
}
B: shortest path

次にみんなが解いてたB問題へ。
ダイクストラ臭しかしないので書いてみる。
各点から全点に行けると思ってしまうと計算量が多すぎる。
この問題の場合には基本的には左右にしか行かないと思っても大丈夫ということに気づいて実装。AC。

#include <cstdio>
#include <set>
#include <iostream>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

typedef long long ll;

using namespace std;

vector<pair<int, int> > ab[100000];

bool memo[100000];

int main(){
  int n = getInt();
  int m = getInt();
  int d = getInt();
  int s = getInt();
  int t = getInt();

  REP(i,m){
    int a = getInt();
    int b = getInt();
    int c = getInt();

    ab[a].push_back(make_pair(b, c));
    ab[b].push_back(make_pair(a, c));
  }

  typedef pair<ll, int> data;
  priority_queue<data, vector<data>, greater<data> > pq;
  pq.push(make_pair(0, s));

  while(pq.size()){
    data dt = pq.top(); pq.pop();
    ll cost = dt.first;
    int pos = dt.second;

    if(memo[pos]) continue;
    memo[pos] = true;

    if(pos == t){
      cout << cost << endl;
      break;
    }

    REP(i,ab[pos].size()){
      int next = ab[pos][i].first;
      ll cc    = cost + ab[pos][i].second;
      if(!memo[next])
        pq.push(make_pair(cc, next));
    }

    if(pos != 0 && !memo[pos - 1])
      pq.push(make_pair(cost + d, pos - 1));
    if(pos != n - 1 && !memo[pos + 1])
      pq.push(make_pair(cost + d, pos + 1));
  }


  return 0;
}
D: unbalanced

解けそうな問題を探していたらこの問題が解けそうだった。
文字列を前からと後ろから見ていってDPできそうだと思い書いてみる→WA。
空文字列が悪さをしているような気がするのでどうしようか悩む。
とりあえずスモールケースを解くプログラムを書いて提出→AC。
このプログラムを使ってどういうケースで間違えているのかを確認する。
やはり空文字列を返した場合にうまく行かない場合がありそうなので対策を考える。
最終的には、辞書順でいいものを数個返すDPにすることでAC。

#include <set>
#include <iostream>
#include <vector>
#include <algorithm>

#define REP(i,n) for(int i=0; i<(int)(n); i++)


using namespace std;

string s;
vector<string> memo[100][100];
bool check[100][100];

void update(string &r, const string &s){
  r = min(r, s);
}

vector<string> ret0;

vector<string> solve(int p1, int p2){
  if(p1 > p2){
    return ret0;
  }
  if(check[p1][p2])
    return memo[p1][p2];

  check[p1][p2] = true;

  vector<string> ret;

  if(s[p1] == s[p2]){
    vector<string> tmp = solve(p1 + 1, p2 - 1);
    REP(i,tmp.size()) ret.push_back(tmp[i]);
  }

  {
    vector<string> tmp = solve(p1 + 1, p2);
    REP(i,tmp.size()) ret.push_back(s[p1] + tmp[i]);
  }

  {
    vector<string> tmp = solve(p1, p2 - 1);
    REP(i,tmp.size()) ret.push_back(tmp[i] + s[p2]);
  }

  sort(ret.begin(), ret.end());
  unique(ret.begin(), ret.end());
  if(ret.size() > 20) ret.erase(ret.begin() + 20, ret.end());

  return memo[p1][p2] = ret;
}

int main(){
  cin >> s;

  ret0.push_back("");
  string ans = solve(0, s.size() - 1)[0];

  cout << ans << endl;
  return 0;
}
A: input

もうラージケースの解法が分かる問題がなさそうだったのでスモールケース解けるものをとりあえず解いていく方針に。
この問題のスモールケースでは、素因数分解をするだけでよいので早々AC。
このあとの問題はAのラージケースを考えつつ解いていく。

#include <iostream>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;

string gen(int i){
  string ret = "a";

  while(i){
    ret = ret + (char)(i % 20 + 'a');
    i /= 20;
  }

  return ret;
}

int main(){
  int x; cin >> x;
  vector<int> cnts(160);
  int cnt = 0;

  if(x == 1){
    cout << "1" << endl;
    cout << "ahoge" << endl;
  }else{
    for(int i = 2; i < 160; i++){
      while(x % i == 0){
        x /= i;
        cnts[i]++;
        cnt += i;
      }
    }

    if(x == 1 && cnt <= 150){
      int id = 0;
      cout << cnt << endl;
      REP(i,160) if(cnts[i]){
        REP(j,cnts[i]){
          REP(k, i){
            cout << gen(id) << endl;
          }
          id++;
        }
      }
    }else{
      cout << "NO" << endl;
    }
  }
  return 0;
}
F: flying snowman

スモールケースはビットDPでできそう→AC。
ラージケースの場合は、1≦M≦Nなのでやばい点は少なさそうなのでどうにかできないか考えるも、実装できそうな案が思い浮かばなかった。

#include <climits>
#include <set>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

int dp[15][1 << 15];
int n, m, d;
int cost[15][15];

int main(){
  n = getInt();
  m = getInt();
  d = getInt();

  if(n > 15){puts("muripo"); return 0;}

  REP(i,n) REP(j,n) cost[i][j] = d;

  REP(i,m){
    int a = getInt();
    int b = getInt();
    int c = getInt();

    cost[a][b] = cost[b][a] = c;
  }

  REP(i,n) REP(j, 1 << n) dp[i][j] = INT_MAX;

  dp[0][1] = 0;

  REP(j,1<<n){
    bool update = true;
    while(update){
      update = false;
      REP(i,n) if(dp[i][j] != INT_MAX){
        REP(k, n){
          int &tmp = dp[k][j | (1 << k)];
          int tmp2 = dp[i][j] + cost[i][k];

          if(tmp > tmp2){
            tmp = tmp2;
            update = true;
          }
        }
      }
    }
  }

  printf("%d\n", dp[0][(1 << n) - 1]);

  return 0;
}
G: snowy bunny

スモールケースは全探索すればできそう→AC。
ラージケースは何も思い浮かばないので早々諦めました。

#include <cstdio>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

int m, n, a, b;
int x[1001];
vector<int> xs;
int y[1001];

int wariate[4];

int henkan(int k){
  int ret = 0;
  REP(i,m) if(k & (1 << i)){
    ret |= wariate[i];
  }
  // printf("%d => %d\n", k, ret);
  return ret;
}

int dfs(int pos, int flag){
  if(pos == m){
    if(flag != (1 << n) - 1) return 0;

    // puts("test");

    REP(i,xs.size()){
      if(!y[henkan(xs[i])]) return 0;
    }

    return 1;
  }else{
    int ret = 0;
    REP(i,1<<n) if((flag & i) == 0){
      wariate[pos] = i;
      ret += dfs(pos + 1, flag | i);
    }
    return ret;
  }
}

int main(){
  int cc = getInt();
  while(cc --> 0){
    m = getInt();
    n = getInt();
    a = getInt();
    b = getInt();

    if(n > 4 || m > 4){
      printf("myonmyon");
      return 0;
    }

    REP(i,1<<m) x[i] = 0;
    REP(i,1<<n) y[i] = 0;
    xs = vector<int>();

    REP(i,a) x[getInt()] = 1;
    REP(i,b) y[getInt()] = 1;
    bool update;

    update = true;
    while(update){
      update = false;
      REP(i,(1 << m)) if(x[i]){
        REP(j,i) if(x[j]){
          if(x[i | j] == 0 || x[i & j] == 0){
            update = true;
            x[i | j] = x[i & j] = 1;
          }
        }
      }
    }

    update = true;
    while(update){
      update = false;
      REP(i,(1 << n)) if(y[i]){
        REP(j,i) if(y[j]){
          if(y[i | j] == 0 || y[i & j] == 0){
            update = true;
            y[i | j] = y[i & j] = 1;
          }
        }
      }
    }

    REP(i,1 << m) if(x[i]){
      xs.push_back(i);
    }
    /*
    REP(i, 1 << n) if(y[i]){
      printf("ys: %d\n", i);
    }
    */

    printf("%d\n", dfs(0, 0));
  }
  return 0;
}
その後

そのあとはA問題のラージを考えて探索解をかいたりしていたが、探索が全然終わらなさそう。
最後の15分でH問題をやろうとするもタイムアップ。
という感じでした。