hotpepsiの練習帳

SRM 549

01:06

Div1 Easy (250) PointyWizardHats

問題

• 上用のコーンと下用のコーンを使って帽子を作りたい。
• 下コーンに上コーンを載せたとき、下コーンの頂点が上コーンに当たらず、かつ、下コーンが隠れないようにしたい。
• 最大でいくつの帽子が作れるか求める。

方針

• 何通りの帽子が作れるか、と読んでしまい時間を浪費。反省
• なんかDPっぽいなあと思いつつ、適当に貪欲で書く
• 終了30秒前にサンプル通るだけのコードを提出
• 終わったあたりで二部マッチングの存在を思い出す
• 被撃墜...すばらしい読解力だ!
• 蟻本を写経したら通った。しかし理解していない...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_549/PointyWizardHats.cpp

結果

x-- 0pt 382nd rating 1392 -> 1339 (-53)

余分な部分をカットすればもっとたくさん帽子が作れますよ!

SRM 548

01:55

Div1 Easy (250) KingdomAndTrees

問題

• N本の高さがばらばらな木がある。
• パワーXの魔法を使うと、木の高さを最大±X変化させることができる。
• 木の高さを昇順にするための最小のパワーを求める。

方針

• 最小・最大を取ったり無駄な時間を過ごす
• わかんないから試行すれば...二分探索?
• 判定関数では、できるだけ最小になるように寄せる
• なんとか提出
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_548/KingdomAndTrees.cpp

結果

o-- 172.43pt rating 1382 -> 1392

まあプラス点ではある。

末端の処理に自信がなかったので、high-lowが2以下になったらループするというひどいコードで提出。-1からMAXまでで探索すればよかったらしい。

SRM 547

02:03

Div1 Easy (250) Pillars

問題

• 2本の柱があり、柱間の距離はwである。
• それぞれの柱の高さは、1からx、および、1からyのいずれかである。
• 柱の上端をまっすぐなロープで結ぶとき、ロープの長さの期待値を求める。

方針

• xとyのうち、低い方をa、高い方をbとして、高さの差で場合わけしてみる
• 高低差をdとする
• d=0(同じ高さ)になるのはa通り
• b側が高い場合、b側の一番低いケースの高さは1+d、一番高いケースの高さはmin(b, a+d)なので、(min(b, a+d) - (1+d) +1)通り
• a側が高い場合、a側の一番低いケースの高さは1+d、一番高いケースの高さはaなので、(a - (1+d) + 1)通り
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_547/Pillars.cpp

結果

o-- 120.31pt 270th rating 1352 -> 1382 (+30)

なんとかプラス点。

SRM 546

23:35

Div1 Easy (250) KleofasTail

問題

• ある数値を、偶数なら1/2、奇数なら-1していく。
• 範囲AからBまでの数Xについてその操作を行う。
• 一度でも数Kが出現するXの総数を求める。

方針

• 一番下のビットが落ちていく
• 途中でKを経由するかどうかを判定する
• 上位のビットがKならOKっぽい
• ゼロはどうやら特別扱い
• 上位ビットがKでNを超えない総数を求めるf(N)を書いて、f(B)-f(A-1)でいける
• Kが偶数のときは、K|1もKを経由するので、それを考慮
• 一時間以上かかって提出
• (書き直し)
• Kをlower、K|1をupperとして、1ビットずつ大きくしていって、lower<=X<=upperとなるものを数えればよい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_546/KleofasTail.cpp

結果

o-- 95.63pts 362nd rating 1278 -> 1352 (+74)

久しぶりのプラス点。

だいぶ無駄なコードを提出してしまい反省。

AtCoder Regular Contest #004

00:13

初参加。

A. 2点間距離の最大値 (The longest distance)

問題

• http://arc004.contest.atcoder.jp/tasks/arc004_1

方針

• dx*dx+dy*dyの最大値を全探索して、sqrt取る

B. 2点間距離の最大と最小 (Maximum and Minimum)

問題

• http://arc004.contest.atcoder.jp/tasks/arc004_2

方針

• 全ての点を使って、最初の点に戻ってくる可能性があればゼロ
• 最も長い辺が、そのほかの点の全ての合計より短ければ、多角形ができるので、ゼロにできる
• そうでない場合、最も長い辺と、そのほかの合計の差が答え
• max(0, (最大-(合計-最大)))でOK

C. 平均値太郎の憂鬱 (The melancholy of Taro Heikinchi)

問題

• http://arc004.contest.atcoder.jp/tasks/arc004_3

方針

• 不等式でNの範囲を決めるらしい...なかなか合わない

結果

A、Bのみで200pt。

このシステム、WAの場合に内容が出ないのがつらい。