Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-23

[][] Google Code Jam Round 1A 02:14 はてなブックマーク -  Google Code Jam Round 1A - 練習帳

 問題一覧:http://code.google.com/codejam/contest/dashboard?c=1145485

 結果:http://code.google.com/codejam/contest/scoreboard?c=1145485#vf=1

 解説:http://code.google.com/codejam/contest/dashboard?c=1145485#s=a

=A.B.C.
-SmallLargeSmallLargeSmallLarge
26.3925.3026.39----
.--1 Wrong Try-1 Wrong Try-

全体 729位.

 3回あるRound 1の1回目,各回で上位1000人までが次のラウンドに進出できます.運良く1回目で条件を満たせました.ボーダーはProblem Aをsmall, large両方を42分程度で解答するものでした.

A. FreeCell Statistics

要約

 引き分けのない一人用のゲームこれまでに何回か行っており,勝率は今日行ったゲームだけで集計するとPD%, 全体でPG%である(PD, PG整数).また,今日行ったゲームの回数はN回以下と分かっている.このような条件を満たすゲームのプレイ回数と勝ち負けの回数が存在するか,あるいは,これらは矛盾する情報かを判定せよ(存在する場合でも,条件を満たす数の具体例を挙げる必要はない).

 テストケースの数はsmallで100以下,largeで2000以下.PD, PGは0以上100以下,Nはsmallで1以上10以下,largeで1以上10^{15}以下.

方針

 今日(resp. これまで)の行ったゲームの回数をD(resp. G)とすると,求める条件は

  • D * PD <= G * PG
  • D * (100 - PD) <= G * (100 - PG)
  • D * PD / 100, G * PG / 100は整数
  • D <= N

 ポイントはGはいくらでも大きくしても良いということ,Gを大きくする事で,PGが0でない限り1番目の条件は満たされ,100でない限り2番目の条件は満たされる.また,Gを100の倍数にすればG * PG /100は整数になる.よってD * PD / 100を整数にするような整数Dのうち最小のものを求め,それがN以下かを調べれば良い.例えば,PD = 12の場合,12/100 = 3/25と既約分数にすれば,D = 25が条件を満たす最小の数とわかる,つまり,PDと100の最大公約数を求めれば良い.

コード例
#include <iostream>
#include <vector>
#include <utility>
#include <string>

using namespace std;

typedef long long ll;

ll gcd (ll a, ll b){
  if(a < b) swap(a, b);
  if(a % b == 0) return b;
  return gcd(a %b, b);
}

string  solve(ll N, int pd, int pg){
  if(pg == 0){
    if(pd == 0) return "YES";
    else return "NO";		  
  }
  if(pg == 100){
    if(pd == 100) return "YES";
    else return "NO";		  
  }
 
  ll g = gcd(100, pd);
  ll n = 100 / g;
  if( n <= N) return "YES";
  else return "NO";

}


int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    ll n;
    int pd, pg;
    cin >> n >> pd >> pg ;

    string ans = solve(n, pd, pg);
    if(ans == "YES") ans = "Possible";
    else ans = "Broken";
		       
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;

}

B. The Killer Word

要約

 ハングマン(http://en.wikipedia.org/wiki/Hangman_(game))を2人で行う.但し,通常のハングマンとは異なり,解答者の誤答回数に制限はない.出題者と解答者は共通するワードリストを持っており,次の要領でゲームは進む.

  • 出題者が単語を一つ選び,単語の文字数分だけ空白マスを黒板に書く,出題者は解答者の提示に応じて答えを埋めていく.
  • 解答者は26文字のアルファベットのを並べ替えたリストを作る
  • 解答者はリストから順にアルファベットを選ぶ
  • 正解の候補の中に選んだアルファベットがあるならばそれを提示する,そうでなければ提示しない
    • 正解の候補とは,リスト中の単語のうち,解答者が知っている情報と矛盾しないものの事を言う
    • 解答者の知っている情報は答えの文字数と,答えのうち既にアルファベットが書かれているマスと答えとなる単語の文字数
  • 解答者が提示した場合で,
    • もしそのアルファベットが答えの中にあれば,その単語のなかの同じアルファベットをマスに書き込む.
    • なければ,解答者は1点得点を失う
  • 3番目に戻る
  • 以上をマスがすべて埋まるまで繰り返す

 出題者と解答者が共有する単語のリスト,及び解答者のアルファベットを提示する順序が与えられている.リストの中で解答者が失う点数が最も大きくなる単語を答えよ.

 テストケースの数は1以上10以下.共有リストの数はsmallで100以下,largeは10000以下.リストに現れる単語の文字数は10文字以下.1つのテストケースで与えられるリストの数はsmallで10以下,largeで100以下.

方針

 愚直に実装しても,リストの個数の2乗に比例するアルゴリズムが得られる.リストの数が10000なので,枝刈りを十分行えばlargeでも制限時間の8分以内に解答が得られる(ですが,largeは1発勝負なので,時間内に計算が終了するかの確認は事前に行うのが安全だと思います).

コード例

このコードはpracticeのlargeデータを48秒程度で計算できました.

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <cmath>

using namespace std;

int INF = 100000000;

int solveone(int n, string & s, vector<string> & d, string c){
  vector<int> kouho(n, 1);
  int lpoint = 0;
  for(int i = 0; i < n; i++){
    if(s.size() != d[i].size()){
      kouho[i] = 0;
    }
  }
  
  string suggest;
  for(int i = 0; i < s.size(); i++){
    suggest += "_";
  }
  
  for(int i = 0; i < c.size(); i++){
    bool flag = false;

    //check if c[i] should be claimed.
    for(int j = 0; j < n; j++){
      if(kouho[j] == 0) continue;
      for(int k = 0; k < d[j].size(); k++){
	if(d[j][k] == c[i]){
	  flag = true;
	}
      }
      if(flag){
	break;
      }
    }

    if(flag){
      bool islost = false;
      //completion of suggest
      for(int j = 0; j < s.size(); j++){
	if(s[j] == c[i]){
	  suggest[j] = c[i];
	  islost = true;
	}
      }
      if(!islost){
	lpoint++;
	for(int j = 0; j < n; j++){
	  if(kouho[j] == 0) continue;
	  if(d[j].find(c[i]) != string::npos){
	    kouho[j] = 0 ;
	  }
	}

      }
    }
    // narrow down of kouho 
    if(flag){
      for(int j = 0; j< n; j++){
	if(kouho[j] == 0) continue;
	for(int k = 0; k < d[j].size(); k++){
	  if(suggest[k] != '_' && d[j][k] != suggest[k]){
	    kouho[j] = 0;
	  }
	}
      }
    }
  }
  return lpoint;
}


string solve(int n, vector<string> & d, string c){
  int mn = -1;
  int pos = -1 ;
  for(int i = 0; i < n; i++){
    int s = solveone(n, d[i], d, c);
    if(s > mn){
      mn = s;
      pos = i;
    }
  }

  return d[pos];
}


int main(){
  int t;cin >> t;
  for(int i = 1; i <= t; i++){
    int n, m;cin >> n >> m;
    vector<string> d(n);
    vector<string> c(m);
    for(int j = 0; j < n; j++){
      cin >> d[j];
    }
    for(int j = 0; j < m; j++){
      cin >> c[j];
    }
    string ans;
    for(int j = 0; j < m; j++){
      ans +=solve(n, d, c[j]);
      if(j != m-1)
	ans += " ";
    }
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;

}