Hatena::Grouptopcoder

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

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~と例示されたケースは一致するとは限らない

2012-01-16

Topcoder SRM529 Div2 反省

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

Div. Place: 215

Points: 535.17

Solved: 2 (250, 00:07 / 500, 00:27)

Rating: 745 -> 875 (+130)

割と良かったけれど緑に届かず.

HardでN == 0 || N == 1を考慮していない人が割といたのにChallengeで先を越されてしまったのが残念.


529 Div2 250

チェスの駒(ポーン)が1次元の配列a上(size <= 20)に並んでおり,駒は配列の先頭(a[0])を目指して以下の条件で移動する.

  • 1度に移動できるのは1マスだけ
  • 2つペアの時のみ移動できる
  • 移動すると,駒は1つにまとめられる

この時,できるだけa[0]に駒を集めた時のa[0]の値を答えよ.というもの.

配列int a[n]の末尾から駒の数a[i]を見て,a[i-1] += a[i] / 2を繰り返せばいいだけ.


529 Div2 500

歴代の王の名前を辞書順にソートする.ただし,王の名前の末尾にはスペース1つの後にローマ数字が書いてあり,同じ名前の王の場合は数字が小さい方を優先する.

王の名前自体はvector< string >に格納されているので,普通にソート.

各要素(王の名前)の比較時には,名前部分string aとローマ数字部分string bに分ける.

まずはa同士で比較して,違う名前ならその結果を返す.

同じ名前なら,今度はb同士を比較.

ローマ数字は1~10がI, II, III, IV, V, VI, VII, VIII, IX, X, 20, 30, 40, 50がXX, XXX, XL, Lとなっている.

これらを文字数で区別すると,

  • 4: VIII
  • 3: III, VII, XXX
  • 2: II, IV, VI, IX, XX, XL
  • 1: I, V, X, L

となる.後は文字数が大きい方から優先してローマ数字列bを先頭から比較していけば,bの値が求められる.

後は,求めた値同士を比較してその結果を返す.

文字数を小さい方から比較していくと,"IV"を4ではなく"I"+"V"の6としてしまうなど,正しい結果が得られない.

以上の方法だとローマ数字の変換部分の記述が面倒だが,愚直な処理なので分かりやすい.

Div1 Easyと同じ問題で,特にDiv1の方ではもっとスマートな方法で解いた人が多いようだけど・・


529 Div2 1000

人工知能界の大物マービン・ミンスキーさん登場.

問題自体は,与えられたアルゴリズムと同等な,かつ計算量の小さいプログラムを書け,というもの.

とりあえず問題文に載ったアルゴリズムを写経し,その後色々考えるも時間切れ・・

submitした人自体60人もいなかったらしく,割と難しい方だったのかも.

更に,submitした人の多くが,N == 0 || N == 1の場合はreturn -1するのを忘れており,ここで大量に撃墜されていた.

自分も撃墜するぞと意気込むも,ソースコードを見ている内に撃墜されるということが2回・・

0もしくは10^12を突っ込む準備はできていたのに,いざソースコードを開くとそのあまりにも行数の少ない回答に面食らってしまったorz

ああ勿体ない,勿体ない


反省点

  • challengeフェイズでチャンスを逃した

教訓

  • 他人のコードをみても驚かない
  • 確実にいけるのを確認してからでなく,多分いけそうと思ったらchallengeする

2012-01-12

Codeforces Round #102 (Div. 2) 反省

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

Rank: 625/1254

Score: 1152

Solved: 2 (A: 482, 00:09 / B: 670, 01:10)

Rating: 1450 -> 1418 (-32)


B問題時間かかりすぎわろた

Ratingは下がったものの,問題の出来自体は前回よりは若干マシ.

143A

適宜枝刈りしつつ全探索でおk.

4つのマスをそれぞれint w, x, y, zと置いて,1<= w,x,y,z <= 9で4重ループ.

このとき,w, x, y, zの値が重複したり,計算してもr1やc1に適合しない場合はループの途中でcontinue

正しい組合せが見つかった時点でcoutしてreturn.

144B

ただのimplementation.と思ったらコードが超汚くなったorz

何とか根性で解いた.

文字列を整数部と小数部に分けてそれぞれ処理,最後に一緒にcoutすれば良いことに気付いたのは終わってから.

systestで落ちなかっただけマシだけど,こういうところを手早く解いてC以降に取り掛かりたい.

144C

n = (A-1)*(B-2)*(C-2)を満たすときの,A*B*C-nの最大値および最小値を求める.

A-1 = i,B-2 = jと置いて,iとjの1<=i, j <= nの2重ループをするとn<=10^9故にTLEで死ぬ.

iはともかく,jは1<= j <= n/i でいいじゃんと思い,試してみてもやっぱりTLE

2重ループで解く場合は1 <= i <= sqrt(n),1 <= j <= sqrt(n/i)でいけばOKのようだけど,これはつまりえーと・・

nの因数としてのi, jはそれぞれnやn/2も考える必要があると思いきや,k = C-2の計算の際にi = 1, j = 1ならばk = n,i = 1, j = 2ならばk = n/2になるから,i, j ,kが等価(本当に?)であるn = i*j*kにおいてはiやjをn/2まで考える必要がない・・ということか?

素数判定の試し割りに出てくるのと同じ考え方かね.(nの因数を考えるとき,sqrt(n)より大きい数の因数が存在するならば,それより小さい因数も必ず存在するので,sqrt(n)まで考えれば良い)

143D

殆ど見てない.

Standingsを見るとCを解かずにDを解いている人もそこそこいた&pretestに通った人の数も割とCに近かったので,Cで手こずったらDを見るのもありか.

143E

見てない.

反省点

  • 分割して処理すべきデータを常にまとめて扱っていた
  • 数学的思考力が足りない

教訓

  • 一見同じデータに対する処理でも,別々の箇所に行う場合はデータを分割して処理後に統合する
  • 整数問題をこなす

2012-01-08

Codeforces Round #101 (Div. 2) 反省

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

Rank: 763/1262

Score: 482

Solved: 1 (A: 482, 9min)

Rating: Not Rated -> 1450 (Specialist, 緑)


1完\(^o^)/

緑になれたのはTopcoder同様初参加時のレーティングだけ高いというアレだと思うので,今後精進したい.


141A

26文字のアルファベットの数をそれぞれカウントし,前者2文字列と後者1文字列の場合で比べる.

・・が,なぜかvector< pair< string, int > >を使うという無駄な行為に出る.

9分で解けたからまだいいものの,これなら5分で解けた.

141B

ただのimplementation.と思ったらsystestで落ちたorz

でも上位陣も割と落ちてるという..

141C

色々考えたけれどいいのが思いつかず.要再チャレンジ.

141D

見てない.

141E

殆ど見てない.スパニングツリーということはプリム法かクラスカル法?


反省点

  • 実装に無駄が多い
  • 条件文がややこしくなって自爆する
  • Status Number (#)をクリックするとテストの詳細を見れることを知らなかったorz

教訓

  • 定石を覚えて実装の負担を減らす
  • 複雑な記述は多少時間を使ってでも修正する
  • テストに落ちたら詳細を確認して対応する