Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2009年05月16日(土) ACM-ICPC Japan Domestic Warm Up I

[]ACM-ICPC Japan Domestic Warm Up I ACM-ICPC Japan Domestic Warm Up Iを含むブックマーク ACM-ICPC Japan Domestic Warm Up Iのブックマークコメント

http://rose.u-aizu.ac.jp/onlinejudge/jdwu1.html

http://rose.u-aizu.ac.jp/onlinejudge/ContestRankList.jsp?contestID=JDWU2009I

ICPC参加資格も何もないですけど、

リハビリのために参加しました。

最近老化がひどいので…。

A

二つの列を一緒に読み込んで、0加えて、ソートして、前からスキャン

が一番速そうだったので、そう実装。

B

3次元配列をつくって、適当に塗っていく実装。

C

シンプルなparser。

10分でかけるparserとかいう記事を公開しながら

20分かかったのは、多分老化のせい。

D

20個しか科目がないので、2^20とおりビットパターン生成して

条件満たしてるかチェックで書いたのだけど、

1秒の制限時間を5秒ぐらいかかっている。

ちょいちょい変えながら再送するが、

ちっとも速くならない。

TLE厳しすぎる…。

問題チェンジ

F

Eが図形でFが探索なのを見て、

どっちかというとFかなと思う。

起点からのばして探索する方針で適当に書いて

サブミットしたが、全然間に合わない。

これもTLEを量産した揚句、いったん中断。

D

Dに戻る。

枝刈りが入らないのがいけないんじゃないかなあ、というので、

DFSで書き直し。

普通にとおる。うーむ…。

F

こっちも枝刈りを入れることにする。

正のマスについて、

負のマスにつなぐことができないのがあれば、だめ。

負のマスについて、隣接する正のマスの合計が超えてなければだめ。

この二つを入れたら、0.01秒とかで通った。

探索は博打みたいなところがあるなあ…。

E

のこり25分ぐらいだったけど、一応書いた。

座標と向きをノードとしてダイクストラみたいなので、

一応書き終わってサブミットしたが、

バグバグだった模様。

トラックバック - http://d.hatena.ne.jp/tanakh/20090516