Hatena::Grouptopcoder

yaottiの日記

2010-03-03

SRM 463 DIV2続き

| 21:58

hard

何番目までかければよいかを全探索すればできる,境界がややこしい.

複雑に考えすぎずに全て探索すればよかったみたい.

ソース

続きを読む

SRM 153 DIV2

| 22:40

easy

MostProfitable.cpp

score: 243/250 (4mins)

素直な問題.すぐ解けた.

いままでで最速かも

medium

score: 150/500(27mins,何度もsubmit)

問題の読み違え.

If an element of daysAvailable is 0, the corresponding element of sales will also be 0.

で,salesとdaysAvailableを逆と勘違いしていた.ひどいなあ.

もっと気をつけよう…

hard

PickTeam.cpp

解けてない…どうやるのだろう.next_combinationが欲しい.


以下ソース

続きを読む

2010-03-02

SRM 152 DIV2

| 15:32

easy

FixedPointTheorem.cpp

score: 228/250(9 mins)

問題読み違えてた

medium

LeaguePicks.cpp

score: 345->288/500(re-submit, 22 mins)

境界条件(1位の時,一番下のとき)を考慮していなかったため再提出.汚ないソース.

他の人のソース読んだら,pickのループ添字とposition添字を別に扱っていた.うまい.

前のボールが反射する問題もそうだけど,dx(変化量)という軸で考えると綺麗に書けることもあるな.

hard

ProblemWriting.cpp

score: 649->532->383->300 /1000(50mins)

想定してないケースを見付けて対応→既存ロジックが壊れる,というのを繰り返した.ひどい.

バッカスナウア記法見てこりゃ大変そうだと思ったけれど,結局単純なループ構造しかありえないので

見た目よりは簡単にできた.

以下ソース

続きを読む

SRM 462 DIV2

| 19:52

SRMの二時間前からは前回の問題しか開けないようなので,SRM462の問題を解いてみた

easy

Archery.cpp

score: 226/250 (9mins)

難なくとけた.doubleとかintの扱いによわい.


normal

AgeEncoding.cpp

検討がつかなかったので他人のソースを見た.二分探索でやるのか…

解いた(3/5)

ソース

続きを読む

SRM 463 DIV2

| 23:20

初挑戦で緊張しながら待っていたら,登録が必要というのを3分前に知って登録できず,参加できなかった…

くやしいので過去問といた.

easy

score: 238/250(6 mins)

かんたん

medium

score: 406/500(15mins)

時間かけすぎ.なぜかmodせずに引き算してた…3分で書けたのにもったいない

hard

解けてない.システムテストでいくつか通せないのであきらめた.


要素の大きさが2より大きいかどうかがポイント.

a > bにおいて a > 2だとa*b>a+bになる.そうでないならa+b>a*b


以下考えたアルゴリズム.


配列Xnはソート済みとする(Xn:n番目の要素)

Xn<2, Xn+1>2のとき.

nが偶数なら,ありうるのは

(X1+Xn)*(X2+Xn-1)*...*(Xn/2+Xn/2+1)*Xn+1*...

のみ.

nが奇数のときはややこしくて,真ん中の要素をどう扱うか考えないといけない.

実装するもややこしいのでバグ取りきれず.


他人のソース読んだらDPでやってた.たしかに厳密に場合分けするよりそのほうがエンバグしにくそう

以下easy&mediumのソース.hardは明日DPでやる

続きを読む

2010-03-01

SRM 151 DIV2 つづき

| 22:26

hard

MergeSort.cpp

単純にマージソートの実装で,比較回数を調べる問題.

score: 660/1000 (23mins)

off-by-oneミス等でちょっと時間かかったけれど,easy, mediumよりも簡単だった…


ソースは以下

続きを読む

2010-02-28

SRM 151 DIV2

| 22:26

今日は2題だけ.

easy

PrefixCode.cpp

score: 105.84(50mins)

とても時間がかかった.

最初TRIEを作ろうとしてとんちんかんな実装をしていた.

おとなしくソート→逐次比較→元のindexを求める,でいけた.

文字列処理に慣れていないなあ.


はまりポイント

  • substr(0, 10)とsubstr(10)の違い
  • 文字列比較はcompareじゃなくても, == でいい
  • 適当に初期化しない(vectorのサイズとか)
  • ある値がベクタの何番目にあるかを求めるイディオムは?
    • (int)(find(ALL(words), sorted_words[i]) - words.begin())
    • これでいい?
  • いつもsstreamの使い方を忘れる…
stringstream out;
out << num;
string s = out.str();

medium

Birthday.cpp

score: 311/500

日付を月*100+日と変換して比較した.最初float(month+date/100.0)でしてたけど誤差が出て面倒だったのでintに.

  • *(v.end())は確実にまちがい
  • 丸め誤差が出るので,小数を無理に使う必要がない場合は全て整数でやるべき
  • if (hoge) fuga; piyo; とかほんとありえないミスだ

ソース

続きを読む

2010-02-27

SRM 150 DIV2 つづき

| 23:43

hard

BrickByBrick.cpp

何かイベントが始まってSRMのpractice roomに入れなくなったので,1問だけ.

与えられた例ではok,システムテストは未チェック.→通った

自分の書いたソースは明らかに複雑すぎるので他人のソースを読みまくろう…


以下,他人が読んでもわからなさそうだけど重要だと思ったこと

「既に○○をしたか」を知りたい場合,配列で全ての場所でデータを持つ方法と,その「何か」をした回数を数える方法と2つあって,

ケースによってどちらを選択すべきか違うので両方考慮しなければならない.

今回はその選択ミスでかなり時間をかけてしまった.


ソースは続きを読むから

続きを読む