Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-30

[][][] TopCoder Single Round Match 501 Div1 04:32 はてなブックマーク -  TopCoder Single Round Match 501 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:23:06.293Challenge Succeeded0.00
5000:43:32.380Opened0.00
1000--0.00
Challenge..0.00

部屋(Room 10) 14位,全体 487位

Rating : 1494 → 1396 (-98)

前回うまくいったのに調子をのったせいか,足下をすくわれました。

250 FoxPlayingGame

問題文

 (要ログイン)TopCoder Statistics - Problem Statement

要約

 初期値 0 点からゲームを行う。ゲーム中行動 A を nA 回行い,行動 B を nB 回行う。A, B を行う順序は自由に決めて良い。行動 A を行うと,今の持ち点が pA/1000.0 点増え,行動 B を行うと持ち点が pB/1000.0 倍される。ゲーム終了時に得られる点数の最大値を求めよ。nA, nBは 0 以上 50 以下,pA は -10000 以上 10000 以下,pB は -2000 以上 2000 以下。

方針

 きちんと自分で計算式を立てて答えを求めようとすると,場合分けが大変になる。

  pA が正か負かと pB の絶対値が 1000 以上か以下かで場合分けにより,大雑把には「連続 A → 連続 B」か「連続 B → 連続 A 」かが決まることが,サンプル例を見るとわかる。しかしこれだけだと不十分で,例えば B で「連続 A → 連続 B」行った結果,答えが負になった場合,B を 1 回前倒しして「B → 連続 A → 連続 B」とすれば答えを正に出来る。このような調節は,必要かどうかは nB の偶奇に,出来るかどうかは nB が 1 以上かによる。

 

コード例(c++,コンテスト外)
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <map>
#include <cmath>

using namespace std;

class FoxPlayingGame {
public:
  double theMax(int na, int nb, int pa, int pb) {
    double ans = 0;
    if(pb > 1000 || pb < -1000){
      if(pa >= 0){
	ans+= pa * na/(double) 1000;
	if(pb > 0) 
	  for(int i = 0;i<nb;i++){
	    ans *= pb/(double)1000;
	  }
	else
	  for(int i = 0;i<(nb/2)*2;i++){
	    ans *= pb/(double)1000;
	  }
	return ans;
      }else{
	if(pb > 0){
	  return pa * na/(double) 1000;
	}else{
	  if(nb == 0)
	    return  pa * na / (double) 1000;
	  ans+= pa * na / (double) 1000;
	  if(nb % 2 ==0) nb--;
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	  return ans;
	}
      }
    }else{
      if(pa >= 0){
	return  pa * na / (double) 1000;	
      }else{
	if(nb == 0)
	  return  pa * na / (double) 1000;	
	ans += pa * na / (double) 1000;	
	if(pb > 0){
	  for(int i = 0;i<nb;i++){
	    ans *= pb / (double)1000;
	  }
	  return ans;
	}else if(pb == 0){
	  return 0;
	}else 
	  return pb * ans / (double)1000;
      }
    }
  }
};

下のコードは実際に自分が提出して Challenge されたものです。Challengeの練習にどうぞ。実際のケースはここに記載されています:TopCoder - Error

(このコードは正しくありません)
// Challenged Case
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <map>
#include <cmath>
 
using namespace std;
 
class FoxPlayingGame {
  typedef long long ll;
public:
  double theMax(int na, int nb, int pa, int pb) {
    double ans = 0;
    if(pb > 1000 || pb < -1000){
      if(pa >= 0){
        ans+= pa * na / (double) 1000;
        if(pb > 0)
          for(int i = 0; i < nb; i++){
            ans *= pb / (double)1000;
          }
	else
	  for(int i = 0; i < (nb/2)*2; i++){
	    ans *= pb / (double)1000;
	  }
	return ans;
      }else{
	if(pb >= 0)
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	else
	  for(int i = 0;i<nb;i++){
	    ans *= pb / (double)1000;
	  }
	ans+= pa * na / (double) 1000;
	return ans;
      }
    }else{
      if(pa >= 0){
	if(pb >= 0)
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	else
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	ans += pa * na / (double) 1000;  
	return ans;
      }else{
	ans += pa * na / (double) 1000;  
	if(pb >= 0)
	  for(int i = 0; i < nb; i++){
	    ans *= pb / (double)1000;
	  }
	else
	  for(int i = 0; i < ((nb-1)/2) * 2 + 1;i++){
	    ans *= pb / (double)1000;
	  }
	return ans;
      }
    }
  }
};

500 FoxAverageSequence

問題文

 (要ログイン)TopCoder Statistics - Problem Statement

