Hatena::Grouptopcoder

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

2012-02-17

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