Hatena::Grouptopcoder

TopCoder煮ブログ

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

2008-09-30

StampsCollection

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

DIV1 むずいの続き。

こないだ挫折した SRM418 DIV1 Level2 の StampsCollection の答えを読解。

  • グラフに置き換える
    • demand は節点
    • price は節点の重み
    • 同じ stamp を欲しがってる節点同士を枝で結ぶ

3) の例だとこんな感じ。

 ┌─┐    ┌─┐    ┌─┐
 │5│----│9│----│5│
 └─┘    └─┘    └─┘

誰が購入するかを決定することは、「枝を共有しないような節点を選ぶ」と等価になる。収入を最大化するということは、重みを最大化するように選ぶこととなる。つまり、これは最大次数が2の wikipedia:最大独立集合問題 だ、と。

上の例だと、左の2つの節点(5 と 9)を選択してしまうと、枝(Stamp 0)を2人が欲しがってしまうので NG。9(真ん中の節点)もしくは、5+5(両端の節点) のいずれかで、答えは10となる。

んー、言われれば納得するが思いつかない…。

で、解法。

  1. 深さ優先探索して節点をグループ分け
  2. 各グループについて、最大値を求める。
    • 最大次数2なので、一本道もしくは閉路のどちらか
    • 奇数番目、偶数番目だけを選んだときの最大値を求めればよし
    • ただし、閉路のときには少し気をつける

2008-09-29

CactusCount

| 01:12 | CactusCount - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CactusCount - TopCoder煮ブログ

DIV2 で5人しか答えられなかった CactusCount にチャレンジ。答えを導くコードは書けたものの、O(n^2) ぐらいで n=200 のときに時間かかりすぎ。

諦めて答えをみて勉強中。全体3位の人のソースが読みやすかったので読解。

「ループを探すにはDFS(深さ優先探索)で経路を記録すればよい」

なるほど。BFS(幅優先探索)でやろうとして破綻してた。DFS と BFS の性質を体で理解せねば。

2008-09-26

SRM419 DIV1

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

3回目。一問も解けなかった…。

1388 -> 1242

なんとか DIV1 に残ってる。

Undo

勢いよく書いたら境界条件でしくっていて、Challenge で撃墜された。

さすが、DIV1。ミスへのツッコミが厳しい。どちみち、System Test で失敗してたけど。

NimForK

しばらく悩んだが、紙に状態を書き出したら方針が見えてきた。が、時間切れ。

CactusAutomorphisms

ちょっと見たがすぐに諦め。4人しか解かず、正解した人は1人。

DP

20:33 | DP - TopCoder煮ブログ を含むブックマーク はてなブックマーク - DP - TopCoder煮ブログ

topcoder 結果報告のブログを見てると、「DP」という言葉がでてくる。どうやら「動的計画法」のことらしい。最初の状態から状態を保存しつつ計算していく感じか。wikipedia:動的計画法が詳しい。

2008-09-23

DIV1 むずい

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

練習で SRM418 DIV1 Level2 の StampsCollection を解いてみた。テストは通るんだけど、System Test が実行時間が長すぎて失敗。手元にテストを持ってきたら、確かに計算が終了しない。

正解者の答えを解析しようとがんばってるが、かなり難易度高い。恐るべし、DIV1。正答率12%、早い人でも40分近くかかってる模様。

→ (追記)SRM 418 - tsubosakaの日記 によると、「次数2以下のグラフの最大重み独立集合」という問題に帰着できるようだ。

2008-09-21

SRM418 DIV2

| 14:07 | SRM418 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM418 DIV2 - TopCoder煮ブログ

2回目。

1193 -> 1388

DIV2 で23位で blue coder へ。次回からは DIV1 だ!

Towers (250pt)

設問意図をつかむのに少し手間取ったが、分かってしまえば素直に書けた。201.48pt

TwoLotteryGames (500pt)

文章が短い。nCm の組み合わせを求めるときに、1 << n を for で回してみた。あとで見たら、他の人も同様の戦略を取っていたようだ。422.16pt

(追記) DIV1 の1問目と同じ。DIV1 の人の回答をいくつか見たが、パスカルの三角形を使って二項係数を求めていた人や、自分と同じ戦略ながら __builtin_popcount を使ってビット数をカウントしてる人もいた。__builtin_popcount は g++ の内部関数の模様。ずるいので、VC++ に移植して手元でビルドが通るようにしておくとよさげ。

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

BarracksEasy (1000pt)

例題を解くための戦略を決めて解くコードは書いて送信。700pt ほどで成功したが、System test で失敗。総当りで調べるべきだった。正答率は 12.26% とかなり低め。

(追記)総当りにしたら成功した。ちなみに、DIV1 の問題は同じ問題の上限が50→5000に増えたバージョン。こうなると総当りは不可。

[Topcoder] SRM 418 DIV 2 - いそっちノート に一発で解く方法が載っているが、実は、この解法では DIV1 の System Test に失敗した。どのタイミングで bar を倒すかを場合分けしなきゃいけないようだ。DIV1 は奥が深い…。

1位の人の回答を見た。驚くほどすっきりしている。すげーなー。

2008-09-12

SRM417 DIV2

| 09:54 | SRM417 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM417 DIV2 - TopCoder煮ブログ

初参加。

0 -> 1193

ReversedSum

逆順にするところでちょっと悩んだが瞬殺。240.19pt。

TemplateMatching

意味がつかめず撃沈。あとで。0pt。

TripleJump

一様分布を2回実施したときの分布の算出に手間取って時間切れ。集計中にやっと解けた。精進が必要。0pt。