Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-31

[][] Project Euler Problem 113 09:09 はてなブックマーク -  Project Euler Problem 113 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=113

要約

 正数で,各桁の数を順番に見ていった時単調増加でも単調減少でもない数をbouncy numberと呼ぶ事にする.10^{100}未満の数の中でbouncy でない数の個数を求めよ.

方針

便宜上まずは0もbouncy numberに入れて数え上げる.単調増加の数は

0001123・・・999(leading zeroも含めて100桁)

の用になるもの.これの数は横に100マス縦に9マスある格子道を左下から右上に進む進み方なので,109C9通り,

 単調減少の数は

99988877・・・000 (leading zeroがなく100桁以下)

これは9より大きい数がleading zeroの代わりにあると考えれば(これを*と書くことにする),11種類の数を重複を用いて100個並べる並べ方なので,110C10通り.

ここからモレ,ダブりを除いていく

  • 単調増加かつ単調減少
    • 正数としてvalid (000011・・11から000099・・99と****11・・11から****99・・99) (1)
    • 正数としてinvalid (00・・00)  (2)
  • 単調増加だが単調減少でない
    • 正数としてvalid
    • 正数としてinvalid (なし)
  • 単調増加でないが単調減少
    • 正数としてvalid
    • 正数としてinvalid (*00・・00, **00・・00, ・・, **・・**00, **・・**0, **・・**) (3)

(1)は2回重複して数えているのを1回に減らす.(2)は2回,(3)は1回数えているがこれらは両方除外する.従って,求める個数は

