Hatena::Grouptopcoder

TopCoder煮ブログ

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

2008-10-28

比較関数

| 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

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 が少ない → はまりポイントがある

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-19

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() と同じ扱い。

2008-10-12DIV1 Easy 集中特訓

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

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);

と同じ。

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-03

日本人上位coder

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

はてな界隈で SRM キーワードで探してきた中から、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 で帰ってくるので要注意。