2012-02-17

プログラミングコンテストの練習法と戦い方まとめ

Google Code Jam 2010 Round2 感想 - 科学と非科学の迷宮
http://d.hatena.ne.jp/shiumachi/20100608/1276005219
• とりあえず解く
• 解説を読んで再チャレンジ
• 他の人の解答を書き写す
• どういうロジックで動いているのか解析
• もう一度解く
• 人に説明する

team WAKABAでした練習のまとめ - kohyatohの日記 - TopCoder部
http://topcoder.g.hatena.ne.jp/kohyatoh/20111213/1323703954
実戦と同じ時間感覚で模擬戦を重ねる。
• 地道な練習がやっぱり効率がいい
• わからない問題を1日考えるのは、非効率に見えるが良い練習
• 難しめの問題を解いてこそ実力がつく

d3sxpにいた頃、意識していたこと - 歩くような速さで
http://d.hatena.ne.jp/kaming/20111201/1322762383
• Wrong Answerを出さない
• 問題を見逃さない
• 落ち着いて集中して取り組む

マラソンマッチの取り組み方 | システム工房コルン
http://www.colun.net/archives/294

上海交通大学のICPC事情 - awakia-nの日記
http://d.hatena.ne.jp/awakia-n/20100729

私と競技プログラミング。あるいは普通のプログラマがICPC世界大会に出場するまでとその後 - 純粋関数空間
http://tanakh.jp/posts/2011-12-18-icpc.html

大学の授業でICPC対策 - Competitive Programming Advent Calendar - Darseinのプロコン日記
http://d.hatena.ne.jp/Darsein/20111204

ICPC 雑感（来年出る人向け）: ymatsu雑記帳
http://azouno.seesaa.net/article/64712671.html

ICPCの練習方法 - miracle cafeteria
http://d.hatena.ne.jp/miracjp/20110129/1296281752

Topic-問題文の読み方
http://www.lab2.kuis.kyoto-u.ac.jp/~yanagis/acmicpc/topic/howtoread.html

引退＆これから参加する人へ - てきとーな日記
http://d.hatena.ne.jp/wata_orz/20100207/1265542862

TopCoderSRM 3桁レートの人のための攻略法 ~ 基本問題 DIV2 EASY を解くための思考ルーチン(俺流) ~
http://d.hatena.ne.jp/asi1024/20110831/1314777077

TopCoderSRM 緑コーダー(とか緑,青を往復する人)のための攻略法 ~ 初級問題 DIV2 MEDIUM(DIV1 EASY)を解くための思考ルーチン(俺流)
http://d.hatena.ne.jp/asi1024/20110901/1314868701

2011-08-28

JavaScriptでnext_permutation

JavaScript

JavaScriptでSTLのnext_permutationのようなものを実装してみました。

コード

// 昇順から降順へ順列を生成する
var next_permutation = function( d ) {
	var i = d.length - 1;
	while ( i > 0 ) {
		var k = i;
		i--;
		if ( d[i] < d[k] ) {
			var j = d.length-1;
			while ( d[i] >= d[j] ) {
				j--;
			}
			d[i] = d.splice( j, 1, d[i] )[0]; // d[i]とd[j]を入れ替える
			np_reverse( d, k, d.length-1 );
			return true;
		}
	}
	return false; // 次の順列が無いときはfalseを返す
}

// 配列dのa-b間を反転させる
var np_reverse = function( d, a, b ) {
	var sub = d.slice( a, b+1 ).reverse();
	for ( var i = a; i <= b; i++ ) {
		d[i] = sub[i-a];
	}
}

使用例

// テスト用
var test_next_permutation = function( d ) {
	document.write( 'source: ' );
	print_permutation(d);
	// 昇順に並べ替えておく
	d.sort( function(a,b) { return a > b } );
	var cnt = 0;
	// このような書き方で順番にアクセスできる
	do {
		document.write( ++cnt + ": " );
		print_permutation(d);
	} while ( next_permutation(d) );
}

// 順列を出力してみる
var print_permutation = function( d ) {
	var line = "";
	for ( var i = 0; i < d.length; i++ ) {
		line += d[i] + ", ";
	}
	line += "<br>";
	document.write(line);
}

実行結果その1: test_next_permutation( [1,2,3,4] )

普通の整数列

