Hatena::Grouptopcoder

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

2012-02-24

Codeforces Round #109 (Div. 2) 反省

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

Rank: 981/1284

Score: 492

Solved: ox-x-

Rating: 1451 -> 1383 (-68)


フルボッコキタ――(゚∀゚)――!!

の割には,あまり下がってない様子.

いずれにせよ,今回のDは勉強になりました.


155A

最大値・最小値が更新されたらcount++するだけ.

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


155B

a[n]とb[n]を用意しておき,b[i] > b[i+1]になるようにaとbをソート.b[i] == b[i+1]の場合は,a[i] > a[i+1]になるようにソート.

その後,i == 0から順にcount_b == 0になるまでcount_a += a[i], count_b += b[i]すればいいだけ.


が.実際に書いたソートが間違っていたカウントする際の処理を間違えていた/(^o^)\

SRM533 Div2 250のピカチュウの時もそうだったけれど,解法が思いついた状態でさっさと書いたコードの中にケアレスミスがあっても見つけようがないなあ・・

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


C (154A)

前から順に貪欲法で解いて死亡.

abbaaaのときはbを全て潰し,abbaaabbbbのようなときはaを全て潰す必要があることに気付いたのはCを飛ばしてDをsubmitしてから..


D (154B)

何も考えずon/offの状態を配列で保持し,二重ループするとO(10^10)になって死亡する.

ので,on状態のcolliderのみset<long> colsに保持し,offのリクエスト時にはcols.findしてoffを判断.

onのリクエスト時にも同様にcols.findし,無ければリクエストされた番号とcolsの中の番号をしらみつぶしにユークリッドの互除法.


で死亡.そりゃあいくらfindで計算量減らしても,ループの中で全探索やってりゃ結局O(10^10)になるわな・・


診断人さんの放送(http://com.nicovideo.jp/community/co78570)を見ていたら,”整数のペアを共に素因数分解し,同じ素数を持っていたら互いに素ではない”ということを利用すれば良いと知る.なるほど.


k番のリクエストが来たらk番と一緒にkの素因数もon状態と考えておけばユークリッドの互除法は必要なくなる.

更に,使用中の素因数を覚えておけば,k番を削除するときにも役立つ,と.


ついでに,整数が非常に多く出てきても,出てくる素因数はそんなに多くない,というのも有用な情報だと思った.


E (154C)

読んだだけで解いていないが,u, vを使ってる時点でグラフ問題だなあ,という感想.

ノードが2つのみの木を構成するペアおよびその他のノード全てとつながっているノードのペアを探せ,ということですね.


反省点

  • ”互いに素”に対してユークリッドの互除法しか対処法を知らなかった

教訓

  • "互いに素" = "共通する素因数を持たない"と言えるので,素因数分解が有効

2012-02-20

Codeforces Round #108 (Div. 2) 反省

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

Rank: 696/1260

Score: 1288

Solved: oox--

Rating: 1501 -> 1451 (-50)


Cのaccept率826/1260なのにTLEで通せなかったorz


152A

vector<string>に成績を格納し,各科目における最高点を記憶.

別途0で初期化したint a[n]を用意しておき,その最高点と等しい人iはa[i] = 1とする.

最後に,1となった人(=1度でも最高点を取ったことある人)の数を数えればOK.

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


152B

各ベクトルi < kに対し,一回適用するごとにステップ数stepをインクリメントを繰り返す.

それ以上適用できない(フィールドを超える)場合は次のベクトルi+1に移り,同じように一回適用してはインクリメントを繰り返す.

最後にstepを出力・・するとTLEになる.


ので,まずはベクトルiを最大何回適用できるかを数え,その数aの分(dxi * a, dyi * a)だけ一気に移動&step += aする.

aの算出は,ベクトルの向きに気を付けつつ,x方向とy方向それぞれ移動できる回数を求め,小さい方をaとすればよい.

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


152C

TLE@pretest 7の文章を見ること約20回orz


前回"TLEになるようなら大元の処理を見直せ”と反省したものの,何が違うのかさっぱり.

dpしても探索範囲を狭めても処理を軽くしてもTLE


で,他の人のコードを見て納得・・

生成されうる文字列の数 == m文字の各位置で取りうる文字を取った時に生成される文字列の数

なので,各文字列のj<m番目の文字の種類の数を数え,順位掛け算すればよい.</ppp>

正答率が高いのは,この手の問題は頻出もしくは典型的なものなんだろうと予想.

純粋に練習量が足らない・・

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


152D

みてない


152E

みてない


反省点

  • よく考えずに愚直にコードを組んだ
  • 練習量が足らない

教訓

  • Cで愚直な方法は弾かれやすい.アプローチをよく考えるべし
  • 精進すべし

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