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を挟むキャストは誤差の温床.整数だけでできる処理は極力整数だけで行う

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/kmats/20120217