Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-30

[][] 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 問題のコードに追加する事さえ苦労した。