要約

 数列 A (0-indexed,長さは有限) が次の条件を満たす時,beautiful sequence という。

  • 各々の値は 0 以上 40 以下
  • A[i] <= (A[0] + A[1] + ... + A[i-1]) / i.(各値はそれ以前の数の算術平均以下)
  • A[i] > A[i+1] > A[i+2].となる i は存在しない。(2 回連続で値が下がることはない)

 数列が与えられている。その数列の値は -1 以上 40 以下である。そのうち -1 の部分を別の数字に書き換えて,beautiful sequence にする場合の数を mod 1,000,000,007 で答えよ。

方針

 長さ i の数列の個数から長さ i+1 の数列を作る DP を考える。i+1 番目の数を決めるのに必要な情報は

  • 数列の末端で値の下降は何回連続で起こったか( a[t] > a[t+1] を 1 回の値の下降と呼んでいる)
  • それまでの数の和
  • 最後の数

なので,dp[j][k][l] で,(長さが i で)j 回値が下降し,数列の和が k,最後の数字が l の数列の個数を表す事にする。

コード例(c++,コンテスト外)
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <map>
#include <cmath>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;
ll mod = 1000000007ll;
ll dp[2][1700][41] = {} ;

class FoxAverageSequence {
public:
  int theCount(vector <int> seq) {
    memset(dp, 0,sizeof(dp));
    if(seq[0] == -1){
      for(int i = 0; i <= 40; i++){
	dp[0][i][i] = 1;
      }
    }else{
      dp[0][seq[0]][seq[0]] = 1;
    }
    
    for(size_t i = 1;i < seq.size();i++){
      ll next[2][1700][41] = {};
      for(int j = 0; j < 2; j++){
 	for(int k = 0; k < 1700; k++){
	  for(int l = 0; l <= 40; l++){
	    if(dp[j][k][l] == 0) continue;
	    if(seq[i]==-1){
	      if(j == 1){ 
		for(int m = l; m <= 40 && m * i <= k; m++){
		  next[0][k+m][m] = (next[0][k+m][m] + dp[j][k][l] + mod) % mod;
		}
	      }else{
		for(int m = 0; m < l && m * i <= k; m++){
		  next[j+1][k+m][m] = ( next[j+1][k+m][m] + dp[j][k][l] + mod) %mod;
		}
		for(int m = l; m <= 40 &&  m * i <= k ;m++){
		  next[0][k+m][m] = (next[0][k+m][m] + dp[j][k][l] + mod) % mod;
		}
	      }
	    }else{
	      if(seq[i] * i > k)  continue;
	      if(j != 1){
		if(l > seq[i]){
		  next[j+1][k+seq[i]][seq[i]] = (next[j+1][k+seq[i]][seq[i]]+dp[j][k][l] + mod )%mod;
		}else{
		  next[0][k+seq[i]][seq[i]] = (next[0][k+seq[i]][seq[i]] + dp[j][k][l] + mod) % mod;
		}
	      }else{
		if(l <= seq[i]) {
		  next[0][k+seq[i]][seq[i]] = (next[0][k+seq[i]][seq[i]]+  dp[j][k][l] + mod)%mod;
		}
	      }
	    }
	  }
	}
      }
      for(int j = 0; j < 2; j++){
	for(int k = 0;k < 1700; k++){
	  for(int l = 0; l <= 40; l++){
	    dp[j][k][l] = next[j][k][l];
	  }
	}
      }
    }
    ll ans = 0;
    for(int j = 0; j < 2; j++){
      for(int k = 0; k < 1700; k++){
	for(int l = 0; l<=40; l++){
	  if(dp[j][k][l] == 0)continue;
	  ans = (ans + dp[j][k][l] + mod) % mod;
	}
      }
    }
    return(int) ans;
  }
};

1000 FoxSerarchingRuins

問題文

 (要ログイン)http://www.topcoder.com/stat?c=problem_statement&pm=11286&rd=14430

要約

 まだ読んでいません

Coding Phase

 目標 Level 2 を解く事。これまでに比べ黄色や赤色の人が多い部屋に割り振られる。Level 1 パッと思いつく限りでも pB の場合分けが少なくとも 3 通り,pA の場合分けが少なくとも 2 通りある事がわかる。場合分けをきちんとやれば各々のケースは簡単に書けるはずだとコードが汚くなる事を覚悟で if then else を列挙する事に決める。自分が書き始めようとする時点でもう提出者が現れ,焦ってしまう。コーナーケース ( pB = -1000 など)の場合どうなるかと不安になるが,今回の場合気にしなくてもよかった。時間がかかったが提出,場合分けの 1 つので計算式を間違えていたがコンテスト中には気づけなかった。自作のテストケースで検証したが場合分けが多くて全ての可能性を列挙できなかったのが失敗の原因だと思う。

 Level 2 数列の数を数える問題。Project Euler で bouncy number を求める問題*1 と似ている。Codeforcesでも似たような問題を扱ったので,これは解けるのではないかと思った。DP の方法もすぐに思いつき大体の実装も比較的すんなりできた,がデバッグが間に合わなかった。

