Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-31

[][] Codeforces Beta Round #65 E. Nuclear Fusion 01:36 はてなブックマーク -  Codeforces Beta Round #65 E. Nuclear Fusion - 練習帳

問題文

 Problem - E - Codeforces

出典回結果

 Codeforces Beta Round #65

要約

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

方針

 もし作るべき原子数が 1 つならば,ナップザック問題になる。しかし作る原子それぞれに通常のナップザック問題と同様の解法*1を適用すると,解のうちの一つを適当に求めることになり,例えば次のようなケースで失敗する可能性がある(原子番号で表す)。

[材料の原子]  →  [作る原子]
 1 3 6 9 30  →    4 6 39

39(Y) を作るのに 30(Zn) と 6(F) と 3(Li) を用いると 4(Be) が作れない。

 そこでそれぞれの原子を作り方のパターンを全て考え,深さ優先探索を行う。2^{17} の状態ではそれぞれの原子を用いたかをビットで記録すれば良い。さらに既に探索した状態が現れたらそこで枝刈りしている。

コード例(c++)

 周期表はここから取ってきました:The periodic table of the elements by WebElements

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

vector<int > orig;
vector<int > prod;
vector<vector<int> > comb;
int n;
int memo[1<<17];

string table[101] = {"dummy","H","He","Li","Be","B","C","N","O","F","Ne",
"Na","Mg","Al","Si","P","S","Cl","Ar",
"K","Ca","Sc","Ti","V","Cr","Mn","Fe","Co","Ni","Cu","Zn","Ga","Ge","As","Se","Br","Kr",
"Rb","Sr","Y","Zr","Nb","Mo","Tc","Ru","Rh","Pd","Ag","Cd","In","Sn","Sb","Te","I","Xe",
"Cs","Ba","La","Ce","Pr","Nd","Pm","Sm","Eu","Gd","Tb","Dy","Ho","Er","Tm","Yb","Lu","Hf","Ta","W","Re","Os","Ir","Pt","Au","Hg","Tl","Pb","Bi","Po","At","Rn",
"Fr","Ra","Ac","Th","Pa","U","Np","Pu","Am","Cm","Bk","Cf","Es","Fm"};

bool dfs(int res, vector<int > & ans){  
  if(memo[res] != -1){
    return false;
  }  
  if(res == 0 && ans.size() == prod.size()){
    return true;
  }
  int count = __builtin_popcount(res);
  vector<int > nums;
  for(int i = 0; i < n; i++){
    if((res >> i) & 1 == 1){
      nums.push_back(i);
    } 
  }
  for(size_t j = 0 ; j < comb[ans.size()].size();j++){
    if((res & comb[ans.size()][j]) == comb[ans.size()][j]){
      int next = res ^ comb[ans.size()][j]; 
      ans.push_back(comb[ans.size()][j]);
      if(dfs(next,ans)){
	memo[res] = 1;
	return true;
      }
      ans.pop_back();
    }	
  }
  memo[res] = 1;
  return false;
}

int main(){
  while(cin >> n){
    int k;cin >> k;
    memset(memo, -1, sizeof(memo));
    orig.clear();orig.resize(n);
    prod.clear();prod.resize(k);
    comb.clear();
    for(int i = 0; i < n; i++){
      string s;cin >> s;
      for(int j = 0; j < 101;j++){
	if(table[j] == s){
	  orig[i] = j;
	  break;
	}
      }
    }

    for(int i = 0; i < k ; i++){
      string s;cin >> s;
      for(int j = 0; j < 101;j++){
	if(table[j] == s){
	  prod[i] = j;
	  break;
	}
      }
    }
    sort(orig.begin(), orig.end());
    sort(prod.begin(), prod.end());

    comb.resize(k);
    for(int  i = 0; i < k; i++){
      for(int j = 0; j < (1<<n); j++){
	int total = 0;
	for(int l= 0; l < n; l++){
	  if((j >> l) & 1 == 1){
	    total += orig[l];
	  } 
	}
	if(total == prod[i]){
	  comb[i].push_back(j);
	}
      }
    }

    int before = accumulate(orig.begin(), orig.end(), 0);
    int after = accumulate(orig.begin(), orig.end(), 0);
    vector<int > ans;
    if(before == after && dfs((1<<n)-1, ans) ){
      cout << "YES" <<endl;
      for(size_t i = 0; i < ans.size(); i++){
	string s;
	for(int j = 0; j < n; j++){
	  if((ans[i] >> j) & 1 == 1){
	    s += table[orig[j]];
	    s += '+';
	  }
	}
	s.erase(s.size()-1);
	cout << s << "->" << table[prod[i]] << endl;
      }
    }else{
      cout << "NO" << endl;
    }
  next:;
    cout << endl;
  }
  return 0;
}

