Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-19

SRM422 DIV1

| 03:28 | SRM422 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM422 DIV1 - TopCoder煮ブログ

250 と 500 を解けたつもりになったが、500 を Challenge された。全体的に点数が低めだったらしく、ついに Yellow に!

14601514

SRM 422 DIV1 全体では312位、TopCoder 全体では1132位。

PrimeSoccer

14分で解いて204pt。組み合わせを求めるところで時間かかってしまった。パスカルの三角形使うのがシンプルなのかなぁ。対偶で計算したけど、そのまま求めている人も多かった。

→上位の人は1回のインターバルで0回入る確率から順番に、n回のインターバルでどうなるかを順番に求めていってる。動的計画法か。

CavePassage

最大で N=13 ってことは 2^N * N^3 のアルゴリズムだったとしても高々10^7ぐらいなので力技コース。がんばって書き下したつもりだったが、詰めの甘さを発揮して Challenge で追撃された。思い当たる節を修正して System Test に提出してみたがやっぱり撃沈。根本的にどこかでバグがあるようだ。

(追記) 分かった。行った人と違う人が帰ってきてもいいのか! 自分の方針だと、{{3, 3, 6}, {1, 1, 1}, {"YYY", "YYY", "YYY"}, 6} が -1 になる。しかも、帰ってくる人が複数の場合もある。これは想定外!

WorkersOnPlane

見てすらいない。

感想

500を解きたかった…。が、今の実力ではこれは無理だ…。

今回から、TopCoder部 - ハチロク世代Skype chat に参加してみた。楽しい。

コードテンプレート

| 14:01 | コードテンプレート - TopCoder煮ブログ を含むブックマーク はてなブックマーク - コードテンプレート - TopCoder煮ブログ

いまのテンプレート。HTML は FileEdit の設定で HTML として出力するようにしている。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string.h>
using namespace std;

// BEGIN CUT HERE
template<class T> inline int __builtin_popcount(T n){return (n==0)?0:(1+__builtin_popcount(n&(n-1)));}
// END CUT HERE

class $CLASSNAME$ {
public:
	$RC$ $METHODNAME$($METHODPARMS$) {
		
	}

	$TESTCODE$
};

// BEGIN CUT HERE
int main(){
	$CLASSNAME$ __test;
	__test.run_test(-1);
}

// END CUT HERE
2009/01/03
M_PI を使うために #define _USE_MATH_DEFINES を追加
2013/10/06
memset を使うために string.h を追加

BirthdayCake (SRM422 DIV2 Hard)

| 15:31 | BirthdayCake (SRM422 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - BirthdayCake (SRM422 DIV2 Hard) - TopCoder煮ブログ

availableFruits を総当りで回すと 2^50 になってしまうので、friendsDislikings で回して 2^20 にする。これなら高々10^6程度。ただし、ビットフラグで管理すると 32bit に収まりきらないのでミスを連発。んーむ。特に、__builtin_popcount は int にキャストされてしまうので要注意。

TZTester 改

| 22:54 | TZTester 改 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TZTester 改 - TopCoder煮ブログ

TZTester ビルド - TopCoder煮ブログ - TopCoder部 の続き。

http://tech.nitoyon.com/misc/topcoder/

  • コードを整形してテストを追加・修正しやすくした
  • 配列の要素が空のときにエラーにならないようにした

memset と std::fill

| 00:14 | memset と std::fill - TopCoder煮ブログ を含むブックマーク はてなブックマーク - memset と std::fill - TopCoder煮ブログ

memset はバイト単位で値を設定する。int の配列や double の配列を特定の値で初期化する場合は、std::fill を用いるべし。

// 0 はうまくいく
int A[10];
memset(A, 0, sizeof(A));
// A[0] -> 0
// A[1] -> 0

// が、1 は意図しない結果に
memset(A, 1, sizeof(A));
// A[0] -> 16843009 (=0x01010101)
// A[1] -> 16843009 (=0x01010101)

// そういう時は std::fill
fill(A, A + 10, 1);
// A[0] -> 1
// A[1] -> 1

fill の第二引数は最後の要素 + 1の場所を指定する。vector などの end() と同じ扱い。

CavePassage (SRM422 DIV1 Medium)

| 00:29 | CavePassage (SRM422 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CavePassage (SRM422 DIV1 Medium) - TopCoder煮ブログ

解けている人の解法を見ると、次の方針でやっているようだ。

  • 2^N と行ったとき帰ったときの2通りの状態(=16384通り)がある。
  • それぞれを移りながらダイクストラ法で解いていく。
    • 16384^2 の状態をグラフとして持つのは大変なので、ノード一覧だけ保持して計算していく。
    • ダイクストラ法はメモリ量が少ない!!

C++ 一位の人のソースを理解したあとで暗証してみた。細かい部分がより分かるようになった。priority_queue を使わない方法も試してみて、ダイクストラ法への理解が深まった気がする。