Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-02-17

Codeforces Round #107 (Div. 2) 反省

| 02:59 | Codeforces Round #107 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #107 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #107 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 400/1401

Score: 1366

Solved: oox--

Rating: 1418 -> 1501 (+83)


ギリギリ青キタ――(゚∀゚)――!!

Cを通せなかったのは残念だけど,最近多かったケアレスミスやWA@pretest 1がなかったのは良かった.


151A

入力する値がたくさん出てきてうぜーーと思うも,Noteの通りに実装したら他のSampleでも通ったのでそのまま提出.

何かコーナーケースがあるんじゃないかと少し気になるも,まあAだし・・と思ってしまった.危険である.

https://github.com/k-mats/codeforces/blob/master/150/151A.cpp


151B

入力するデータがたくさん出てきてうry

名前name, タクシーの番号の数t,ピザ屋の番号の数p,女の子の番号の数gを持つFriendクラスなるもの

class Friend {
public:
  string name;
  int t;
  int p;
  int g;
}

を用意しておき,上から順番にインスタンスを作ってはvector<Friend> vfに突っ込む.

と同時にt, p, gの最大値max_t, max_p, max_gを取得しておき,各maxに等しい値を持つFriendのnameを最後に出力していけばOK.


電話帳の登録数が0のときの処理方法が書いていなかったので,何かコーナーケースがあるんじゃないかと気になるも,まあBだしry

https://github.com/k-mats/codeforces/blob/master/150/151B.cpp


C (150A)

6はlosing number,30は6を取ればいいのでwinning number,素数はlosingでもwinningでもない・・ということは,各i < qに対し,losing or winning or primeを順々に判定していけばいいのでは?と考えた.

winning numberとは,因数の中にlosing numberを持っている数.

losing numberとは,winningではない&&素数ではない数.


が,この方法だと各i < qに対し一々素数判定をすることになるために当然TLE

losing numberは上の考え方ではなく,”素因数分解したときに素因数が2つしかない数”とするのが正しい.

すると,qを素因数分解して,残りの素因数が2つになるような値を取ればよくなる.

例)q = 120 = 2*2*2*3*5に対し,残りが2*2になるように値を取る,すなわち2*3*5 = 30を取ればプレイヤー1の勝ち.

https://github.com/k-mats/codeforces/blob/master/150/150A.cpp


D (150B)

Cと同じ1500点だったので,解かれた数を見つつCが無理そうならDに移ろうかと思うも,Dはほとんど解かれていなかったので結局ほとんど見てない.


E

みてない


反省点

  • 場合分けの条件を精査しなかった

教訓

  • TLEになるような場合分けの場合は小細工よりも大元の条件を吟味し直すべし

Codeforces Round #106 (Div. 2) 反省

| 21:02 | Codeforces Round #106 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #106 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #106 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 654/1347

Score: 486

Solved: oxx--

Rating: 1448 -> 1418 (-30)


Bはpretest 1が通らず,Cはsystestで爆死.

意地になってBで時間をかけすぎたのが失敗だった.

以前のWA@pretest 1のこともあったので入念にチェックするのは大切だけど,かと言って1問に時間をかけすぎるのも考えもの,


149A

月毎の値を降順にソートして,値の大きいものから取得.値がkに達すればその時の取得回数を返し,12個全て取得してもkに達しなければ-1を返す.

ただし,k=0のときのみちゃんと0を返すようにすること.

https://github.com/k-mats/codeforces/blob/master/140/149A.cpp


149B

文字列処理の問題.

まずは文字列aが"0N"のように2桁目が0,1桁目がN”以下”の値になってないか,かつ,文字列bが"0Z"のように,2桁目が0,1桁目がZ"以下"の値になってないか(実質的に1桁目の値は無視)調べる.そのような文字列は全基数を取りうるので-1を返して終了する.

例)例えば"11:0Z"はa="11"が二桁の時点で取りうる基数が制限される.なぜなら,aを整数化した時に23以下にならないといけないからである.

また,a="0P"のような場合は,23以下となるために取りうる基数が存在しない.よって,これもこの時点では無視する.

一方,a="0N"のような場合,基数をどのように取っても整数化した値は23以下に収まってしまう.したがって,a, b共にそのような文字列であった場合,取りうる基数は無限に存在してしまうので,-1を返して終了する.