分析

 一応通った事は通りましたが,このコードの計算量を評価できていないです。上のコードでは各原子の作り方を前計算で列挙して変数 comb に保存し,それを深さ優先探索を行う時で利用しています。これを前計算せず,探索段階で組み合わせを列挙すると,次のケース (Test #31) で TLE を起こしました。

17 10
He He He He He He He He He He He He He He He He He
He He He He He He He He Li P

 恐らく 1 行目のそれぞれの He を 2 行目のどの He に対応させるかで組み合わせ爆発が起きたのだと思います。しかしそれは上のコードでもおきているはずで,計算量を大幅に減らせるような工夫のようには思えないです。わかる方がいましたら教えてもらえますでしょうか。

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)

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

続きを読む

[][] 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 が行われる予定です。

続きを読む

2011-03-28

[][] Project Euler Problem 110 16:55 はてなブックマーク -  Project Euler Problem 110 - 練習帳

(昨日更新しなかったので,2 日分更新)

テーマ:優先度付きキューとヤング図形

問題文

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

要約

 1/x + 1/y = 1/n (x <= y)の正数解が 4000000個以上あるような自然数 n のうち,最小のものを答えよ。

続きを読む

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

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

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

=.ABCDE
--0:06----
488+0/-0488-2---

部屋内 20位(Room 20),全体460位

Rating:1664 → 1602 → 1597 (2 つ目の変化はレーティングの計算方法が変わった影響)

不安的中,問題文が理解できない病にかかってる。前回と今回で Masa-Y さんが 青 → 紫 → オレンジ と連続ジャンプアップされました。おめでとうございます。

続きを読む

2011-03-26

[][] Codeforces Beta Round #16 E. Fish 12:59 はてなブックマーク -  Codeforces Beta Round #16 E. Fish - 練習帳

テーマ:配る DP と貰う DP *1,条件付き確率

問題文

 Problem - 16E - Codeforces

要約

 湖の中に魚が n 匹いる。ランダムに 2 匹が出会い,一方がもう一方を食べてしまう。魚 i と魚 j が会った時に i が j を食べる確率 a[i][j] は与えられている(a[i][j] + a[j][i] = 1)。これを湖に魚1匹しかいなくなるまで繰り返す時,それぞれの魚が生き残る確率を求めよ。

 nは 1 以上 18 以下

続きを読む

*1: iwiwi さんの講義資料から http://www.slideshare.net/iwiwi/ss-3578511

2011-03-25

[][][][] SRM473 Div1 Level2 600 TwoSidedCards 06:47 はてなブックマーク -  SRM473 Div1 Level2 600 TwoSidedCards - 練習帳

問題文

 http://www.topcoder.com/stat?c=round_overview&er=5&rd=14154

要約

 N 枚のカードが与えられている。それぞれのカードには 1 から N のうちいずれかの数字が裏表に 1 つずつ書かれている。表面合計 N 面に書かれている数字は 1 から N の相違なる数で,裏面も同様である(つまり表面の数をすべて集めると {1, ... , N} の置換)。例えば N = 4 の場合の一例は,

表 1 4 3 2
  ー ー ー ー
裏 3 2 1 4

 この N 枚のカードを適当に順序入れ替え,さらに何枚かを裏返して横一列に並べる事で,ordered N tuple を作る。作れる tuple の種類を modulo 1,000,000,007 で答えよ。

 N は 1 以上 50 以下

