hotpepsiの練習帳

SRM 520 Div2

14:53

SRMの回。ナイスな問題。

Easy (250) SRMRoomAssignmentPhase

問題

• 部屋割り
• K部屋にレートの高い順に割り当てる
• 同じ部屋で自分よりレートが高い人の人数を答える

方針

• 逆から数えた
• 数えなくてもindexがわかればよい
• ソートしなくてもcount_ifで数えるだけでよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_520/SRMRoomAssignmentPhase.cpp

Medium (500) SRMCodingPhase

問題

• コーディングフェーズ
• 75分以内に解けるとポイント加算
• luckを使うと時間が短縮できる
• 得られる点数の最大値を求める

方針

• 全試行
• DPでできそうだが...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_520/SRMCodingPhase.cpp

Hard (1000) SRMSystemTestPhase

問題

• ランキングが確定している
• ランキングとsubmitしたかどうかが既知
• スコアボードが何通りあるかどうかを答える

方針

• 最下位からDPでできるはず...
• わからなかったのでkusanoさんのを写経
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_520/SRMSystemTestPhase.cpp

結果

oo- 227.74+198.49=426.23 rating 1174 -> 1169

medium遅し。

hardはめっちゃ時間かかった。

SRM 519 Div2

01:05

Easy (250) WhichDay

問題

• 6つの曜日が与えられるので、残った1つを答える。

方針

• 連想配列のある言語なら一発でできる
• std::map<string, int>に突っ込む
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_519/WhichDay.cpp

Medium (500) ThreeTeleports

問題

• 始点 (xMe,yMe) から終点 (xHome, yHome) までの最短コストを求める。
• ワープできるポイントが3つある。
• ワープするとコストが10かかる。
• ワープする2点は、どちらも始点として使える。

方針

• 本番では全探索した
• ダイクストラっぽく書き直してみたが、全てのノードからゴールに直接行けるので結局全探索している
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_519/ThreeTeleports.cpp

Hard (1000) BinaryCards

問題

• 0から63まで番号のついた64枚のカードがある。
• 番号xのカードは、片面に2^x個のドットが描かれている。
• ドット数の総和がAからBまで、1ずつ増加する様子が見えるように最小の手順でめくっていく。
• ZからZ+1に遷移させるとき、複数のカードをめくる必要がある場合には最大のカードからめくる。
• 途中経過で見える最大の和を答える。

方針

• 異なる最上位のビットと、それ以下の全てのビットを立てる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_519/BinaryCards.cpp

結果

oo- 243.50+258.65=502.15 rating 1154 -> 1174

mediumのきれいな書き方がわからず力業で埋めたため遅かった。

SRM 518 Div2

01:03

Easy (250) TwiceString

• 同じ文字列が2回出てくる最短のものを求める。
• 普通に全試行。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_518/TwiceString.cpp

Medium (500) LargestSubsequence

• 部分文字列のうち辞書順最大のものを求める。
• 前から見て全試行したが、後ろから見るとO(n)だったらしい。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_518/LargestSubsequence.cpp

Hard (1000)

• N枚のコインがあり全て表になっている。
• Kターン後に表になっている枚数の期待値を求める。
• 最初から1ターンずつ計算したらサンプルと合ったので提出
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_518/CoinReversing.cpp

結果

ooo 241.27+305.88+493.62=1040.77 rating 1100 -> 1154

Easyは全く悩む所がなかったが、テストケースを手で書いていたため5分かかった。

Mediumをきれいに書き直してたら20分くらいかかってしまったが、変なバグを埋め込むよりはよかった。

初めてHard通った。しかし簡単な回かつ遅かったためrate上昇はそこそこ。

SRM 517 Div2

13:42

Easy (250) MonochromaticBoard

• H×W個の白で塗られたマスがある
• 白か黒からなる入力と一致するように塗る
• 塗りの最小回数を答える

短くするとバグりそうだったので冗長に書いた

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_517/MonochromaticBoard.cpp

Medium (500) CompositeSmash

• 整数Nと整数targetが与えられる
• 整数xが2以上の二つの整数yとzの積で表せる場合、ぶつけるとyとzに分離される
• Nをぶつける過程において、どのような分離が行われた場合でもtargetが含まれるかどうかを答える

素数の場合がとかに場合わけしてしまい失敗。やられたがこれは良い問題だと思った。名前がかっこいい

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_517/CompositeSmash.cpp

Hard (1000) CuttingGrass

• N種類の芝生があり、初期値はinit[i]で育つ速度がgrow[i]
• 全体の長さがH以下になるまで、どれか一つを切る
• 何回切る必要があるかを答える(不可能なら-1)

kusanoさんのを写経して理解

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_517/CuttingGrass.cpp

結果

ox- 168.73+50 rating 1076 -> 1100

Mediumが色々ひっかかりそうだと思ってみていたので、はじめて撃墜成功した。

SRM 513 Div2

01:37

不参加。あとで解いた。

Easy (250) TrainingCamp

• 聴講をさぽった生徒が何問解けるか答える
• 眠いときに解くとrowとcolumnのどれがどれだったかわからなくなる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_513/TrainingCamp.cpp

Medium (500) YetAnotherIncredibleMachine

• ボールが全部落ちる配置が何通りか数える
• 単純にループして判定
• どう動かしてもダメな板がはさまっていた場合はゼロにする
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_513/YetAnotherIncredibleMachine.cpp

Hard (1000) CutTheNumbers

問題

• 最大で4x4の各マスに数値が書かれている。
• 任意の場所の数値を左から右または上から下に読むように分割する。
• 分割した数の合計の最大値を求める。

方針

• メモ化
• 無駄にインライン関数を使ってみた。GCCの場合__builtin_ctz、VC++の場合_BitScanForward
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_513/CutTheNumbers.cpp