週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

前回があまりにもひどかったので、まじめに復習して次回に備えることにしました。

しかし75分で解けたのは250点と500点だけ。両方ともSystem Testは通りました。1000点は時間内にテストケースを通すことができませんでした。まだSystem Testを通すプログラムができていません。

250点は瞬殺で242.16点。500点は解けたはずなのにはまりました。メモ化して探索するのですが、

int search_impl(args) {
  if (outOfDomain())
    return 0;
  // snip;
}
int search(args) {
  int& memo = table[args];
  if (memo<0)
    memo = search_impl(args);
  return memo;
}
と書いて、tableが配列で、argsにoutOfDomainとなる負の値を入れて領域外アクセスをしてしまいました。テストケースが通らないので気付きましたが。

1000点は本番ではスルーした最大流問題です。解きかたは上位の解答を見て把握したものの、最大流なんてしばらく書いていないので酷いことになりました。 そもそもICPC現役のときも最大流はChunにまかせていたような気もしますが。 いまだに計算時間が遅く、もっとも大きいテストケースでこけます。

追記:計算量の問題ではありませんでした。よく調べたらdfsがバグって無限ループしていました。

ところで、Practice roomの1000点解答があまりに酷いので撃墜しておきました > shinhさん

スポンサーサイト

仕事を切りあげて18時から参加したら爆死。-50点ですよ-50点。250と500とをSystem Test failedしたうえにChallengeを二回失敗しました。

250点はO(N^3), N=1000で計算がまにあうんですね。目測を誤って難しいプログラムを書いてしまいました。時間がかかりまくった上に、最終的には、a,b,c自体は1000を超えることに気付いていませんでした。さらにO(N^3)でまにあうことに気づいていなかったのでO(N^3)にChallengeしてペナルティーをもらうというありさま。

500点は探索関数をMemo化すればよいことに気づきませんでした。ほかの方法で枝刈りをしまくって時間短縮させたところ、結果的に(おそらく)枝刈りを間違えて失敗しました。


4月27日追記: 500点はTLEでした。オーダーの壁がありました。復習

なんとか中毒になるのは明らかに疲れているからではないかということに気付きました。

会社から帰ってから「英語の勉強として」FuturamaとSouth Parkを見ているのがまずそうです。あるいみずっと仕事中。生活改善のためにテレビはつけておくだけにしておきました。あと英語の勉強はおやすみ。

とくにやることがたくさんあったわけではないけど、油断したら急性れぅ中毒になって週末の1/4くらいをつぶしてしまいました。くやしいです。

ちなみに一番感心したのはこれ。http://www.nicovideo.jp/watch/sm1499570

MegaTokyoは#13までしか読んでいません。さらにずっとPiroを女性だと思ってました。

250点問題のみ + 1 challenge failure:(

500点は p(n, r) = 1^r + 2^r + ... + n ^r (mod 1000000007)を求めるだけ。Bernolli Polynomialsは初めて聞きました。 しかし、冷静に考えると地道に公式を導出する方法が書けた気がします。p(n, r)をnのr+1次の多項式として、その係数を求めます。p(n, r') (r'<r)さえ求まっていればあとは適当にやれば解けます。係数が分数になるところは、modの逆数を掛けるのが正解です。本番では係数をどう保存していいのかわからなかったのでこの方法はとれませんでした。

週末はtopcoderやったあとずっと世界樹してました。よく進みました。肩とか痛いです。

進行状況は三月終わりに第一層突破。先週は第2層8階まで。そしていま2層突破して3層に軽く入ったところです。 パーティーはブソダドガ。でも探索の時は前列の誰かを外し、ドクターを前列に、そしてレンジャーを入れています。 レンジャーはアイテム採取隊として作ったものに忍び足を覚えさせて使っています。攻撃力も適当にあるし、採取ポイントで取れるものを調べるために再度レンジャーを派遣する必要がなくて便利です。

  • ブシドーは上段ツバメ一本。
  • ソはカウンター、トルネード、チェイス*。剣一本だと技はトルネード以外選択肢なくないですか?
  • ダークハンターは毒殺とジエンド。
  • ドクターは回復。といってもキュアとエリアヒールくらい。最近まで前列職だということに気づきませんでした。
  • ガンナーは跳弾マスターしてから三色と全体攻撃。

ガンナーのつぶしの効き具合が異常です。遅いのが難点ですが。三色と全体攻撃ができるので倒せない敵編成があまりいません。

shinhさんのコードに便乗して実験します。dequeとreserveしたvectorを追加。

#include <iostream>
#include <iomanip>
#include <ctime>
#include <vector>
#include <list>
#include <deque>
using namespace std;
const int REPEAT=10000000;
template<typename C>
void pushbacker(C& c) {
  clock_t cl = clock();
  for (int i = 0; i < REPEAT; i++) {
    c.push_back(i);
  }
  cout << (((double)clock() - cl) / CLOCKS_PER_SEC) << endl;
}
int main(void) {
  cout.setf(ios::fixed);
  cout << setprecision(3);
  vector<int> v;
  pushbacker(v);
  list<int> l;
  pushbacker(l);
  deque<int> d;
  pushbacker(d);
  vector<int> v2;
  v2.reserve(REPEAT);
  pushbacker(v2);
  cout << CLOCKS_PER_SEC << endl;
  return 0;
}

実行してみます。

$ g++ --version
i686-apple-darwin8-g++-4.0.1 (GCC) 4.0.1 (Apple Computer, Inc. build 5367)
Copyright (C) 2005 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ g++ -O2 -o pushabck -Wall -W pushback.cc
$ ./pushabck
0.270
1.490
0.130
0.120
100
$

dequeは速いですね。速いのでstackのデフォルトになっていると認識しています。 一方listが何故かさらに遅くなりました。どうしてこんなに遅いのでしょう。

今年のACM ICPC WFがおわったようです。 公式, 結果, 問題

選手のみなさんはお疲れさまでした。あとまたロシアですね。ロシアMITロシアStanford。Stanfordって強かったでしたっけ? それから中国がちょっと後退したのでしょうか?

とりあえず問題を読みます。

topcoder marathon match 32に参加してみたのですが一点もとれませんでした。そもそも時間内に終わらないとか酷すぎる状態でした。土日だけでなんとかしようとしたのが失敗だったかもしれません。

問題は普通のOR。材料がn種、製品がm種類あって、製品はこの材料からできるというレシピがわたされます。そのあと一日毎に、「この製品いくつを何日までに作るといくら払います」という契約がたくさんくるので、それを締結したり拒否したりして稼ぎます。製品が製品に依存していて、製品をつくるだけで一苦労でした。

さすがに出張中に参加するのは問題だった。

なんか妙なバグがあると思ったらintのつもりの変数をboolにしていました。

bool t = true;
bool f = false;
for (int i = -1; i < 2; ++i) {
  cout << t + i << ' ' << f + i << endl;
}
出力>>
0 -1
1 0
2 1
これはboolからintへの暗黙の変換でしょうか。でも次のとか
bool b = false;
for (int i = 0; i < 300; ++i) {
  cout << b;
  ++b;
}
cout << endl;
出力>> 011111111111111111(snip)
これとか
bool b = false;
for (int i = 0; i < 300; ++i) {
  cout << b;
  b -= 1;
}
cout << endl;
出力>> 010101010101(snip)
どういう意味があるのかわかりません。ちなみに最後のコードは b--がコンパイルエラーになったので b -= 1;になっています。どっちも却下してほしい。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。