続きを読む

2011-03-23

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

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

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

=.ABCDE
--488892---
1380+0/-00:060:27---

部屋内 19位(Room 100),全体 296位(out of competition 含む)

Rating:変化なし(out of competition)

 Div2 の問題でも十分練習になるので参加。結果はあまり芳しくありませんでした。次の rated contest が不安でしょうがないです。

続きを読む

2011-03-22

[][][][] SRM473 Div1 Level2 500 RightTriangle 03:23 はてなブックマーク -  SRM473 Div1 Level2 500 RightTriangle - 練習帳

問題文

 http://www.topcoder.com/stat?c=round_overview&er=5&rd=14155

要約

 円周上に等間隔に places 個の点が置かれ,時計回りに 0 から places-1 まで番号が振られている。整数 a, b, c が与えられていて,次のルールで points 個の点に赤いマークを付ける。N = 0,1, ... , points-1に対して

  • P(N) = (a * n * n + b * n + c) % places を計算する
  • P(N)の番号を振られた点から時計回りに点を巡り,赤くマークされていない最初の点を見つける(P(N)がマークされていなければP(N)自身を選ぶ)
  • その点に赤いマークを付ける

円に内接するの直角三角形で頂点 3 つともに赤いマークがついているものの数を答えよ。

 places は 1 以上 1000000以下,pointsは 1 以上 100000 以下でplacesより大きくはない,a, b, cは 0 以上 1000000 以下

続きを読む

2011-03-21

[][] Unknown Language Round #2 18:46 はてなブックマーク -  Unknown Language Round #2 - 練習帳

 問題一覧:Dashboard - Unknown Language Round #2 - Codeforces

 結果:Standings - Unknown Language Round #2 - Codeforces

=penaltyABCDEFGHI
..--+-+-++1+1
5370--0:37-2:26-0:101:270:50

 全体 55位

 開始 1 分前まで使用言語が明かされないプログラミングコンテスト。前回の言語は tcl,今回は Ioでした *1。今回はインストーラやドキュメントへのリンクが提供されていて前回より親切設計です。

 同時刻に CodeChef の Monthly コンテストが行われていましたが,自分はこちらに参加しました。後で見てみると自分の認知できる日本人参加者は半々くらいで参加していたように思います。

続きを読む

2011-03-20

[][][] Top Coder Single Round Match 500 Div1 14:10 はてなブックマーク -  Top Coder Single Round Match 500 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:31:16.592Passed System Test138.89
5000:43:32.380Opened0.00
10000:41:14.889Challenge Succeeded0.00
Challenge..0.00

部屋 6位 (Room 43) ,全体 148位

Rating : 1260 → 1492 (+232)

 まさかの大幅アップ,自分くらいのレーティングで Easy を解けた方は同じような恩恵を受けたのだと思います。もうすぐ黄色になれる位置ですが,ここからはもっと大変そうです。 

 同じ部屋だった wrong さんが Redcoder になられたようです。おめでとうございます。

続きを読む

2011-03-19

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

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

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

=.ABCDE
--0:110:28---
1316+0/-1478888---

部屋内10位,全体284位

Rating:1637 → 1664 (+27)

 紫色になりました,hackをしなかったら 60 位くらい順位が上がり,hackが成功していたら 170 位くらい上がっていました。問題が難しいとちょっとの差が大きく響きます。

続きを読む

[][][][] SRM474 Div1 Level2 500 TreeCount 07:14 はてなブックマーク -  SRM474 Div1 Level2 500 TreeCount - 練習帳

テーマ:試行錯誤,実験の重要性

問題(要ログイン)

 http://www.topcoder.com/stat?c=problem_statement&pm=10805&rd=14185