108C9 + 109C9 - 100 * 9 - 2 -  100
コード例(c++
#include <iostream>

using namespace std;

typedef long long ll;

ll n = 100;

ll comb(ll n, ll m){
  if(m == 0 || m == n) return 1;
  return comb(n-1, m-1)* n / m;
}


int main(){
  cout << comb(n + 9, 9) + comb(n + 10, 10) - 10 * n - 2 << endl;
  return 0;
}

2011-05-29

[][] TopCoder Single Round Match507 Div1 19:38 はてなブックマーク -  TopCoder Single Round Match507 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:11:56.237Passed System Test214.63
5000:57:07.821Challenge Succeeded151.45(再提出1回)
9001:00:14.440Opened0.00
Challenge..0.00

部屋(Room 30) 7位,全体 481位

Rating : 1449 → 1448 (-1)

500の正答率が30%弱で,250点問題の早解き + 500点問題Challengeの回でした.

続きを読む

2011-05-28

[][] Google Code Jam Round 1A Problem C 18:20 はてなブックマーク -  Google Code Jam Round 1A Problem C - 練習帳

要約

 カードを用いたゲームを行う.それぞれのカードには3つの数字が書かれており,それぞれs(score), c(card), t(turn)と表す.手札に何枚かカードを持ち,残りは山札としてゲームを始める.残りターン数1から初めて,1ターンに次の行動を行う.

  • 手札から好きなカードを1枚切る
  • 捨てたカードに書かれた
    • sの数だけ得点を獲得する
    • cの数だけ山札の上からカードを引く
    • tの数だけターン数を増やす
  • 残りターン数を1消費する
  • 最初に戻る

 手札が0になるか,残りターン数が0になったらゲームは終了する.最初の手札と山札にあるカードが予めすべて分かっているとき,得られる点数の最大値を求めよ.テストケースは100個以下.最初の手札の枚数は1枚以上,山札の枚数は0枚以上で,手札と山札の合計は80枚未満.カードに書かれている数は

small:0 <= c <= 1, 0 <= s <= 20, 0 <= t <= 20

large:0 <= c <= 2, 0 <= s <= 50, 0 <= t <= 50

分析

 まず,手札の中でターン数を増やすもの(つまり t > 0)があればそれを切っても損はしないので,無条件に選ぶ.問題は手札が全てt = 0の時何を切るか.sあるいはcの多いカードから貪欲に切る方法は,例えば次のような反例がある(|の左3枚が手札,右2枚が山札で(s, c) = (9, 0)の方が上).

(残りターン数:2)
s 2 1 0 | 9 0
c 0 1 2 | 0 0

この時は(1, 1), (9, 0)と切ると最高得点10点が得られる.また,同じ手札でも,

(残りターン数:2)
s 2 1 0 | 0 9
c 0 1 2 | 0 0

ならば,(0, 2), (9, 0)と切らないと最高得点とならない.つまり,何を切るかはいまある手札だけではわからない.

という事は,「cの値で手札を分類した時,それぞれのグループで得点が最大のものが次に切るカードの候補である,それらのどれを切るかで動的計画法を行う」のか等と考える.しかし山札の中では後にくるカードを先に切る可能性があるので,それぞれのカードを切った/切っていないで状態を持たなければならず,従って組み合わせ爆発を起こしてしまう.

 この辺りで何をすればよいかが分からなくなったので,解説を読む.自分が気づかなかったのはobservationの2つ目.これがあれば,cの値が同じ2枚のカードがあり,両方とも最終的に切る事になる場合,2枚のうち山札の中で上にある方を先に切ったと仮定してよい.すると,山札を上から順番に走査して切る/切らないを決めていけば良く,後戻りする必要はない.c = 0, 1, 2で分類したとき,どのカードまで切る/切らないかが決まっているかを動的計画法で用いる状態で持てばよい.

コード例

下のコードはkrijgertjeさんのコードを写経したものです.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

vector<int> cs, ss, ts;
int n;

int best[81][81];
int memo[81][81][81][81];

// c1 : the position of cards whose bonus of turn is 1 and which is not determined if it is discarded or trumped.
// c2 : bonus of turn is 2. 
// drawn : the largest index of the card drawn. 
// turn : residual turn
// todraw : the number of cards to draw in next turn whose bonus of turn are zero.

int solve(int c1, int c2, int drawn, int turn, int todraw){
  if(turn == 0) return 0;

  // Trump cards at hand whose bonus of turn are more than 0.
  int extra = 0;
  while(todraw > 0 && drawn < n){
    if(ts[drawn] > 0){
      todraw += cs[drawn];
      extra += ss[drawn];
      turn += ts[drawn] - 1;
    }
    todraw--;
    drawn++;
  }
  turn = min(turn, n);
  
  // search for next cards to be considered.
  while(c1 < drawn && (ts[c1] > 0 || cs[c1] != 1)) c1++;
  while(c2 < drawn && (ts[c2] > 0 || cs[c2] != 2)) c2++;

  int ret = memo[c1][c2][drawn][turn];
  if(ret == -1){
    // Points from cards from C0-cards
    ret = best[drawn][min(drawn,turn)];

    if(c1 < drawn){
      // trump C1-card
      ret = max(ret, ss[c1] + solve(c1 + 1, c2, drawn, turn + ts[c1] - 1, cs[c1]));
      // discard C1-card
      ret = max(ret, solve(c1 + 1, c2, drawn, turn, 0));
    }
    if(c2 < drawn){
      // trump C2-card
      ret = max(ret, ss[c2] + solve(c1, c2 + 1, drawn, turn + ts[c2] - 1, cs[c2]));
      // discard C2-card
      ret = max(ret, solve(c1, c2 + 1, drawn, turn, 0));
    }
  }
  
  memo[c1][c2][drawn][turn] = ret ;
  return ret + extra;
}


int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    int N;cin >> N;
    cs.clear();cs.resize(N);
    ss.clear();ss.resize(N);
    ts.clear();ts.resize(N);

    for(int j = 0;j <N;j++){
      cin >> cs[j] >> ss[j] >> ts[j];
    }
    int M;cin >> M;
    for(int j = 0;j < M;j++){
      int c,s,t;
      cin >> c >> s >> t;
      cs.push_back(c);
      ss.push_back(s);
      ts.push_back(t);
    }

    n = N + M;

    for(int j = 0 ;j <= n;j++) {
      vector<int> have;
      for(int k = 0; k < j ;k++){
	if(ts[k] == 0 && cs[k]==0)
	  have.push_back(ss[k]);
      }
      sort(have.rbegin(),have.rend());
      best[j][0]=0;
      for(int k =1; k <= j; k++){
	best[j][k] = best[j][k-1] + (k-1 < have.size() ? have[k-1] : 0);
      }
    }

    memset(memo, -1, sizeof(memo));
    int ans = solve(0,0,0,1,N);
    
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;

}

}

||<

2011-05-27