source: 1, 2, 3, 4, 
1: 1, 2, 3, 4, 
2: 1, 2, 4, 3, 
3: 1, 3, 2, 4, 
4: 1, 3, 4, 2, 
5: 1, 4, 2, 3, 
6: 1, 4, 3, 2, 
7: 2, 1, 3, 4, 
8: 2, 1, 4, 3, 
9: 2, 3, 1, 4, 
10: 2, 3, 4, 1, 
11: 2, 4, 1, 3, 
12: 2, 4, 3, 1, 
13: 3, 1, 2, 4, 
14: 3, 1, 4, 2, 
15: 3, 2, 1, 4, 
16: 3, 2, 4, 1, 
17: 3, 4, 1, 2, 
18: 3, 4, 2, 1, 
19: 4, 1, 2, 3, 
20: 4, 1, 3, 2, 
21: 4, 2, 1, 3, 
22: 4, 2, 3, 1, 
23: 4, 3, 1, 2, 
24: 4, 3, 2, 1,

実行結果その2: test_next_permutation( [1,1,3,4] )

同じものを含む場合

source: 1, 1, 3, 4, 
1: 1, 1, 3, 4, 
2: 1, 1, 4, 3, 
3: 1, 3, 1, 4, 
4: 1, 3, 4, 1, 
5: 1, 4, 1, 3, 
6: 1, 4, 3, 1, 
7: 3, 1, 1, 4, 
8: 3, 1, 4, 1, 
9: 3, 4, 1, 1, 
10: 4, 1, 1, 3, 
11: 4, 1, 3, 1, 
12: 4, 3, 1, 1,

実行結果その3: test_next_permutation( ['r','u','b','y'] )

文字もいける

source: r, u, b, y, 
1: b, r, u, y, 
2: b, r, y, u, 
3: b, u, r, y, 
4: b, u, y, r, 
5: b, y, r, u, 
6: b, y, u, r, 
7: r, b, u, y, 
8: r, b, y, u, 
9: r, u, b, y, 
10: r, u, y, b, 
11: r, y, b, u, 
12: r, y, u, b, 
13: u, b, r, y, 
14: u, b, y, r, 
15: u, r, b, y, 
16: u, r, y, b, 
17: u, y, b, r, 
18: u, y, r, b, 
19: y, b, r, u, 
20: y, b, u, r, 
21: y, r, b, u, 
22: y, r, u, b, 
23: y, u, b, r, 
24: y, u, r, b,

2011-08-23

SRM 366 DIV1 Easy/DIV2 Medium

SRM

ChangingSounds
URL: http://community.topcoder.com/stat?c=problem_statement&pm=7973

時刻付きで考えたことのログを取ってみた。

ギタープレイヤー、コンサートを開く　10:47 2011/08/23
全ての曲を同じ音量で弾くのは嫌だ　10:47 2011/08/23
曲ごとにボリュームを変更することにした　10:48 2011/08/23
各曲ごとに音量を上げるか下げるかする　10:49 2011/08/23
1つずつじゃなく、インターバルの量だけ増減する　10:51 2011/08/23
与えられるもの
　ギターの初期音量　10:49 2011/08/23
　ギターの最大音量　10:49 2011/08/23
　0<=音量<=最大音量 10:50 2011/08/23
求めるもの
　音量の最大値 10:50 2011/08/23
　音量が範囲外にならざるを得ないなら -1 10:53 2011/08/23
　→貪欲にやれるか？　10:52 2011/08/23
　　←出来るだけ増やす　10:54 2011/08/23
　　　←下げざるを得ないときだけ減らす　10:54 2011/08/23
　→全探索で間に合うか？　10:54 2011/08/23
　　←changeIntervalsの要素数は最大50個 10:55 2011/08/23
　　←音量の最大値は最大で1000 10:55 2011/08/23
　　　→DPのにおいがする　10:55 2011/08/23
　　　　←[何番目まで使ったか][音量]　10:56 2011/08/23
　→動的計画法　10:57 2011/08/23
　　←dp[i][j]: i番目のギターを演奏したとき音量jが最大値かどうか　10:58 2011/08/23
　　　←dp[0][beginLevel] = true 11:01 2011/08/23
　　　　←dp[i][j]がtrueならdp[i+1][j+I[i] ], dp[i+1][j-I[j] ]もtrueになるはず 11:02 2011/08/23
　→とりあえず動的計画法でやってみる　11:03 2011/08/23
　　→サンプル通った　11:12 2011/08/23　終了

2011-08-05

test

テストテスト