要約

 連結無向グラフ G = (E, V) が与えられていて,頂点に 0 から N-1 まで番号が振られている。G に含まれる木で,0 から各点の最短距離が変化しないものの数を modulo 1000000009 で答えよ。つまり数えるのは次の条件を満たす G の部分グラフ

  • G' は木
  • V' = V
  • E' ⊂ E
  • 任意の頂点 i に対し,G' と G で 0 と i の最短距離は同じ

続きを読む

2011-03-17

[][][][] SRM475 Div1 Level2 600 RabbitIncreasing 01:47 はてなブックマーク -  SRM475 Div1 Level2 600 RabbitIncreasing - 練習帳

テーマ:pが素数ならZ/pZは体,Z/p^{k} Z → Z/p^{k-1} Zの標準的全射

問題(要ログイン)

 http://www.topcoder.com/stat?c=problem_statement&pm=10879&rd=14156

要約

 最初の年 (year 1) の 7 月にオスメスが 1 羽ずつ産まれ,その後次のサイクルをyear kまで繰り返す

  • 3 月に 1 歳を越えるつがい 1 組からオスメス 1 羽ずつが産まれる( 1 歳は含まない)
  • 4 月に同じ年齢のオスメスがつがいを作る

 1 から k の整数の部分集合が与えられ,その年が部分集合にあるならば,

  • 7 月に年齢の高い順に半分(小数点切り上げ)のつがいがいなくなる。

 year k の 12 月にいるウサギのつがいの数を mod 1,000,000,009で答えよ。k は 1 以上 10,000,000以下,部分集合の元の数は 1 以上 50 以下

続きを読む

2011-03-16

[][][][] SRM475 300 RabbitStepping 01:41 はてなブックマーク -  SRM475 300 RabbitStepping - 練習帳

テーマ:±1 のズレで心が折れないようにする訓練

問題(要ログイン)

 http://www.topcoder.com/stat?c=problem_statement&pm=10878&rd=14156

要約

 N 個のマス横に並んでおり,白,黒,赤いずれかに塗られている。そこに r 羽のウサギが等確率で配置され,次のアルゴリズムを繰り返す

  • ウサギが左右どちらに移動する。移動方向は乗っているマスの色と位置に応じて決まる。
  • もし同じマスにウサギが 2 羽いたら 2 羽とも除外される
  • 一番右端のマスが除外される(移動のルールからこのマスにウサギはいない)
  • 以上のステップをマスが 2 個になるまで繰り返す

 ウサギの移動方向は次のルールで決まる。

  • 左端のマスにいる場合は右へ
  • 右端とその左隣にいる場合は左へ
  • それ以外の場合
    • マスが白色なら左へ
    • マスが黒色なら右へ
    • マスが赤色の場合
      • 最初の移動の場合は左へ
      • 2 回目以降の移動場合その直前のステップにいたマスに戻る

 最終的に残るウサギの数は0,1,2匹のどれか。最終的に残るウサギの数の期待値を求めよ。

 最初のマスの数 N は 2 以上 17 以下,ウサギの数 r は 1 以上 N 以下

続きを読む

2011-03-15

[][] Manthan 2011 C. Sequence of Balls(未解答) 01:52 はてなブックマーク -  Manthan 2011 C. Sequence of Balls(未解答) - 練習帳

テーマ:編集距離

問題文

 Problem - 67C - Codeforces

要約

 2 つの文字列 A, B が与えられていて,A を操作して B に変更する。許されている操作は

  • A の任意の位置に任意の 1 文字を挿入する(コストt_i)
  • A の任意の 1 文字を削除する(コストt_d)
  • A の任意の 1 文字を別の 1 文字に置き換える(コストt_r)
  • A の隣り合っている文字を交換する(コストt_e)

A を B に変更するのに要するコストの最小値を求めよ。

 A, B の文字列は 1 文字以上 4000 文字以下で文字数は異なるかもしれない。それぞれの操作のコストは 0 以上 100 以下,コストの間には 2 * t_e >= t_i + t_d の関係が成り立つ。

続きを読む

2011-03-14

[][] Manthan 2011 01:08 はてなブックマーク -  Manthan 2011  - 練習帳

問題一覧:Dashboard - Manthan 2011 - Codeforces