次に,文字1つ1つを整数化する関数を作っておき,まずは取りうる基数の下限を調べる,

例)14:50の場合は5が含まれるので,基数の下限は6でないといけない


次に指定した基数に基づいて文字列を整数化する関数を作っておき,ある基数rでa, bを整数化した値が23もしくは59に収まるかどうかをrをインクリメントしながら調べ,基数の上限を見つける.


以上で発見された取りうる基数を順に表示していけばよい.


・・・のはずが,pretest 1でWA.また初期化ミスか?と思うもそれらしいミスは見つからず・・

終了後改めてsystestに通してみると,手元の環境では

input: 11:20

output: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

となるものが,systestでは

input: 11:20

output: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

となっていた.工エエェェ(´д`)ェェエエ工


どうやら,文字列->整数変換の関数の中で,int c = a^bを計算するのに

int c = (int) pow((double) a, (double) b)

としていたのが原因だったようだ・・

確かにアレなキャストだとは思っていたけど・・誤差を生みかねない処理はするもんじゃないなあ・・

https://github.com/k-mats/codeforces/blob/master/140/149B.cpp


149C

20分でpretestは通ったけれどsystestでfail.

tutorialを見てぐうの音もでないほど納得・・

プレイヤーを実力順に並べ,偶数の位置(0, 2, 4, ...)にいるプレイヤーは1つ目のチームに,奇数の位置(1, 3, 5, ...)にいるプレイヤーは2つ目のチームに振り分ける.これだけで3つの条件は全て満たされる.

実力差が最も上手い人の実力以下になることは幾何的に証明する.

実力の値を軸とする一次元上にプレイヤーを並べ,0番目と1番目,2番目と3番目,4番目と5番目・・といった各人毎の実力差の和=チーム全体の実力差は原点と最も上手い人の位置をつなぐ点線になり,決して最も上手い人の実力を超えることはない.

https://github.com/k-mats/codeforces/blob/master/140/149C.cpp


149D

みてない


149E

みてない


反省点

  • 1問に時間をかけすぎた
  • doubleを挟むキャストをしてしまった

教訓

  • 1問に1時間以上使わない
  • doubleを挟むキャストは誤差の温床.整数だけでできる処理は極力整数だけで行う

2012-02-09

Topcoder SRM532 Div2 反省

| 03:58 | Topcoder SRM532 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Topcoder SRM532 Div2 反省 - iwbtr - kmats Topcoder SRM532 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 554/1361

Points: 234.58

Solved: ox-

Rating: 930 -> 914 (-16)


registerした後仮眠を取って起きたら0:59.250を理解するのに時間がかかった..

systestでは600点問題大虐殺.ただのgreedyで解くとx.xの場合に引っかかることに終盤気付くも950が気になってそっちを優先してしまったorz


532 Div2 250

Mr. Dengklekが数えそこねたアヒルの数の最小値を求める問題.

アヒルに付いた数字の最大値をmax_num, 最小値をmin_numとして,

return (max_num - min_num + 1 + 1 - ducks.size());

するだけ.


532 Div2 600

できるだけ綺麗な鎖の列を作る問題.

鎖を場合分けすると,

  1. "xyz"のように錆のない鎖
  2. "x.."や"xy.", "..z", ".yz"のように片端が錆びている鎖
  3. "x.z"のように中央が錆びている鎖
  4. ".y."のように両端が錆びている鎖

の4通りになる.1番目は何も考えず連結に使えるので,int sumに値を保持しておく.

2番目はそれぞれ左端もしくは右端にしか使えず,3番目は左端・右端両方に使える.

そこで,2番目もしくは3番目に属する鎖は別途vectorなどに保存しておき,そこから"最も値が大きくなる左端・右端の組み合わせ"を探す.

ただし,"x.z"型の鎖はそれ一つで両端に使うことはできないので,そのことに注意する必要がある.

4番目は連結不可なので,4番目に属する鎖の内最も値が大きいものと,1〜3番目を連結した鎖の値を比べる必要がある.


引っかかるポイントはおそらく2つ.

  1. 4番目の鎖の処理を最後に行うのを忘れる
  2. 3番目の鎖の処理を間違う

この内1つ目はExamplesの中にあるので,大抵の人が気付くはず.

2つ目は,初めにint left, rightという左端・右端用の変数を用意しておき,chainsを順に見てその場で大小比較することにより左端候補・右端候補を決めてしまうgreedyな方法を思いついてしまうとハマる.

この方法の場合3番目の鎖の処理で迷うが,それっぽい条件でleftもしくはrightと比較する処理を書くとExamplesは通ってしまう.自分がこれだったorz


例)"..3", "2..", "5.4", "6..", "111"

正解は"5.41116..."で13になる.

しかし,greedyな方法の場合,"5.4"を見たときにこの鎖を右端候補としてしまう可能性がある.

(まだ"6.."を見ていないので,左端候補で間違いないといえるような処理は書けないはず.)

よって,"..31115.4"で12・・というような誤答を返す可能性がある.


コードを書いている途中も"greedyだと無理じゃないかなあ"と思いつつもExamplesが通ってしまったので"まあいいや"と思ってしまった・・

950を解いている途中で無理だということに気付くも時すでに遅し・・Easyはともかく,Mediumは回答の妥当性をちゃんと確かめないと駄目だと痛感..


532 Div2 950

愚直に全探索するとオーダーが大きすぎてしまう問題.

dpでなんとかするのかな.

なんかdpが必要そうな問題は毎回ほとんど手を付けずに終わってる気がする・・


反省点

  • 起きたら開始直前だった
  • 回答の妥当性を確かめずに提出してしまった

教訓

  • 仮眠しなくてもいいように前日・当日の睡眠を調整する
  • 回答の妥当性をちゃんと確かめる,もしくは気になったケースは手でちゃんと確かめてからsubmitする

2012-02-02

Codeforces Round #105 (Div. 2) 反省

| 05:16 | Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 427/1320

Score: 1628

Solved: 2 (A: 980, 00:05 / C: 748, 01:28)

Rating: 1350 -> 1448 (+98)


出題者による問題点の不適当な設定を避けるために5問すべてが1000点になったRound.

148A

お姫様がd匹のドラゴンをなぎ倒していく,

姫は4つの攻撃手段を持っており,各攻撃手段では”各”第k, l, m, n番目のドラゴンを倒すことができる.

全部で何匹のドラゴンを倒すことができるか?という問題.


問題文だけ読むと(゚Д゚)ハァ?な問題だが,sampleを見れば一目瞭然.

i番目のドラゴンに対し,iがk, l, m, nのいずれかで割り切れる = そのドラゴンは倒せる,ということ.

https://github.com/k-mats/codeforces/blob/master/140/148A.cpp


148B

お姫様がドラゴンの巣から城へ逃げ帰る.城までの距離はc.

姫が逃げてからt時間後,ドラゴンは脱走に気づき追いかけ始める.

姫(速度vp)がドラゴン(速度vd)に追いつかれた場合,宝玉をその場に捨てる.

するとドラゴンは宝玉を一旦持ち帰り時間fをかけて宝玉を整頓し,その後追跡を再開する.

このとき,上手く逃げ帰るのに必要な宝玉の数はいくつか?という問題.


姫の位置をxp, ドラゴンの位置をxd, 追いつくまでにかかる時間をdtとおき,dt時間後に追いつく

-> 宝玉の数++

-> ドラゴンが帰って整頓するまでの時間分xpを進める

-> xd = 0にする・・

というのを,xp >= cになるまで続ければOK.


・・が,systestで撃沈.よくよく考えればvp > vdの場合(もちろん宝玉は0個)を忘れていたorz

https://github.com/k-mats/codeforces/blob/master/140/148B.cpp


148C

お姫様が花婿を探している.姫は複数の候補者と順番に謁見するが,その比較基準はお金.

ある候補者がそれまでの候補者よりもお金持ちなら,姫は"Oh..."と言う.

ある候補者がそれまでの候補者全員のお金の和よりもお金を持っていたら,姫は"Wow!"と言う.

1人目の候補者に対しては何も言わない.

候補者の数をn人,Oh...と言った数をa, Wow!と言った数をbとした場合,あり得る候補者の列を答えよ(候補者iは整数,すなわち所持金tiで表す),という問題.あり得る列がない場合は-1を出力.


初めにWow!と言い切らせ,次にOh...と言い切らせる作戦.

お金は1から50000までなので,候補者1人目はt1 = 1とする.

その後,bの数だけti = sum + 1を繰り返す.(sumはi-1までの和)

その後,aの数だけti = t(i-1) + 1を繰り返す.

最後に,残りの候補者はすべて1にする.

例)10 2 3

1 2 4 8 9 10 1 1 1 1


ただし,n - a = 1の場合は-1になる.なぜなら,a = n - 1の場合,2人目以降の全候補者に対しOh...と言わせないといけないのだが,1人目がどのような数であろうと,2人目に対しては何も言わない or Wow!しか言えないので.

例)t1 = 1 に対し,t2 = 1なら何も言わないし,t2 = 2ならWow!と言ってしまう.


途中で使ったbool flagの初期化を忘れてかなりタイムロス.

ずーーーーーっとpretest 1が通らず,もうだめだあああと思っていたらオチがこれだとは・・

手元の環境では上手く動いてしまったのが運の尽き.

https://github.com/k-mats/codeforces/blob/master/140/148C.cpp


148D

姫とドラゴンによるネズミを使ったゲーム.

姫が勝つ確率を求めよ,ということなので,数学の問題だなあ,と思いつつ試行錯誤していたところでタイムアップ.

ちょっとしたことに気をつければ,なんてことはない問題・・な気がする.

白ネズミwと黒ネズミb,およびそこから求められる確率をdpで保存していくと上手くいく?


148E

みてない


反省点

  • 初期化忘れに気付かずタイムロス

教訓

  • 初期化を忘れるべからず
  • 何をやってもpretest 1で通らなかったら問題文の読み間違いやコードのケアレスミスを考慮する

2012-01-21

Topcoder SRM530 div2 反省

| 01:23 | Topcoder SRM530 div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Topcoder SRM530 div2 反省 - iwbtr - kmats Topcoder SRM530 div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 238/911

Points: 234.58

Solved: 1 (250, 00:07)

Rating: 875 -> 929 (+54)

1000をChallengeで落とされ,500をSystestで落とされ意気消沈していたら何故かRatingが上がったでござるの巻.

順位を確認したら謎の238位.1200~1300人くらい参加してるときなら350位くらいか?

Editorialを見ると1000をPassしたのは一人もいないとか・・どういうことなの

緑になれたのはまあ良かったけれど,せめて500は通してもう少し上に行きたかった.


530 Div2 250

ボールが入ったN個の瓶をボールの数順にソートする.ただし瓶の位置は替えず,中のボールを移動させることで行う.このとき移動させるボールの数の最小値を返す問題.

移動前および移動後の瓶内のボールの数の差を取って全瓶の和を取り,1/2すればいいだけ.


530 Div2 500

2次元平面上に置かれた長方形のケーキから型(cutter)を使ってケーキを切り取る.与えられるのは切り取られた後のケーキと型.この2つから,ケーキは型のみを使って切り取られたか否か?という問題.

ケーキを左上から走査し,"."が現れたらそこを左上端としたケーキの一部分と型を比較.切り取られた部分が型に一致したら,その部分に適当な文字("o"など)を入れて次に進む.

全て走査し終わった後にまだ"."が残っているようだと型では切り取れない部分があるということになるので,NOを返す.それ以外ならYES.

・・という方法で解いたところSystestでfailed.走査開始条件を"."にすると,型の左上端が"X"の時に上手くいかない場合があるようだ..


530 Div2 1000

お!霊夢ゥー!

行(row)をステージ数,列(column)を次移行のステージへ進めるか否かの真偽値とするvector<string>が与えられ,スタートからクリアまで何通りの道があるか?という問題.

スタート地点からゴール地点までつながっているパスがいくつあるか,なので,つながっているノード間のパスのみを記憶してたどっていき,ゴールに辿りつけたら答えを+1(でいいはず・・).

が,それを深さ優先探索で書いてしまった.submit後にTLEが気になって20x20のinputを入れてみると0.11秒,これは無理だろうなあと思いつつも直す時間がなく,Challengeでは50x50を突っ込まれ予想通り陥落.

他の人のコードを見ると,スタート地点からあるノードmにたどり着くまでのパスの数を配列a[m]に格納しておき,ノードmからノードnへのパスがあれば,a[n] += a[m]とする・・という手法の人が割といて,なるほどと思った.が,全員落とされていた.はて?

まだちゃんとEditorialを読んでないので,後で復習したい.

というかあのflashは・・


反省点

・深さ優先探索でTLE

・余計な条件の付与で爆死

教訓

・再帰が深くなりそうな場合は幅優先探索で解く

・計算量を落とそうと追加した条件は余計な枝刈りをしていないか確認する

laycrslaycrs2012/01/22 09:30Div2 1000は何通りのパスがあるかという問題ではないですよ.
繰り返しゲームをやるけど,今まで使ったことのない枝を少なくても1個は使わないといけない,という条件で,最大で何回ゲームをやることが出来るか,です.

kmatskmats2012/02/03 03:40Editorialを読んでみたら仰る通りでした.
アルゴリズム以前に読解力不足でした..

2012-01-18

Codeforces Round #103 (Div. 2) 反省

| 05:18 | Codeforces Round #103 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #103 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #103 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 1129/1365

Score: 430

Solved: 2 (A: 480, 00:10)

Hack: -1

Rating: 1418 -> 1350 (-68)


なんというか色々と散々な回.

144A

配列から最大値かつ出来るだけ左にある要素と,最小値かつ出来るだけ右にある要素を探し出し,それらをスワップで移動するのにかかるコストを計算.最大要素と最小要素が入れ替わる際にスワップ1回分得するのを忘れなければいいだけ.


144B

はじめに与えられるテーブルの対角線上の2頂点がどの組み合わせか分からないので,何が来たとしても(xa, xb)は左下,(xb, yb)は右上(即ちxa < xb and ya < yb)になるように頂点の値をスワップしておく.

その後vector< pair<int, int> >にテーブル上の頂点を全て格納し,各頂点毎と各ストーブの距離がストーブの範囲内か調べる.範囲内だとわかった時点で答えを+1してbreak.

・・とすればいいはずなのに,pretest 7で落ちる.距離とストーブの半径の比較の際にdoubleの誤差が問題なのかと,色々試してみるが落ちる.どこかの変数でintを使うとオーバーフローするのかと,全てlong longにしてみるが落ちる.何故だし.

で,よくよくコードを読み返してみれば,(xa, xb)と(ya, yb)のスワップの部分でケアレスミス・・orz

今にして思えば,距離distと半径rの比較の際は,dist^2とr^2で行えばわざわざdoubleにキャストして,誤差を考えて・・という必要はなかった.これも反省.


144C

2つの文字列s, pが与えられ,pのアナグラムはsのsub stringの中にいくつ含まれるか?という問題.前者の中には'?'が含まれており,どのアルファベットに置き換えてもよい.

見るべきはpのアナグラムなので,p中の文字の順番は関係ない.なので,pに各文字がいくつ含まれるかをa[26]に保存しておく.あとは,sの先頭から,pの長さと同じ分だけ切り出しては文字数を数えてaa[26]に保存し,はじめに保存したa[26]の値を上回らなければ答えを+1.

これを愚直に2重ループで実装したところTLE

過去に出たsub stringは再調査しなくてもいいように,sub stringをキー,結果を値としてmap<string, int>を使ってDPしてみてもTLE

test結果を見ると,ひたすら??????????????????が続く入力の時にやられていたので,sub stringが全て?で構成されているときは特別に別途処理するようにしてもTLE.なん・・だと・・?

どうやら考え方が根本的に間違っているようなので,後日改めてチャレンジ.

条件にs.size() < p.size()もあり得ると書いてあったので,それを考慮していないように見えるコードをHackしてみたら返り討ちにされた・・

Cを解き始めた時,a[26]の初期化ミスのおかげで,a, b, c以外の文字が含まれていると正常動作しないバグがあった.が,例示されたテストケースではa, b, cしか用いていなかったので気付かなかった.これをsubmitするとpretest1でWA.この時点で,pretest1~は例示されたケースと同じと思い込んでおり,手元では正しいのに何故pretestは通らんのだ?バグ??としばし混乱した.pretest1~と例示されたケースは一致するとは限らない・・と考えていいんだよね?

144D

みてない.

144E

みてない.


反省点

  • ケアレスミスに気付かなかった
  • a^1/2とbの比較を直接行おうとした
  • pretest1~と例示されたケースは同じだと思い込んでいた

教訓

  • ケアレスミスこそ最大の敵.問題文だけでなく,コードを一からくまなく追いかける
  • a^1/2とbの比較は2乗してaとb^2で行う
  • pretest1~と例示されたケースは一致するとは限らない