Hatena::Grouptopcoder

TopCoder煮ブログ

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

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位の人の回答を見た。驚くほどすっきりしている。すげーなー。