Hatena::Grouptopcoder

TopCoder煮ブログ

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

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/