0xDEADBEAF

念願の消音スネアをついに買ったのです。やったっっ++。 スネアってこんなに跳ね返るもんだったっけなぁなんて言いながら、ぺしぺしと叩いて悦に入ってます。

TopCoder::SRM::351 に取り組んでいました。先週は参加できなかったので、2週間ぶりです。

いつもどおり、250点問題を無難にこなしたあと、500点問題へ。 なんとかの一つ覚えみたいに、幅優先探索で挑んでみたのですが、どうしてもできない。 なんでかなぁといろいろ試してみたところ、STLの使い方に問題があったのでした。

やりたいこと

struct Combi {
  int g, s, b;

  Combi(int gg, int ss, int bb) : g(gg), s(ss), b(bb) {}
};

みたいな構造体を、コンテナに入れたい。

トラブル : std::set に insert できない、std::map で find できない

operator <がないよ、とコンパイラに諭されてしまいます。

ならばと、3つのメンバg, s, b について

bool operator <(const Combi &rhs) const {
  return g < rhs.g || s < rhs.s || b < rhs.b;
}

みたいなoperatorを書いてみたところ、コンパイルは通るのですが、insert/find ともに結果が妙なことになってしまいます。どうも、operator <のせいで、異なる値を持つ2つのオブジェクトが同一視されてしまうようなのです。

異なる値をもつオブジェクトをsetにinsertしようとしても、同じオブジェクトと見なされてinsertできない、あるいは要素xがないはずのmapにfind(x)をかけても見つかってしまうという。

---

うーん、とそんなところで悩んでいろいろしているうちに時間切れに… どんなよい刀でも、手に馴染んでいなければ自分を切ってしまうということですね。

しかし、なぜ同一視されてしまうのだろう…

無事我が家に帰還しました。 横浜中華街遠い。想像していたよりも遠い。8段の飛び箱くらい。

なんか、ひとってそう簡単には変わらないものなんだなぁとしみじみとしたりほっとしたりしました。

眠い目をこすりながらの参戦です。 この一週間、TopCoderのTutorialを読んだり過去問を解いたりして勉強してきたものが、果たしてどう出るか。

Coding Phase

250点問題

単純な文字列処理の問題みたい。解き方さえ問題文に書かれてあり、ただ忠実にコードにするだけ、みたいな問題。 5分でsubmit。236.74ptsでした。

500点問題

幾何の問題。これまた簡単だなぁと思いつつ、最初単純なミスをしていてローカルテストすら通らず首をひねったりして時間をロス。 その後40分でsubmit。339.18ptsでした。

1000点問題

残り時間で1000点問題を考えていました。 最近取り組んでいた、幅優先探索で解けないかなぁと、あれやこれやコードをいじくりまわしているうちにCoding Phaseが終了、となりました。

Challenge Phase

最近の適当Challengeで痛い目にあっている反省から、Challenge Phaseで自分からしかけることはなしにしてしばらく放置。

…としていると、500点問題にChallengeされて陥落してしまいました。境界条件が甘かった…

---

というか、Room全体でChallengeがかなりアグレッシブに行われて、数々の500点問題解答がSuccessfully Challengedになっていておもしろかった。

これが…

こうなったという。

簡単そうな問題ほど、落とし穴があるのだという教訓になりました。やれやれ。

結果

室内6位というしょんぼりな結果に。500点問題でもっと注意深くやってればなぁあ、と。

しかし、Ratingは 777 → 912 となり、無色 → 緑色 になったので、ちょっとだけうれしいな。250点問題をきちんと解くことができれば、緑色になれる、ということのようですね。

ちょっとプールで600m泳いだ次の日にギターの練習を1.5時間、ドラムの練習を15分ほどやったくらいでもものすごく眠くなってふとうたた寝してしまった自分はなんて体力がないんだろうと思った。

なんてひとりごとこそ、twitterに書いたらいいじゃない、とか書いてから思った。twitterはいまひとつ何がおもしろいのか分かんないんだよなー。

数年ぶりにコードをおさえたりしてると、左手の指の腹がかわいそうなくらいに痛くなるのも、かわいらしいものだとか思った。なんか思ってばっかだなとか思った。

TopCoder::SRM::348::500::LostParentheses で提出したコードがChallengeされて撃沈した件を調べていました。

原因

std::stringのコンストラクタの仕様を間違って捉えていた。

詳細

数字と+,-から成る文字列が与えられたときに、-でsplitするコードをどう書くか。 string::findを使って、順に部分文字列を取得しようと思いました。

ダメなコード

 1 #include 
 2 #include 
 3 using namespace std;
 4 
 5 void split(const string &str) {
 6    string::size_type left(0);
 7    string::size_type right(str.find('-'));
 8 
 9    while (string::npos != right) {
10       cout << string(str, left, right) << endl; // XXX : まちがい
11 
12       left = right + 1;
13       right = str.find('-', left);
14    }
15 
16    cout << string(str, left, right) << endl;
17 }
18 
19 int main() {
20    const char *strs[] = {
21       "55-50+40",
22       "00009-00009+0009-09+09-09+09-09"
23    };
24 
25    for (int i=0; i<2; i++) {
26       cout << "str : " << strs[i] << endl;
27       split(strs[i]);
28       cout << endl;
29    }
30 
31    return 0;
32 }

