hotpepsiの練習帳

SRM 566

03:03

Div1 Easy (250) PenguinSledding

問題

• ペンギンのパーシーがペンギンそり用のコースを設計する
• コースにはいくつかのチェックポイントがあり、それらを直線で結ぶ
• チェックポイントが同一直線状にないことは保証されている
• チェックポイントの座標の精度は非常に悪い可能性がある
• パーシーは慎重なので、直線が交わる可能性を排除したい
• 直線が存在しないケースも含めて、何通りの設計がありうるかを求める

方針

• 直線が交差する可能性があるとダメ
• つまりほとんどダメ。どういうのならOKなんだ...
• ゼロ本はOK
• 1本だけ残すならOK
• 点を共有する2直線はOK、つながってないのはだめ
• sample3の値が異常
• なるほど1点だけから出てるの(スター型みたいなの)はOKか
• 1～36本まで任意の組み合わせ=combinationの和かな
• それっぽい
• sample4で数が足りない
• 三角形なら3辺でもぶつからない!
• 三角形判定追加
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_566/PenguinSledding.cpp

Div2 Easy (250) PenguinTiles

問題

• スライドパズル
• 全て同じ絵
• 右下を空けたい
• 最小の手数を求める

方針

• 右下が空いているならゼロ
• 右端か下端が空いているなら1
• それ以外は2
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_566/PenguinTiles.cpp

Div2 Medium (500) PenguinPals

問題

• ペンギンのマッチングサービス
• 青か赤のどちらが好きか聞く
• 円状に並ぶ
• 同じ色同士を直線で結ぶ
• 最大のペア数を求める
• 直線は交差してはならない

方針

• DPかな
• start,endを決めて、端点同士が同じ色なら、+1してその内側を数える
• 合わない...
• 隣り合うケースを忘れていた
• だいたい合う(だめすぎ)
• サンプル1のように並行で区切るやつしか考えていなかった
• 3等分みたいな区切り位置を考慮する必要がある
• start,endを任意の位置で区切ってメモ化
• 隣り合うやつは、端点同士の特殊な場合として吸収
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_566/PenguinPals.cpp

結果

o-- 111.06 372/701 rating 1327 -> 1373 (+46)

easyはTopCoderらしい問題だと思った。これが解けたのは非常に良かった。

そりのコースとしては全然だめだと思うが!

combinationの和は2の累乗ということに気づかなかった。

部屋はeasy提出者全員AC、medium提出者なし、チャレンジなしだった。

div2mediumが難しかった。

SRM 565

22:00

Div1 Easy (250) MonstersValley

問題

• N匹のモンスターに順番に遭遇する
• それぞれのモンスターは1～2枚の金貨で買収できる
• 遭遇したモンスターの恐ろしさが、買収したモンスターの恐ろしさの合計値を超えている場合、モンスターを買収する必要があり、そうでない場合は買収してもしなくてもよい
• 必要な金貨の枚数の最小値を求める

方針

• あからさまにDPだが、恐ろしさの数値がlong long
• 金貨の枚数は最大100なので余裕で収まる
• 提出
• バグってる...
• 再提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_565/MonstersValley.cpp

結果

o-- -1 50.0pt 444th rating 1302 -> 1327 (+25)

1文字写経をミスってチャレンジ失敗。なんとかプラス点は確保した。

今年のSRMは530以外は全て出て、ratingが1093->1327(+234)だった。

今のところ参加したコンテストは全て日記をつけているので自分にしてはかなりマメだと思う。

今年の目標(SRMで一瞬黄色になる＆GCJ R1突破)は達成した。来年は複数回黄色＆GCJ Tシャツを目指す。

SRM 564

03:41

Div1 Easy (250) KnightCircuit2

問題

• w×hのサイズのチェス盤がある
• 左上からナイトが到達可能な升目の総数を求める

方針

• wとhの小さいほうをa、大きいほうをbとする
• aが1のときは1 (最初の点から動けない)
• aが2のときは(b+1)×2
• aが3のときは...bが3なら8、それ以外はa×b
• aが4以上のときはa×b
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_564/KnightCircuit2.cpp

