Codeforces Beta Round #36
久しぶりのCodeforces.
最近まともにプログラムを書いていないので、EPOCH@まつやまに向けてのリハビリを兼ねて出場。
Result
1743->1712
102位 428(-1) / 896 / (-5) / - / -
C
今回はCから解いていく戦略で行こうと思いまず読んでみる。
皿を重ねる問題。
……これ、重ね方の場合分けもの凄く面倒じゃない？さすがにはまれないので飛ばす。
B
Bを読もうと思ったら問題がエラーで表示されない。仕方ないのでAへ。
結局時間損しただけだった。。。
A
問題
0と1からなる文字列が与えられる。文字列中に登場する1の間隔が全て等しいならYESを、そうでないならNOを出力せよ。
試行錯誤
今回は入出力が標準入力ではなく、ファイル入出力になったようだ。
一体誰得……ファイル入出力の仕方について一応調べる。確かfstreamだかをincludeする必要があった筈。
できた。提出。PE. 入出力間違ってる！ふぁっく！
直して送信。
C
で、問題のCへ。
問題
円錐の頂点を底面に切り落とした形で表される皿がある。
下側の円の半径をr,上側の円の半径をR,高さをhとする。各皿のr,R,hが与えられたとき、
最も下の皿の底の面から、最も上の皿の高い部分までの長さを求めよ。
試行錯誤
まずは皿の重なり方を分類してみる。
- 一つが一つにすっぽり収まる場合
- 下の皿の側面に上の皿の下の面がぶつかる場合
- 上の皿の側面に下の皿の上の面がぶつかる場合
- 下の皿に上の皿が完全に乗る場合
がある。。。よな、何これ自信ない……
しかもすっぽり収まってる場合は干渉しうる皿の組み合わせがいっぱいあるので、
全て判定するとO(n^2)になりそう。
間に合うの？ケースリミット2secでn<3000
まあ間に合わないともう解きようがない。。。
それぞれの場合の条件を書いて、
全ての皿と直接重なる場合を書いて、んでそれの最大値を取るような感じで書いた。
4回WAを出して、最後に小数点誤差死しているのを直したらPretestに通った。
D
残り20分。解いている人は多いが苦手なゲーム問題だし、時間短い。。。
問題
wxhのサイズのチェスとチェスのコマを使い、二人で次のようなゲームをする。
- プレイヤーはコマを右または下に1マス動かすことができる
- プレイヤーはコマを右下の斜めに1マス以上kマス以下動かすことができる
このとき、先にコマを動かすことのできなくなったプレイヤーが負けである。
盤のサイズおよびkが与えられたとき、お互いが最善を尽くすとして勝利するプレイヤーを答えよ。
試行錯誤
どうやるんだろ。斜め移動しかできないとすると、L=min(n,m)として、
L=1後手勝ち
L=2〜k+1先手勝ち
L=k+2〜2k+1後手勝ち……
になるはず。
縦横の移動ができるとパスみたいのが何回かできることに相当するのか？？
とか考えているうちに時間終了。
System Test
Cが落ちた。ですよね。こんなの合ってる気がしなかった。
久しぶりに参加した割にはまあまあだったんじゃなかろうか。