[][] Project Euler Problem 109 08:49 はてなブックマーク -  Project Euler Problem 109 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=109

要約

 ダーツで次の条件を満たすポイントの組み合わせの数を求めよ。

  • 3 投以内
  • ポイントの合計は 100 点未満
  • 最後の 1 投はダブル(50 点のインナーブルも含む)
  • 最後の 1 投以外は順不同(順序を変えて同じになる組み合わせは 1 通りとみなす)
    • S1, D2, D4 と D2, S1, D4 は同じ組み合わせ
    • S1, D4, D2 と S1, D2, D4 は異なる組み合わせ

続きを読む

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分程度で解答するものでした.

続きを読む

2011-05-19

[][] TopCoder Single Round Match 504.5 Div1 950 TheTicketsDivOne 02:21 はてなブックマーク -  TopCoder Single Round Match 504.5 Div1 950 TheTicketsDivOne - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

950 TheTicketsDivOne

要約

 n人が1列に並んでいて,そのなかから1人を次のように選ぶ

  • サイコロを振り,出た目に応じて現在先頭の人が次のように行動する
    • 4 : 先頭の人を選んで終了する
    • 1,3,5 : 先頭の人が列の最後尾に並び直す
    • 2,6 : 先頭の人が列から去る
  • 最初に戻る

 一番最初の状態でm番目(1-indexed)に並んでいる人が選ばれる数を求めよ.nは1以上1000以下.mは1以上n以下.

続きを読む

2011-05-18

[][] TopCoder Single Round Match 504.5 Div1 02:08 はてなブックマーク -  TopCoder Single Round Match 504.5 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:07:45.740Passed System Test233.07
5000:41:00.454Challenge Succeeded0.00
10000:25:54.023Opened0.00
Challenge..0.00

部屋(Room 37) 10位,全体 370位

Rating : 1420 → 1490 (+70)

 ノーコンテストとなった回の代替試合.Mediumが荒れた回でした.

自分の結果に関しては,Easyを解いた速さは比較的満足しています.Mediumは前回のSRMと同じく検証をさぼったのが原因です.950を解く時間の確保を優先したのが戦略ミスでした.

 同じ部屋だったuwiさんが部屋1位でレッドコーダーに昇格しました.おめでとうございます.

続きを読む

2011-05-15

[][] 2011 TCO Qualifier Round 1 15:26 はてなブックマーク -  2011 TCO Qualifier Round 1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:13:44.036Passed System Test206.05
5000:27:12.828Challenge Succeeded0.00
10000:33:46.621Opened0.00
Challenge..0.00

部屋(Room 18) 13位,全体 763位

Rating : 1453 → 1420 (-33)

 3回あるQualification Roundの1回目,上位600名がRound 1に進出します.今回はDivisionの分割はなく,全員が共通の問題を解きました.問題の難易度はDiv.1とDiv.2 の中間くらいだったように思います.AdvancerになるにはEasy + Medium かEasy + Challenge2回くらいが必要でした.また,一部屋あたりの参加者の数が20人から25人に増えていました.これは参加者が増えて,Register期間内に定員に達する事が多かったので,今回だけの措置ではないと思います.

 反省点は250が余りにも遅かった事と,500での最大ケースでの検証をさぼった事でしょうか.

続きを読む

2011-05-12

[][] Project Euler Problem 64 01:02 はてなブックマーク -  Project Euler Problem 64 - 練習帳

 昨日休んだので,2日分.でも,1問は軽い問題でお茶を濁しています.

問題文

 http://projecteuler.net/index.php?section=problems&id=64

要約

 √N を連分数展開したものを [a[0]; a[1],... , a[i],...] と書き *1 ,さらに a[1] 以降で周期的な部分をまとめて,[a[0]; (a[1],... , a[i])] と書く.この時,i を周期と呼ぶ事にする.N <= 10000 で平方数でないもののうち,周期が奇数のものの個数を求めよ.

続きを読む

[][] Project Euler Problem 77 01:01 はてなブックマーク -  Project Euler Problem 77 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=77

要約

 不定数の素数の和で表す表し方が5000通りを超えるもののうち,最小の整数を答えよ.(例えば 和が10となる足し方は次の 5 通り )