結果:Standings - Manthan 2011 - Codeforces

=.ABCDE
--2:382:24---
574+0/-0150424---

部屋内18位,全体249位

Rating:1608→1637

上がるとは思わなかったです

続きを読む

2011-03-13

[][]プリム法を有向グラフに使用して失敗した例 04:58 はてなブックマーク - プリム法を有向グラフに使用して失敗した例 - 練習帳

Codeforces Beta Round #17 B. Hierarchy

問題文

 http://www.codeforces.com/problemset/problem/17/B

要約

 n 人の会社で,上司ー部下の関係を n-1 組作る。この関係の候補が m 個与えられていて,社員 a[i] が社員 b[i] を部下にするにはコスト c[i] がかかる(1 <= i <= m)。さらに,各社員には能力値が定められていて,社員 a[i] の能力値は社員 b[i] の能力値より高い事が保証されている。

 合計でかかるコストの最小値を求めよ。

 社員の数 n は 1 以上 1000 以下,候補の数 m は 0 以上 10000 以下,コスト c[i] は 0 以上 10^6 以下,能力値 q[j] は 0 以上 10^6 以下

続きを読む

2011-03-12

[][] Codeforces Beta Round #18 D Seller Bob 00:16 はてなブックマーク -  Codeforces Beta Round #18 D Seller Bob - 練習帳

問題文

 http://www.codeforces.com/problemset/problem/19/D

要約

 n 日間で商品を得て,それを売る事を行った。i 日目の行動は

  • 商売する日の場合:容量 2^x[i] のメモリースティックを買いたいお客がやってくるので,もし自分がその容量を持っていたらそれを価格 2^x[i] で売る。
  • 大会開催日の場合:大会に出場し,容量 2^x[i] のメモリースティックを獲得する。

 各日でメモリースティックは 1 個までしか持つことは出来ない。既にメモリースティックを持っている状態で大会に出場した場合,商品を受け取る( = 今持っているメモリースティックと交換する)か,商品を受け取らないかを選択できる。

 n 日終了時点で稼ぐお金を最大値せよ。

 n は 1 以上 5000 以下,xの各値は 0 以上 2000 以下。また,2 人以上のお客が同じ容量のメモリースティックを買い求める事はない。

続きを読む

2011-03-11

[][] Codeforces Beta Round #19 B Checkout Assistant 21:54 はてなブックマーク -  Codeforces Beta Round #19 B Checkout Assistant - 練習帳

テーマ:負のindexを持つDP

問題文

 Problem - 19B - Codeforces

要約

 レジで買い物客がn個の品物を会計する。品物iの価格 c[i] とそれをレジ係が会計するのに要する時間 t[i] 秒が与えられている。レジ係は品物を1個づつ処理する(処理する順番は自由に決められる)。品物iを会計している間に買い物客はi以外の品物を盗む事ができる。1つの品物を盗むのには1秒かかる(つまり品物iを会計中に買い物客は最大 t[i] 個の品物を盗める)。会計した品物は代金を支払わなければならず,盗んだ品物はその必要がない。買い物客が支払う代金の最小値を求めよ。

 品物の数 n は1以上2000以下,処理時間 t[i] は0以上2000以下,価格 c[i] は1以上10^9以下

続きを読む

2011-03-10

[][][]Top Coder Single Round Match 499 Div2 13:00 はてなブックマーク - Top Coder Single Round Match 499 Div2 - 練習帳

コンテスト結果概要

個人結果(要ログイン)

2500:09:41.494Passed System Test224.96
5000:17:19.184Passed System Test378.27
9500:47:41.300Opened0.00
Challenge..100.00

部屋2位,全体106位

Rating : 1198→1260

なんとかDiv.1に上がる事ができました。

次回は祝SRM500回大会,3/20 1:00から

続きを読む

2011-03-09

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

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

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

=.ABCDE
--0:540:27-1:03-
2580+0/-0342842-1396-

部屋内5位,全体131位

Rating:1466→1608

delta - Codeforces

続きを読む