反省

デバッグについて

 Segmentation Fault などの問題とあまり関係ない所でのデバッグに時間がかかった。コード文法ミスがないかをにらめっこして時間を費やす事が多かったが,簡単なテストケースの printf でバッグの方が良かったかもしれない。周りでプログラミングが上手い人との差を見ると,コードを書く時間の差異より,デバッグする時間の差異が大きいように思う。

問題選定について

 Level 2 に注力した結果それに捕われ, Level 1 が疎かになった。

[][] Codeforces Beta Round #65 (Div. 2) 07:19 はてなブックマーク -  Codeforces Beta Round #65 (Div. 2) - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #65 (Div. 2) - Codeforces

結果:Standings - Codeforces Beta Round #65 (Div. 2) - Codeforces

=.ABCDE
--0:030:100:23--
2816+0/-04949601362--

部屋内 4位(Room 71),全体 17位 (out of competion 含めて 53 位)

Rating:1597 → 1659 (+64)

 やっぱりD問題は解きたかったです。本日の夜 20 時からSRM 501 が行われる予定です。

A. Way Too Long Words

要約

 文字列が与えられている。文字列が 10 文字以下の場合はそのまま出力,10文字を越える場合は,省略記法で出力せよ。省略記法は「先頭文字 + 省略した文字数 + 終端文字」の形で表す。例えば

localization → l10n
pneumonoultramicroscopicsilicovolcanoconiosis → p43s

 与えられる文字列の数は 1 以上 100 以下,各文字列の長さは 1 以上 100 以下

方針

 文字数で場合分けして,指定された通りに出力すれば良い。

コード(c++)
#include <iostream>
#include <string>
using namespace std;

int main(){
  int n;
  while(cin >> n){
    for(int i = 0;i<n;i++){
      string s;
      cin >> s;
      if(s.size() > 10){
	int a = s.size() -2;
	cout<< s[0] << a << s[s.size()-1] <<endl;
      }else{
	cout << s << endl;
      }
    }
  }
  return 0;
}

B. Progress Bar

要約

 ファイルの解凍などの時に現れる,進捗を表すバーを考える。バーは n 個のマスからなり,それぞれのマスの充填度合いを 0(空)から k(満杯)の整数で表す。マスは左から充填し,あるマスが満杯になったらその右隣のマスが充填され始める。すべてのマスが 0 ならば 0 %の進捗,全てのマスが k なら 100 %の進捗を表す。t %の進捗を表すマスの充填度を n 個の整数で表せ。

 n, k は 1 以上 100 以下,t は 0 以上 100 以下。

 数式で書くと,出力するのは次の条件を満たす数列 {a[i] | 1 <= i <= n}.

  • 0 <= a[i] <= k
  • a[j] ≠ 0 ⇒ a[j-1] = k for j = 2,3,..n
  • (Σ_{i = 1}^{n} a[i]) / n*k <= t / 100 <= ( (Σ_{i = 1}^{n} a[i]) + 1) / n*k
方針

 出力すべき数の合計値を予め計算しておき,それを k 個ずつに区切って出力する。

コード(c++)
#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n;
  while(cin >> n){
    int k,t;
    cin >> k >> t ;
    int sum = n * k * t /100;
    for(int i = 0; i < n; i++){
      if(sum >= k){
	cout << k << " ";
	sum -= k;
      }else if(sum > 0){
	cout << sum << " " ;
	sum = 0;
      }else{
	cout << 0 << " ";
      }
    }
    cout <<endl;    
  }
  return 0;
}
分析

 システムテストで落ちていた解答を見ると,満杯のマス,中途半端のマス,空のマスを異なるループで計算した結果,n 個より多い(or 少ない)の整数を出力しているものが多かった。そのため,ループの回数は固定してその中で出力する整数を場合分けする上のコードは有効だったように思う。

C. Round Table Knights

要約

 円上等間隔に n 人の騎士が座っている。それぞれの騎士が機嫌が良いか悪いかが与えられている。円に内接する多角形で,その頂点すべてに機嫌の良い騎士座っているかようなものが存在するかを判定せよ。n は 3 以上 10^{5} 以下。