10 = 7 + 3
          5 + 5
          5 + 3 + 2
          3 + 3 + 2 + 2
          2 + 2 + 2 + 2 + 2

続きを読む

2011-05-10

[][] Project Euler Problem 78 23:54 はてなブックマーク -  Project Euler Problem 78 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=78

要約

 正数 n で,分割数が1,000,000で割り切れるもののうち最小のものを答えよ.

続きを読む

2011-05-08

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

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

 全問small, large共に正答できました.時間をかければ解けるという事が分かって一安心です.

続きを読む

2011-05-07

[][] Yandex.Algorithm 2011 Qualification 2 02:42 はてなブックマーク -  Yandex.Algorithm 2011 Qualification 2 - 練習帳

問題一覧:Dashboard - Yandex.Algorithm 2011Qualification 2 - Codeforces

結果:Standings - Yandex.Algorithm 2011Qualification 2 - Codeforces

=.ABCDE
--0:100:50---
580+1/-0480-2---

部屋内18位(Room 29),全体570位

Rating:1452 → 1541 (+89)

 Qualfication Roundの2回目.順位だけ見ると惜しい気もしますが,ボーダーの978点に達するにはBを当てるか,後4人Hackする必要があったので,少し厳しいような気もします.BのHackが大量に行われ,多い人は20回近く成功していました.

続きを読む

2011-05-05

[][] SRM 505 Div1 300 RectangleArea 01:38 はてなブックマーク -  SRM 505 Div1 300 RectangleArea - 練習帳

 前回のSRMのEasyがwriterさんのコードを見てようやく理解できたので,備忘録としてメモを残しておこうと思います.

300 RectangleArea

要約

 N*Mの小長方形に分割された長方形があり,小長方形のうちいくつかは面積がわかっている.あといくつ小長方形の面積がわかれば全体の面積が求まるか.個数の最小値を求めよ.N, Mは1以上50以下.

続きを読む

[][] Yandex Open 2011 Qualification 1 09:35 はてなブックマーク -  Yandex Open 2011 Qualification 1 - 練習帳

問題一覧:Dashboard - Yandex.Algorithm Open 2011Qualification 1 - Codeforces

結果:Standings - Yandex.Algorithm Open 2011Qualification 1 - Codeforces

=.ABCDE
---0:29---
0+0/-0--1-2--

部屋内10位(Room 68),全体781位

Rating:1531 → 1452 (-79)

 Yandexなるロシアのインターネット関連会社が主催するプログラミングコンテストが,Codeforcesをホストとして開催されています(ルールは通常のCodeforcesと同様です).今回は2回あるQualificationラウンドの1回目で,上位500位までがRound1に進出します.ボーダーは1188点なので,A+Bを高速で解くか,A+Cを少ない誤答で解けばノルマを達成できたようです.

 自分については,Codeforcesで0点は初めてかもしれないです.A, B問題について掲載します.C問題までは消化したいと思っています.

続きを読む

2011-05-03

[][] TopCoder Single Round Match 505 Div1 00:23 はてなブックマーク -  TopCoder Single Round Match 505 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

3001:14:55.450Opened0.00
5000:38:24.331Opened0.00
10000:00:00.000Unopened0.00
Challenge..0.00

部屋(Room 36) 7位,全体 306位

Rating : 1484 → 1453 (-31)

何にも出来なかったです・・.取りあえず500のコードだけ掲載します.

続きを読む

[][] Project Euler Problem 75 12:27 はてなブックマーク -  Project Euler Problem 75 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=75

要約

 1 本の針金を折り曲げて,各辺の長さが整数の直角三角形をつくる.長さが1500000 以下で,作れる直角三角形が 1 種類しかないものの個数を求めよ.

続きを読む

2011-05-01

[][] Codeforces Beta Round #71 22:50 はてなブックマーク -  Codeforces Beta Round #71 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #71 - Codeforces

結果:Standings - Codeforces Beta Round #71 - Codeforces

=.ABCDE
--0:050:30---
490+0/-0490WA---

部屋内17位(Room 59),全体612位

Rating: 1614→ 1531 (-83)

 ちょっとショックでした.作業のみの問題は人並みの速さで解けるようになってきたので,そうでない問題を時間内に解けるようになる練習が必要なのだと思います.

続きを読む