Hatena::Grouptopcoder

TopCoder煮ブログ

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

2008-10-29

SRM423 DIV1

| 11:56 | SRM423 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM423 DIV1 - TopCoder煮ブログ

撃沈。むずい。

15141459

0点だからしかたなし。

TheTower

題意がつかめず撃沈。普通に解いても爆発するので、何らかの工夫が必要なんだろうが思いつかん。

TheEasyChase

素直に書いてみたが何らかのバグがあり撃沈。たぶん、バグがなくても時間内に終了しなかったと思われる。

(追記) 結果がでたあとに、同じ room 内の人に適当に自分が考えた Test case(盤面が20x20で適度に追いかけっこが発生するもの)を与えると撃沈した。ダメもとで乱発すればよかったのかもしれん。

TheBeautifulBoard

一瞬見たが諦め。

TheTower (SRM423 DIV1 Easy)

| 00:35 | TheTower (SRM423 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TheTower (SRM423 DIV1 Easy) - TopCoder煮ブログ

chokudai さんに教えてもらったあとにじっくり考えて理解。

気付けば簡単なんだが・・・。

  1. x, y を独立に考えられる
    • マンハッタン距離なので、点が集まる座標は x と y を別々に考えてよい。
    • 以下の 2. では x 座標を求めることを考える(例0のパターン)。
  2. 集まる先の x 座標は n 個の点の x 座標のうちのどれかだと考えてよい
    • 例えば、2個の点だと、x0~x1 の間の全ての x 座標がありうる
    • 例えば、3個の点だと、x0 < x1 < x2 だとすると、最終的な座標は x1 以外にはありえない
      • x1 + 1 と x1 までの移動距離の違いを考えてみると分かりよい。
      • x1 に比べて、x1 + 1 は点0、点1 の2つが余計に1つ右に動き、その分、点2 の移動分が1つ減る。よって、x1 + 1 は x1 までに比べて、1つ移動量が多い。
      • 同様に、x1 に比べて、x1 - 1 は1つ移動量が多い
    • このように、必ずどれか1つの x 座標か、隣接する2つの x 座標の間に集まる(必ずしも中央の点に集まるわけではなさそう)
    • だから、n 個の点の x 座標のうちのどれかだと考えてよい(間になる場合はその両端のどちらかだと考えて無視していい)
  3. n 個の点の x, y を全て組み合わせた n^2 通りの座標について調べればよい
    • n 個の中から i 個の全ての組み合わせに対して移動距離を求めるのは大変
    • 魔法の作戦がある!
      • n 個の点のそれぞれと最終地点の距離を調べてソートする
      • ソート結果の最初の2つを足したものは、min(nC2の点から最終地点までの距離の和)である
      • 最初の3つを足したものは…以下同じ
  4. n^2 通りについて最小の移動距離が求まるので、その全ての点のうち最小のものを返せばよい

これを3分台で解ける人がいるのが理解できない……。

2008-10-28

BirthdayReminders (SRM412 DIV2 Medium)

| 03:43 | BirthdayReminders (SRM412 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - BirthdayReminders (SRM412 DIV2 Medium) - TopCoder煮ブログ

順番に求めていけばいいかと思いきや、優先順位がちょっと厄介。ならば、全ての組み合わせでの誕生日を記憶しておいて、選ばれたものから次の誕生日で上書きしてやればよい。

STL の練習がてら、operator < を定義した構造体にデータを格納して、set に格納していった。こうすれば誕生日が近く、また、優先順位の高いものから順番に並んでくれる。多少ロジックミスで手間取ったが、System Test には合格。やったね。

上位の人の回答をみたらもっと直接的に解いていた。friendNames と occasions の2次元配列に次の誕生日を格納していって、最小のものを調べている。優先順位も occations が小さいものから調べていけば実現できてしまう。なるほどねー。

以下、ソース。

続きを読む

比較関数

| 09:43 | 比較関数 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 比較関数 - TopCoder煮ブログ

上で貼り付けたソースは

    bool operator <(const Birthday& bd) const{
        if(date < bd.date) return true;
        if(date == bd.date){
            if(occ < bd.occ) return true;
            if(occ == bd.occ){
                return f < bd.f;
            }
        }
        return false;
    }

と冗長な感じだったけど、Java 1位の人のソースを見ていて、次のようにシンプルに書けることが分かった。

    bool operator <(const Birthday& bd) const{
        if(date != bd.date) return date < bd.date;
        if(occ != bd.occ) return occ < bd.occ;
        return f < bd.f;
    }

シンプルだと分かりやすい。

2008-10-26

KPlanetaryAlignment (SRM414 DIV1 Hard)

| 22:57 | KPlanetaryAlignment (SRM414 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - KPlanetaryAlignment (SRM414 DIV1 Hard) - TopCoder煮ブログ

難しそうだったので、とりあえず力技で解く。やはり入力の規模が大きくなると時間がかかりすぎるが、題材が面白かったこともあって勉強になった。


模範解答を探して結果を見たら解けた人は1人のみ。泥臭かったらどうしようと思ったがすごく綺麗なコード。惑星が k 個重なる組み合わせごとに、一直線になる周期を記録している。最後に、それぞれの組み合わせについて、数え上げていく。重複してカウントするのを防ぐために、k個同時を足して、k + 1個同時を引いて、k + 2個同時を足して、k + 3を引いて…としている。円がn個のベン図を考えると分かりよい。かっこいい。分子分母の情報が重要になるので、有理数クラスを作って表現しているところもポイント。

Match Overview の Collect %

| 23:03 | Match Overview の Collect % - TopCoder煮ブログ を含むブックマーク はてなブックマーク - Match Overview の Collect % - TopCoder煮ブログ

Collect %
  = Submission Accuracy
  = Correct / Submitted * 100
  = (Submitted - Failed by Challenge - Failed by System Test) / Submitted * 100
  • Submissions が少ない → 解かずに諦めた人が多い
  • Collect が少ない → はまりポイントがある

TreeCount (SRM413 DIV1 Hard)

| 01:05 | TreeCount (SRM413 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TreeCount (SRM413 DIV1 Hard) - TopCoder煮ブログ

きっと動的計画法なんだろうなと思ったものの、何から算出していくかが皆目検討つかず諦めて答えを見る。問題C++トップの人の回答は理解しにくかったので、全体トップの人の回答を読み進める。なんかうまく計算しているっぽいが、F と G の意味を掴みかねる。解けてる人は同じ方針のようなのだが…難しい…。

LavonLavon2011/07/08 02:06Gee whiz, and I tohught this would be hard to find out.

ezonlvzzezonlvzz2011/07/09 22:23JvdRbr , [url=http://nrkrnawayroz.com/]nrkrnawayroz[/url], [link=http://dahqqmnzaikt.com/]dahqqmnzaikt[/link], http://abtsyryszdck.com/

lsztkrmlsztkrm2011/07/11 01:06avBaTE <a href="http://jfonyhaisomt.com/">jfonyhaisomt</a>

dojczvlyoeydojczvlyoey2011/07/11 23:03iHNjn2 , [url=http://atbxicznuqng.com/]atbxicznuqng[/url], [link=http://jurrdqdadcrh.com/]jurrdqdadcrh[/link], http://sajjqxxxxowc.com/

2008-10-25

upper_bound と lower_bound(とdistance)

| 23:28 | upper_bound と lower_bound(とdistance) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - upper_bound と lower_bound(とdistance) - TopCoder煮ブログ

upper_bound と lower_bound が返す場所への理解が曖昧だったので、実証コードを書いて理解を深めた。

図にするとこんな感じ。

  1   1   3   3   5
  | upper_bound 0
          | upper_bound 1
          | upper_bound 2
                  | upper_bound 3

  1   1   3   3   5
  | lower_bound 0
  | lower_bound 1
          | lower_bound 2
          | lower_bound 3

upper_bound はその数を超える最初の場所を指す。lower_bound はその数以下の最大の数字を指す。同じ値が複数あった場合、upper_bound も lower_bound も先頭を指す。

以下、少し長いけど実証コード。イテレータの場所をインデックス番号で取得するために std::distance() を使ってみた。イテレータはポインタみたいに引き算で差分ができなくて悩んだ。


void main(){
    vector<int> v;
    v.push_back(1); v.push_back(1);
    v.push_back(3); v.push_back(3);
    v.push_back(5);

    vector<int>::iterator p;
    p = upper_bound(v.begin(), v.end(), 0);
    cout << distance(v.begin(), p) << endl; // 0
    p = upper_bound(v.begin(), v.end(), 1);
    cout << distance(v.begin(), p) << endl; // 2
    p = upper_bound(v.begin(), v.end(), 2);
    cout << distance(v.begin(), p) << endl; // 2
    p = upper_bound(v.begin(), v.end(), 3);
    cout << distance(v.begin(), p) << endl; // 4

    p = lower_bound(v.begin(), v.end(), 0);
    cout << distance(v.begin(), p) << endl; // 0
    p = lower_bound(v.begin(), v.end(), 1);
    cout << distance(v.begin(), p) << endl; // 0
    p = lower_bound(v.begin(), v.end(), 2);
    cout << distance(v.begin(), p) << endl; // 2
    p = lower_bound(v.begin(), v.end(), 3);
    cout << distance(v.begin(), p) << endl; // 2
}

2008-10-22

間違えた

12:35 | 間違えた - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 間違えた - TopCoder煮ブログ

SRM 423 は来週だった。

2008-10-21

WorkersOnPlane (SRM422 DIV1 Hard)

| 01:28 | WorkersOnPlane (SRM422 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - WorkersOnPlane (SRM422 DIV1 Hard) - TopCoder煮ブログ

しばらく考えて分からなかったので全体一位の人(neal_wuさん)のコードをみた。まず、ある W から到達できる G と S を列挙している。この情報を元に、次のような最大フロー問題を考える。

            /-S\
  /G---W---W--S-\
S--G--/     \-S--D
  \G---W---W--S-/

どの組み合わせを選ぶかは、最大で何本のフローを流せるかに帰着する。

問題を解くには Edmonds-Karp 法を使う。最短路を求めるところは、ちょっと工夫した深さ優先探索で実施している。(ゴールから順番に枝を確認していけば、自動的にそれは最短路になる)

一点、逆順に流れを記録している理由がよく分からん…。たしかに、これをしないと System Test で落ちている。

→ 試してみた。逆流する余地を残している。逆流して流れる場合は、イメージ的には以前の道を付け替えるような感じ。Edmonds-Karp 法での流量分減らす処理に対応している。

最大フロー問題と Edmonds-Karp 法が少し分かった気がする。

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 を使わない方法も試してみて、ダイクストラ法への理解が深まった気がする。

2008-10-18

FloorIndicator (SRM421 DIV2 Hard)

| 14:27 | FloorIndicator (SRM421 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - FloorIndicator (SRM421 DIV2 Hard) - TopCoder煮ブログ

普通に解いたら System Test にも通った。522pt。平均を求めるところで全組み合わせを列挙したら時間オーバーしそうだったので、各桁ごとに平均を出して足し合わせた。C++1位の人とだいたい同じソース。

WalkingDistance (SRM417 DIV1 Hard)

| 18:11 | WalkingDistance (SRM417 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - WalkingDistance (SRM417 DIV1 Hard) - TopCoder煮ブログ

ダイクストラ法使って解こうとしたら撃沈。C++ トップの人のコードをみて学習。任意の2地点間の最短距離を求めるにはウォーシャル・フロイド法というのがシンプル。そのあとに、最短路の最大長のループを求めて、2で割って返してる。

wikipedia:ワーシャル-フロイド法, はてなダイアリー

DancingCouples (SRM416 DIV2 Hard)

| 22:52 | DancingCouples (SRM416 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - DancingCouples (SRM416 DIV2 Hard) - TopCoder煮ブログ

力技で求めるしかなさそうだったので普通に再帰で。普通に System Test したら普通に時間オーバーになった。普通にキャッシュしたら普通に Sytem Test に通った。この問題、計算時間の見通しを立てにくい。

TZTester ビルド

| 00:30 | TZTester ビルド - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TZTester ビルド - TopCoder煮ブログ

TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed を参照してプラグインを導入してみて快適になっている。

ただ、TZTester の吐くコードが気に食わなかったのでソースを修正してビルドしてみた。

  1. JDK をインストール (1.4.2 でいけた)
  2. http://www.topcoder.com/contest/classes/ContestApplet.jar をダウンロードしておく
  3. ソースを http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins から入手
  4. コンパイル: javac -classpath ContestApplet.jar -deprecation TZTester.java
  5. jar 化: jar cvf TZTester.jar TZTester.class
  6. 既存の TZTester.jar に上書きして ARENA を再起動

ひとまずは、テストコードに適度に改行を入れて、自分でテストを追加しやすいようにした。空の vector でコンパイルエラーになるバグも修正したい。→改善した http://topcoder.g.hatena.ne.jp/nitoyon/20081019/1224424489

2008-10-13

NextNumber (SRM416 DIV1 Easy)

| 10:59 | NextNumber (SRM416 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - NextNumber (SRM416 DIV1 Easy) - TopCoder煮ブログ

勢いよく Submit したが、System Test で撃沈。凡ミス。

C++ 一位の人の回答がスマートすぎる。

  1. (N & -N) で最下位ビットが分かる
    • 補数表現は最下位ビットが重複する
  2. 最下位ビットを足す
    • 必ず繰り上がりが起きてビット数が同じか小さくなる
  3. ビット数が小さくなったら、減った分だけ加算
    • (1 << num) - 1
    • (例)num が 3 のときは、7(111)

CubeNets (SRM417 DIV1 Medium)

| 18:22 | CubeNets (SRM417 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CubeNets (SRM417 DIV1 Medium) - TopCoder煮ブログ

サイコロ問題。展開図を回すのではなく、展開図の上をサイコロを転がすとよいようだ。C++ 1位の人は、展開図全面をサイコロごろごろ転がして、全部の面に # がヒットしたら YES を返してる。なるほど…。

YearProgressbar (SRM420 DIV2 Medium)

| 18:57 | YearProgressbar (SRM420 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - YearProgressbar (SRM420 DIV2 Medium) - TopCoder煮ブログ

勢いよく書いたが System Test で撃沈。うるう年の時に3月以降なら1日足すところを、if(M > 2 && isLeap(Y)) days++; とやっていた。月は 0 base で保持していたので、3月は 2。M >= 2 としたら成功。こんなしょぼいミスばっかり。

PrettyPrintingProduct (SRM420 DIV2 Hard)

| 23:22 | PrettyPrintingProduct (SRM420 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - PrettyPrintingProduct (SRM420 DIV2 Hard) - TopCoder煮ブログ

上位桁と下位桁を別々に計算すればよい。方針は合っていたが、できる限り多く保持しようとして、long long が桁あふれしてしまった。

64bit で表せる数が 0~1.8*10^19。かけていく数は最大10^6なので、low, high ともに 10^12 ぐらいに留めるべきだった。

2008-10-12DIV1 Easy 集中特訓

ForbiddenStrings (SRM412 DIV1 Easy)

| 12:34 | ForbiddenStrings (SRM412 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ForbiddenStrings (SRM412 DIV1 Easy) - TopCoder煮ブログ

違うアルファベットが何個続いているかを覚えておいて数だけを計算。これも DP か。早くはないが、一発 OK。

ArithmeticProgression (SRM413 DIV1 Easy)

| 13:40 | ArithmeticProgression (SRM413 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ArithmeticProgression (SRM413 DIV1 Easy) - TopCoder煮ブログ

上界と下界を順番に調べていって、範囲が不正なら -1 とする。ほとんどできていたのに条件を1つ忘れて、System Test で撃沈…。細かいミスが多いのをなんとかせねば。

ShipLoading (SRM415 DIV1 Easy)

| 20:12 | ShipLoading (SRM415 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ShipLoading (SRM415 DIV1 Easy) - TopCoder煮ブログ

sort して upper_bound を使って。C++ 一位の人とほとんど同じコードだった。嬉しい。<algorithm> 便利!

std::accumulate

| 20:19 | std::accumulate - TopCoder煮ブログ を含むブックマーク はてなブックマーク - std::accumulate - TopCoder煮ブログ

コンテナの値を加算するには std::accumulate が便利。numeric の include も忘れずに。

使用前:

// vec は vector<string> とする
string s = ""
for(int i = 0; i < vec.size(); i++){
    s += vec[i];
}

使用後:

#include <numeric>

string s = accumulate(vec.begin(), vec.end(), string());
// 第3引数は初期値

2008-10-11

HoleCakeCuts (SRM411 DIV1 Medium) その2

| 00:15 | HoleCakeCuts (SRM411 DIV1 Medium) その2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HoleCakeCuts (SRM411 DIV1 Medium) その2 - TopCoder煮ブログ

その1の続き。塗り別け問題として解いてみた。冗長なところが多いけど、一発でSystem Test は通った。でも、慣れてないので時間かかった。

DIV2 で C++ 一位の人は、格子点の間を表現するために、座標を二倍にしていた。なるほど、すっきり。

DIV1 で C++ 一位の人は、驚くほどソースが短い。ケーキの外側を切れ目に含めてる。あとは、それぞれの四角が、hole によって分断される場合、なかったことになる場合を調べてる。鮮やかだなー…。

vector の検索

| 00:23 | vector の検索 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - vector の検索 - TopCoder煮ブログ

for で回すのは面倒。2分探索を使えばよい。

使用前:

// value を探す
bool found = false;
for(int i = 0; i < v.size(); i++){
  if(v[i] == value){
    found = true;
    break;
  }
}

if(found){
  // 見つかったときの処理
}

使用後:

#include <algorithm> // sort, binary_search
using namespace std;

sort(v.begin(), v.end());
if(binary_search(v.begin(), v.end(), value)){
  // 見つかったときの処理
}

binary_search するためには sort が必須なので注意。

begin() と end() をいちいち書くのが面倒なので

#define ALL(A) (A).begin(),(A).end()

のようなマクロを書いてる人がそこそこそいるようだ。

最小値演算子・最大値演算子

| 03:48 | 最小値演算子・最大値演算子 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 最小値演算子・最大値演算子 - TopCoder煮ブログ

g++ 独自の演算子。deprecated と warning は出るが動く。

a <? b
数値 a と b のうち小さいほうを返す最小値演算子
a >? b
数値 a と b のうち大きいほうを返す最大値演算子
http://www.asahi-net.or.jp/~WG5K-ICKW/html/online/gcc-2.8.1/gcc_4.html#IDX416
a <?= b;

a = min(a, b);

と同じ。

SentenceDecomposition (SRM411 DIV1 Easy)

| 03:52 | SentenceDecomposition (SRM411 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SentenceDecomposition (SRM411 DIV1 Easy) - TopCoder煮ブログ

素直に解いたら System Test の 50! 通りになる場合で時間オーバー。撃沈。文字長で動的計画法すべきだった。DIV1 の 250 の正答率を上げねば。

JawadJawad2012/09/01 13:04I can't bieleve I've been going for years without knowing that.

kdvyqyavzjikdvyqyavzji2012/09/02 04:27Kpeubu <a href="http://mqmbkmhedzjw.com/">mqmbkmhedzjw</a>

pqtofnzpqtofnz2012/09/04 17:50GdHgEq , [url=http://swjxqfenbdnc.com/]swjxqfenbdnc[/url], [link=http://qhqvwwbnhitb.com/]qhqvwwbnhitb[/link], http://tpccblpzwmkt.com/

2008-10-09

SRM421 DIV1

| 02:02 | SRM421 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM421 DIV1 - TopCoder煮ブログ

250と500を解けたつもりになったが、250 が System Test で落ちた。

12681460

うっひょい。250 が行けてたら、Yellow だったなぁ…。

EquilibriumPoints

ちょっと時間かかった。計算式はあっていたが、誤差以内に収まるかどうかをきちんと検証していなかったので System Test に落ちた。

両端の差が 1e-9 以下になるまで半分ずつつめて行く必要あり。100回ループ回してる人もいた。1000/2^100 は 1e-9 以下になるのは当たり前。そういう概算に強くならねば。

CakesEqualization

20分ぐらい戦略誤って解いていて、諦めかけた瞬間にひらめいた。最初にひらめいてれば、あと15分は縮められたはず…。

TeamManagement

残り10分ぐらいで問題だけみた。友達関係をグラフに見立てて、深さ優先で探索していけばいいような気がする。あとで。

感想

初めて DIV1 の 500 が解けた! 250 も解けてれば、レートがかなり上がっただろうに。残念。

2008-10-08

HoleCakeCuts (SRM411 DIV1 Medium) その1

| 23:44 | HoleCakeCuts (SRM411 DIV1 Medium) その1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HoleCakeCuts (SRM411 DIV1 Medium) その1 - TopCoder煮ブログ

勢いで解こうと悩んだが時間切れ。

しばらく頭を冷やして挑んだら、すごくかっこいい答えができた。たまにはコードをここに書いておこう。

int cutTheCake(int cakeLength, int holeLength, vector <int> horizontalCuts, vector <int> verticalCuts)
{
    int h = 0, v = 0;
    for(int i = 0; i < horizontalCuts.size(); i++){
        if(-holeLength <= horizontalCuts[i] && horizontalCuts[i] <= holeLength){
            h++;
        }
    }
    for(int i = 0; i < verticalCuts.size(); i++){
        if(-holeLength <= verticalCuts[i] && verticalCuts[i] <= holeLength){
            v++;
        }
    }

    int total = (horizontalCuts.size() + 1) * (verticalCuts.size() + 1);
    int inner = max(0, h - 1) * max(0, v - 1);
    total -= inner;

    if(h == 0) total += max(0, v - 1);
    if(v == 0) total += max(0, h - 1);
    return total;
}

ざっと解説。

  1. 穴に交わる数をカウントする
  2. 穴がなかったときに何個になるかを total に入れる
  3. 穴の中にある数を引く
  4. 穴があることで上下に分断される場合を加算する

図を描くと分かりやすい。

DIV2 の C++ トップの人は、塗り分け問題として解いていた。法則を導き出せないときは、そうやって機械的に解いた方が確実だろう。あとで試そう。

その2 に続く

2008-10-05DIV1 Medium 特訓中

CustomDice (SRM416 DIV1 Medium)

| 12:22 | CustomDice (SRM416 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CustomDice (SRM416 DIV1 Medium) - TopCoder煮ブログ

んー、解けない…。

しばらく考えて方針は決まったがコードに落とせない。1位のコードを見たら見事。んー、読めるが書けない。

動的計画法の適用

一応まとめておく。

平均 M をみたす全ての組み合わせを見つけるために、さいころの値が変わる面の数を順番に増やしながら DP していく。

例えば、2面だったとして、合計が24(21 + 3)になる組み合わせ D3 は以下の2通り(1 2 3 4 5 6 からの差分で記している)。

1: 0 0 0 0 0 3
2: 0 0 0 0 1 2

2面が変わるときに合計が27(21 + 6)になる組み合わせ D6 は以下の3通り。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3

では、3面を変えるときを許容した場合、D6 の増分は D3 の要素数になる。

なぜか。D3 の各要素に 0 0 0 1 1 1 を足すと、3面変わるときに取りうる全ての組み合わせになるからだ。

具体例を見れば納得できるはず。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3
5: 0 0 0 1 1 4  (←0 0 0 0 0 3 + 0 0 0 1 1 1)
6: 0 0 0 1 2 3  (←0 0 0 0 1 2 + 0 0 0 1 1 1)

4面変わるときの D6 は同じように、D2 に 0 0 1 1 1 1 を足す。結果として、D6の組み合わせは次のようになる。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3
5: 0 0 0 1 1 4
6: 0 0 0 1 2 3
7: 0 0 1 1 1 3  (←0 0 0 0 0 2 + 0 0 1 1 1 1)
8: 0 0 1 1 2 2  (←0 0 0 0 1 1 + 0 0 1 1 1 1)
9: 0 1 1 1 1 2  (←0 0 0 0 0 1 + 0 1 1 1 1 1)
0: 1 1 1 1 1 1  (←0 0 0 0 0 0 + 1 1 1 1 1 1)

同じように、これに 1 1 1 1 1 1 を足したものは、D12 の6面変わるときの組み合わせを出すときに利用できる。

InfiniteSequence2 (SRM413 DIV1 Medium)

| 14:50 | InfiniteSequence2 (SRM413 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - InfiniteSequence2 (SRM413 DIV1 Medium) - TopCoder煮ブログ

そのまま再帰で計算するしかないんで、そのままコーディング。キャッシュしたら案の定、System Test で落ちた。トップのコードを読むと、キャッシュの範囲を限定していた。なるほど。一番参照される場所をメモリが許す範囲でキャッシュするわけか。

StringsAndTabs (SRM412 DIV1 Medium)

| 23:04 | StringsAndTabs (SRM412 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StringsAndTabs (SRM412 DIV1 Medium) - TopCoder煮ブログ

出題文を読んで仕様を漏れなくきちんと実装していくだけ。複雑な仕様を丁寧に実装することが求められている問題。同じ音程の弦がある場合や音程が降順じゃない場合などは、Challenge Phase で追撃に使えそう。

リーディングとコーディングに時間かかったけど、System Test は一発で通って嬉しい。

2008-10-04

RedIsGood (SRM420 DIV1 Medium)

| 16:27 | RedIsGood (SRM420 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - RedIsGood (SRM420 DIV1 Medium) - TopCoder煮ブログ

4時間かかってやっと解けた。できたコードは30行ほど。4時間で30行って、だめすぎるプログラマだ…。

思考経路

  1. 再帰で解いていけばいいはず。効率よくするためにキャッシュいるよね。
  2. R, B の箱を作って、その中に期待値を突っ込んでいけ。
  3. 期待値の算出をしばし悩む。
  4. やっとできた。時間遅いけど、手元だと動くよね。
  5. TopCoder 鯖で実行すると、std::bad_alloc で落ちる。double×5001×5001 でメモリ足りない。ざっと200M か…。
  6. 困った。
  7. 困った。
  8. 困った。
  9. 動的計画法に変える。あれ、それでもメモリ量変わらん?
  10. あ、R, B の値を求めるとき、R-1, B と R, B-1 が分かれば十分なのか
  11. ということは、左上から順番に計算していけば、ほとんどキャッシュする必要ない。
  12. しばしコーディング。
  13. 慣れてないので時間かかる。
  14. できた。すぐ終わる。すごい。

感想

再帰だと上手くやらないと時間かかったりメモリ食いすぎたりする場合も、動的計画法だと簡単に書けた。具体例を実感できて有意義だった。まだ動的計画法に慣れていないので、いつ使うのか、どうやって使うのかが直感的に思いつかない。繰り返せば慣れるのかなぁ…。

TopCoder SRM 420 Div1 - chokudaiの日記(仮) がとても参考になった。ありがたや。

その後、早い人の解をみた。できたコードのエッセンスは同じだ。しかし、3分40秒で解いてるのがすごすぎる。コードが一瞬で頭の中にできあがって、あとは書くだけなんだろな…。

StringInterspersal (SRM414 DIV1 Medium)

| 00:16 | StringInterspersal (SRM414 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StringInterspersal (SRM414 DIV1 Medium) - TopCoder煮ブログ

500点問題の練習。と思ったらすごく簡単だった。正答率50%。ま、そんなもんだろうな。番兵を最後におけばシンプルなコードになった。

CollectingPostmarks (SRM415 DIV1 Medium)

| 02:41 | CollectingPostmarks (SRM415 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CollectingPostmarks (SRM415 DIV1 Medium) - TopCoder煮ブログ

制限時間に計算を終わらせる方法が分からない。そのまま調べると2^32通りになってしまう。案の定、System Test でタイムオーバー。諦めて模範回答を見る。

2分割する手法をとっている。

  1. 半分ずつ分割する
  2. それぞれの組み合わせで値と値段を求める(2^16×2=12万通り)
  3. それぞれの組み合わせで値でソート
  4. それぞれの結果を見比べて K を超えるものを調べていく(16^2=256通り)

なるほど。2分割してマージしてる。分割統治法か!

正答率14.58%。解けなくても仕方がないとするか。2^32 で解くところまでなら書けたので、あとは2分割することを思いつくかどうかだ。

2008-10-03

日本人上位coder

| 18:11 | 日本人上位coder - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 日本人上位coder - TopCoder煮ブログ

はてな界隈で SRM キーワードで探してきた中から、yellow 以上の人をピックアップ。

問題の振り返りをブログでしてくれてるので、非常に参考になる。

とてもじゃないけど追いつけなさそうで絶望的になる…。

SRM420 DIV1

| 21:27 | SRM420 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM420 DIV1 - TopCoder煮ブログ

1問だけ解けた。

12421268

SolitaireSimulation

前回 0 だったので、慎重に解いたら18分かかった。ostringstream を初めて使ったり、multiset を初めて使ったりしてるうちに、時間を浪費してしまった。上位の回答を見ていると、vector を std::sort してそのまま使ってる人が多い。ふむふむ。

RedIsGood

なんか難しそうだったのでパス。意外に解けてる人が多かった。あとで。

ChangeOMatic

簡単そうに見えて挑戦するも、時間内に解けず。遅い。トップダウンで方針は決定したものの、ボトムアップで書いて悩んでるうちに、全体を見失って混乱してしまった。あとで。

感想

DIV1 の 500 を解けたことがない。そこを解けるようにならないと、yellow は遠い。

algorithm の壁

| 23:48 | algorithm の壁 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - algorithm の壁 - TopCoder煮ブログ

std::sort 便利。vector をソートするには

sort(vec.begin(), vec.end());

とする。第3引数で関数オブジェクトを渡す比較方法を変えられる。greater を渡すと降順になる。

sort(vec.begin(), vec.end(), greater<int>());

関数オブジェクトおもしろい。

map みたいなこともできる。

vector<int> vec;
vec.push_back(1);
vec.push_back(3);
vec.push_back(2);
transform(vec.begin(), vec.end(), vec.begin(), negate<int>());
// -1 -3 -2

全部の要素の正負が反転する。

要素を足すには plus 関数オブジェクトの片方を束縛してやる。

transform(vec.begin(), vec.end(), vec.begin(), 
  bind1st(plus<int>(), 1));
// 2 4 3

count_if なんかも便利そう。remove_if は終端の場所が iterator で帰ってくるので要注意。