Div1 Medium (500) AlternateColors2

問題

• R、G、Bの三色のボールが、合計N個かある
• ボールをR、G、Bの順番で破壊するロボットがいる
• K番目のボールはRであるとき、ボールの個数の組み合わせの総数を求める

方針

• 最大で3色使えて、使える色は減っていくこともある
• 色は順番に選ばれる。存在しない色は飛ばされる
• DPかな
• (終了後)
• dp[x番目][使える色のビットマスク][終端の色]
• K番目の場合だけRしか処理しない
• 色がなくなるときに場合わけしてカウントを増やす
• すごく面倒な感じに書けた
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_564/AlternateColors2.cpp

結果

o-- 204.77pt 382nd rating 1250 -> 1302 (+52)

場合わけとか判定が入るやつは苦手。3×3はたまたま気づいたが落としてもおかしくなかった。

同室の診断人さんには負けてしまったが、200点取れたのでなかなか良かった。

提出後いまいち自信がなかったので総当りの関数を書いて比較したら、そっちがバグっていて時間を食った。

mediumは力技で何とか解いた。DP力は多少上がっていると思う。

場合の数など、これ以外の方法で解いているコードは理解できなかった。

SRM 563

01:22

Div1 Easy (300) FoxAndHandle

問題

• 二つの文字列を、どちらかの先頭から一文字ずつ結合していく操作をシャッフルとする
• シャッフル後の文字列が与えられる
• 元の文字列の候補のうち辞書順最小のものを求める

方針

• 文字をカウントして半分にしたものが元の文字列の必要要素
• 蟻本に辞書順最小は貪欲と書いてあった気がする...
• (終了)
• kojingharangさんの日記を読む
• 先頭の文字を決めて、その位置から成立可能かどうか調べる
• なるほど...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_563/FoxAndHandle.cpp

Div2 Easy (250) FoxAndHandleEasy

問題

• 文字列の途中に同じ文字列を挿入する操作を拡張とする
• 与えられた文字列が拡張操作によるものかどうかを求める

方針

• 誤読して時間がかかる
• 前とうしろの文字列を結合して調べればよい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_563/FoxAndHandleEasy.cpp

Div2 Medium (550) CoinsGameEasy

問題

• 盤面にコインが二つ置かれている
• 上下左右のいずれかにゆすることで1マス動かすことができる
• 10回以内の操作で1つだけ落とすことができるかどうかを求める

方針

• コインの位置でBFS
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_563/CoinsGameEasy.cpp

結果

0pt 328th rating 1268 -> 1250 (-18)

div1,div2ともにやや難しかった。

UTPC 2012

11:41

A. 2012年12月02日

任せた。

AC

B. 残像に口紅を

問題

• 筒井康隆!!

方針

• 逆から使える文字を増やしていく
• AC

C. 森ですか？

問題

• 完全グラフとクエリが与えられる
• クエリ毎に森かどうか答える

方針

• 任せたが、バグっていたのでDと交代
• 単純に配列で持って部分点get
• 頂点がsqrt(100000)以上のときは森にならないのでは?
• データの持ち方がいまいちでTLE

D. 地図が２枚

問題

• 地図の中に縮尺1/2の地図
• 固定点を求める

方針

• 単純な行列式だと思うんだけど...
• 交代
• 部分点get (さすが学生!)

E. 選挙

任せた。

部分点get

F. Uinny

問題

• 同じハッシュ値を持つ文字列を最大100個生成する

方針

• 長さaの文字列でb個見つけて、掛け合わせればa×a個生成できる
• 7点くらいget

結果

チーム抹茶としてat.kanon君とオンサイト参加。

357.28pt チーム16位

初めてチーム戦をやってみたがなかなか楽しめた。CとDはすぐに交代したほうが良かったかもしれない。

全体的には難しかった。問題文と部分点で楽しませてもらった。

練習問題は毎年面白いらしい。TLEかMLEのどちらかを生じさせて場合わけすれば問題文がわかるとかそんな感じだろうか。解いてる人もいたのでさすがである。