Hatena::Grouptopcoder

Div2脱出のための日記 このページをアンテナに追加

 | 

2011-07-23

Codeforces Beta Round #78 Div. 2

| 17:51 | Codeforces Beta Round #78 Div. 2 - Div2脱出のための日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #78 Div. 2 - Div2脱出のための日記 Codeforces Beta Round #78 Div. 2 - Div2脱出のための日記 のブックマークコメント

結果

rating 1438 → 1438

points: 0

  • A: WA 00:20
  • B: WA 40分くらい
  • C: Openして、問題は理解した。
  • D: Openしたが、題意が取れず。
  • E: Openして、問題は理解した。
  • Hacks: 撃墜なし/非撃墜なし

room 17: 28位

全体: 821位

ABがWrong Answerで、CDEは手が出せず。全滅でありました。 :-(

どうも他の方の日記によるとD問題が意味不明過ぎて、

unrated回になったということのようで、うまいこと救われた形になりました。

問題

  • A. Help Far Away Kingdom

標準入力で与えられる実数の整数部の一の位が'9'の場合は、"GOTO Vasilisa."を標準出力に表示し、

それ以外の場合は小数部分が'0.5'以上であれば切り上げた整数を'0.5'より小さければ切り捨てた整数を

標準出力に表示しなさい。

  • B. Help Chef Gerasim

n個のコップに注がれた液体を全てのコップで等しい量になるよう1度だけ注ぎ直す。

標準入力の1行目はカップの数n、2行目以降の行がコップに注がれた液体の量。

入力が以下の場合、

3

270

250

230

"20 ml. from cup #4 to cup #1." と表示する。

既に全てのコップの液体の量が等しく、調整の必要がない場合、"Exemplary pages." と表示する。

調整しても全てのコップの量を揃えられない場合、"Unrecoverable configuration." と表示する。

  • C. Help Victoria the Wise

サイコロの各面を標準入力で指定された文字列の1文字づつを使って塗り分け、その塗り分けの種類数を標準出力に出力せよ。

入力が"BOOOOB"の場合、"2"を表示。

"YYYYYY"の場合、"1"。

"ROYGBV"の場合、"30"。

  • D. Help King

王女の婿候補n人をコインを投げた裏表で選別して婿を決定する。婿が決まるまでに必要なコインの投擲回数を表示せよ。

n=2なら1/1

n=3なら8/3

  • E. Help Greg the Dwarf

長さ'l'幅'w'の棺桶を屈折した通路を通せるように作りたい。

通路は直角に屈折した部分があり、折れ曲った一方の通路の幅は'a'で、もう一方の幅は'b'。

棺桶の長さ'l'は身長から決まっているので、通路を抜けられる幅'w'の最大値を求めよ。


DIV1との関連

今回のDIV2の問題のうち、DIV1の問題でもあるものは、

DIV2DIV1
C A
D B
E C

みごとにスライドして使われています。

DIV2でCDEを正答できないとDIV1に上っても定着できないということですね。

解答

解答は全てpythonです。

  • A. Help Far Away Kingdom

以下は提出したものではなく、後でsystem testを通したもの。

x, f = raw_input().split('.')
n = int(x)

if x[-1] == '9':
    print "GOTO Vasilisa."
else:
    if f[0] >= '5':
        print n + 1
    else:
        print n

入力は常に小数点付きの実数ということなので、入力を整数部と小数部に分けた文字列として解析している。

提出した解答では、小数部の文字列を/= 10などと割っていって、'0.5'以上になるか判定していたのが、NGだった模様。

  • B. Help Chef Gerasim

BもAと同じく、後でsystem testを通したもの。

n = int(raw_input())
li = [(int(raw_input()), i + 1) for i in xrange(n)]
li.sort()
mx = li[-1]
mn = li[0]

if mx[0] == mn[0]:
    print "Exemplary pages."
    exit(0)

if (mx[0] - mn[0]) % 2 == 1:
    print "Unrecoverable configuration."
    exit(0)

val = (mx[0] - mn[0])/2
vv = mn[0] + val
li.pop(0)
li.pop()

if len(li) != len([x for x in li if vv == x[0]]):
    print "Unrecoverable configuration."
    exit(0)

print "{0} ml. from cup #{1} to cup #{2}.".format(val, mn[1], mx[1])

実戦の解答では、

2

1

0

というケースで0.5mlづつには分割できないということで、

"Unrecoverable configuration."とするべきところが処理できず、

WAとなっていた。

問題に明記されているのだが、液体の量がIntegerで表現されるところが微妙な引っ掛け。

豆の数とかキャンディーの数とか加算名詞であれば対応できたと思うのだが。

総括・反省

  • A.

float変数は極力使うな。なるべく文字列かIntegerとして扱え。

という格言(今作った)通りの問題。

今回は文字列だけで間に合う問題なので、格言に従っておけば何の問題もなかったはず。

  • B.

問題に登場する人・物は理解を助けるイメージに過ぎないので、

一旦、問題を記号と数学的性質に抽象化し、そのレベルで考慮すべき条件に抜けがないか確認せよ。

これも格言(?)通りでした。液体なのにIntegerという具体例に微妙な点があるなら、

騙されないように整数として抽象化しておくべきでした。そうすれば、最大と最小の差が2で割れない時の扱いは、

"Unrecoverable configuration."にするくらいしか無さそうという予想がついたはず。

  • C.

codeforcesで付いたtagによると"brute force"なので、

総当たりで解けるらしいですが、同じ模様の違う並びを同じかどうか判定するという部分をどうするか想像付かない。

  • D.

これは英語ゲーっぽい。候補一人一人の前でコインをトスして表が出れば合格ってことなのか?

丁半博打のように候補に裏表を賭けさせてから、おもむろに王様がコイントスするのか?

色々なふるい分け方法がありそうなんだけど選別方法は問題文には含まれてないような。

方式も含めてトスが最小になるようにしろというのが題意なのか?

Petrさんも解けてないぞ。

  • E.

大学1年生の時なら解けてそうな問題。三角関数の公式とか忘れました。

学生時代なら、計算機なしで微分して極大極小を計算して後は値の代入のみというところまで

持っていくことはよくやったな。1時間で出来るかというと怪しいけど。

実は解析なしで、幾何だけで解けちゃったりするのかもしれまんが。

以上。

tatuyan_edsontatuyan_edson2011/07/23 20:41はじめまして。
Cは全部数え上げるという手もありますよ。
Dですが、そもそも題意が取れません。おっしゃるとおり、選別方法が書いておらず、意味がわからないからunratedと、Editrialに書いてありました。後日再アップするみたいなので、その時に意味がわかるかも知れません。

hide5stmhide5stm2011/07/23 22:14http://codeforces.com/blog/entry/2323
ありがとうございます。ホントですね。
総評みたいのが出てるのですね。

GabrielGabriel2012/07/09 23:11Whoa, things just got a whole lot eaiesr.

nqephnzmlsgnqephnzmlsg2012/07/10 15:44H7ATQc <a href="http://dsbenakwexdo.com/">dsbenakwexdo</a>

 |