方針

 大雑把に見積もると O(n^2) で間に合わないように見えるが,実際の計算量はもっと少ない。i 個飛ばしの場合を全探索すると,約 n/i * i 通り,実際に探索するのは騎士を n/3, n/4,.., n/n 個飛ばしで調べる場合なので,n/3 + n/4 + .. + n/n = O(log n). 従って,きちんと枝狩りすれば全探索でも O(n * log n) のアルゴリズムになる。

 作った多角形が退化する場合( = 頂点が3個未満である事)を除かなければならないが,問題文で丁寧に説明されていたので間違える心配は少ない。

コード(c++)
#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n;
  while(cin >> n){
    vector<int > a(n);
    for(int i = 0; i < n; i++){
      cin >> a[i];
    }
    for(int i = 1; i < (n+1)/2; i++){
      if(n % i != 0) continue;
      for(int j = 0; j < i; j++){
	bool flag = true;
	for(int k = 0 ; k < n/i; k++){
	  if(a[(j + k * i) % n] != 1){
	    flag = false;
	    continue;
	  }
	}
	if(flag){
	  cout << "YES" <<endl;
	  goto next;
	}
      }
    }
    cout << "NO" <<endl;
  next:;
  }
}

D. Solitaire

要約

 トランプ54枚(52枚+ジョーカー2枚)でゲームを行う。まず n * m の長方形に並べられたカードが並べられる,残りは手札として持っている。並べた中にジョーカーがある場合は,それを手札の好きなカードと取り替えて良い。並べた中に次の条件を満たす 3 * 3 の正方形のペアがあれば勝ち,そう出なければ負けとなる。

  • 2つの正方形は重なりあわない。
  • それぞれの正方形は次のいずれかを満たす
    • 9 枚のカードのスートが同じ・・・(1)
    • 9 枚のカードのどの 2 枚を取っても数が相違・・・(2)

 勝ち負けを判定せよ。また,勝つ場合にはジョーカーを何に変えれば良いかと,条件を満たす 2 つの正方形がどこにあるかも答えよ。

方針

 まだ解いていません

E. Nuclear Fusion

要約

 原子がいくつか与えられている。そこから核融合を繰り返し,決められた原子を作れるかどうかを判定し,作れる場合はその作り方を示せ。融合は 2 つの原子を 1 つの原子にする事のみでき,原子番号 Z の原子と原子番号 W の原子から原子番号 Z+W の原子ができる。初めに与えられる原子の個数 n は 1 以上 17 以下で,作るべき原子の個数 k は 1 以上 n 以下。問題に登場する原子の原子番号は 100 以下。

方針

まだ解いていません

コンテスト中

 目標 4 問。アルゴリズムが関わるような問題を最低限 1 題は解きたいと思い臨む。最初 30 分は今までで一番調子良かった。3問解き終えて,部屋 1 位,全体 2 位まで順位が上がった。この時 A, B, C の Hack をするか D 問題に行くかを迷う。自分で書いている時に引っかかりそうなケースを思いつかなかったので,他の人の Hack の様子を見て多かったら自分も参加しようと決める。D 問題,ジョーカーがなければ簡単だけれど,ジョーカーを何に代えれば良いかが分からず詰まる。条件を満たす物を適当に取れば良いかと思ったが,次のような状況でまずい事に気づく:2 つの正方形の両方にジョーカーがあり,一方の正方形ですり替えられる手札の候補が 2 枚以上,かつもう一方では 1 枚でさらにその 1 枚が両方の正方形で条件を満たせる。この時,2 枚以上ある方で適当にカードを取った結果,両方で条件を満たせる 1 枚を取ってしまったら勝てる状況でも負けと判定されてしまう。しかし,そもそもこういうような状況が起こりうるのかがわからない。適当な例を作ろうとするも,うまくいかずこの辺りで混乱し始める。その後(1)⇒(2)なので,(2)の条件だけ調べれば良い事だけはわかったが,ジョーカーの変え方が分からないままだった。1時間程度 D 問題と部屋の様子を交互に見ているも進展はなかった。

 E 問題を読むも 30 分弱で書ける自信がなかったので Hack に集中する事を決める。ソースをいくつか見ても大丈夫そうにしか見えず何も出来ないまま終了した。

反省

 システムテストを見ると自分で大丈夫だと思っていたものが結構落ちている(今回の場合 B 問題がそうだった)。こういう物をきちんと取れるようにしたい。また 30 分前に書いた自分のコードでも忘れるので,書くなら突貫でやらないと行けないと感じた。途中まで書いた D 問題のコードに追加する事さえ苦労した。