ところが、これでは2つめのケースがおかしくなります。

実行結果

% ./strfind
str : 55-50+40
55
50+40

str : 00009-00009+0009-09+09-09+09-09
00009
00009+0009-09+09 <<<<
09+09-09+09-09
09+09-09
09

‘<<<<’の行が、ちゃんとsplitできていないことが分かります。

理由

標準C++ライブラリ string> によると、std::stringのコンストラクタで(別の文字列, 数値1、数値2) を渡すと別の文字列の数値1の位置から数値2の長さぶんだけコピーした文字列がつくられるとあります。ここを、別の文字列の数値1の位置から数値2の位置までの部分文字列をコピーした文字列がつくられると勘違いしていたのがまちがいのもとでした。

修正

問題の10行目を、

 cout << string(str, left, right-left) << endl; // XXX : OK

とするだけでOKでした。

所感

考えたアルゴリズム自体は、遠回りだけれど間違っていないものだっただけに、文字列処理のところでミスるなんていうのは痛いところです。もったいない。 C++の標準ライブラリのリファレンスがやっぱり手元に欲しいなとか思いました。 Mac OSXだとmanで引けないんだよなぁ。Ubuntu 7.04だとあるんだけれど。

静かで暗い、こんな夜が好きだ。

外の強い風をぼんやり見たり天井と壁のさかいめあたりを見つめていると、いろんなものが見えるような気がしてくる。 けっきょく、ひとが生き続けていくのに必要なものなんて、いくつかの幸せな思い出だけなんじゃないのかな。 べつにそのときに戻りたい、なんていうふうには思わない。そういう類のものなんじゃなくて、寒い寒い冬の日に、ようやく帰り着いた家のドアを開けたときに感じる暖かさみたいなもの。 牛みたいになんども反芻すれば、そのたびに沁み込むものがある。

なんていうのは、マッチ売りの少女の話に似ているのかもな、とか思った。

Ratingが下降中なのにもめげずにSRM348にチャレンジしてみました。

さいしょ、ぜんぜんRoomにenterすることができず、chat roomでみなが「おいおい、どうなってんだ」みたいなことをざわざわとしゃべっていたのが面白かったのです。

250::OptimalList

文字列の処理および簡単なロジック、ソートなんかの問題。12分ほどで書いてsubmit。213.30pts.

500::LostParentheses

([0-9],+,-)から成る文字列を与えられて、その文字列を計算式として評価したとき、最小になるようなカッコの入れ方を考えましょうという問題。

どうすんのかなぁと30分くらいうんうんと唸って、「-で囲まれた部分は足すしかないからまとめて足す。そんで、まとまった数字を前から引いていけばいいのでは」と思いつきました。

1. ‘-’で文字列をsplit
2. 各部分文字列に対して、’+'でsplit -> 数字のリスト -> 足し合わせる
3. 2でできた部分合計のリストを、前から順に引く

みたいな。さっそくコードを書いて、ローカルでテストしたところちゃんとパスしたのでsubmit。200ptsくらい。

1000::IncreasingSubsequences

部分問題を解いて全体問題の解をつくる、といういかにも1000点問題なもの。 BFSとかDPとかで解くんだろうなぁと思いつつも、それらの手法にまだ習熟していないのでベタに書き、けっきょくテストをとおすことができないまま時間切れ。

ChallengePhase

500点問題に対してChallengeされ、敢えなく撃沈してしまいました。

うぇーんと泣きながら他の人の怪しそうなコードに対してChallengeしてみたところ、またもや失敗。自分のスコアを落とすだけの結果になってしまいました。

結果

188.30pts

Ratingもまた落ちてしまい、800を切って700台に突入です。やれやれ。

その他

数学ハッカーな先輩に500点問題をどうやって解くか聞いてみたところ、

最初の’-'以降の数字は全て符号をどちらにでもすることができるから、ぜんぶ足してしまって、’-'より前のものから引けばいいだけやん

と1.5分ほどで答えられてしまいました。うーん、たしかに…

いろんなことがどうでもよくなるけど、それでも素敵なことがたくさん周りにあふれていることのしあわせを噛み締めたりする。

いまこうして息をして、ぼんやりした頭をかかえながらキーボードを打てていることの貴重さを、明日の目覚めたときにも覚えていたいと思う。いろんなことをきっと忘れてしまうのだけれど、だいじなものが胸の底にしんしんとつもっていたらうれしい。

みんながゆきばのない想いを胸の奥にしまいこんで、たとえば満員電車に揺られながら毎日を過ごしているのだとしたら、それはなんていう奇跡なんだろうと思う。外に出されることのない、膨大な想いというものの重さが放たれて、夜の静けさがさらに深まればいいな。

9日間ありました。 アクティブに動いたり、親交を深めたり、内省したりとなかなか充実したものだったようです。