hotpepsiの練習帳

TCO 2013 Round 1A

01:02

Easy (250) HouseBuilding

問題

• 家を建てるために土地を買った
• 土地はでこぼこで、高さの配列が与えられる
• 全体の高低差を1以下にするためのコストを求める

方針

• 二重ループで全探索
• なぜかはまる
• 場合わけして書く
• 提出
• Passed System Test
• 書き直し
• https://github.com/firewood/topcoder/blob/master/tco_2013/HouseBuilding.cpp

Medium (500) TheFrog

問題

• 蛙が距離Xずつジャンプする
• 穴の開始と終了の座標が与えられる
• 穴を全て飛び越えるための最小のXを求める

方針

• 二分探索かな...複数の候補があるので無理っぽい
• 最小値は必ず最後のRを通る気がする
• 最後のRをN等分してみる
• なんか最後のLを通るケースもありそう
• サンプル通る
• 提出
• Failed System Test
• 書き直し
• 最小の距離で飛び越えようとすると、どれかの端点Rを通ることになる
• それぞれの端点RをN等分した距離で可能かどうか調べる
• https://github.com/firewood/topcoder/blob/master/tco_2013/TheFrog.cpp

結果

ox- 797th/1752 rating 1411 -> 1383 (-28)

mediumが手ごわい問題だった。

SRM 571

23:31

Div1 Easy (250) FoxAndMp3

問題

• MP3のファイル名を辞書順にソートする
• 先頭の最大50曲を求める

方針

• 順番に作れそうだが、場合わけが面倒そうなので挫折
• DFSで適当に1000個くらい生成してset<string>に突っ込む
• 先頭の50曲にして返す
• 提出
• Passed System Test
• 書き直し
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_571/FoxAndMp3.cpp

結果

o-- 151.04pt 567th/769 rating 1449 -> 1411 (-38)

ソートしないで作るやりかたはおっかなくてできなかった。弱い。

SRM 570

13:42

Div1 Easy (250) RobotHerb

問題

• ロボットがXY平面上を移動する
• 命令が数値の配列で与えられる
• 各命令では数値nだけ直進し、n回90度右回転する
• 命令列全体をT回実行後、スタート地点からのマンハッタン距離を求める

方針

• サンプル読んで、シーケンスa全体をT回繰り返すことを確認
• 実行後の向きは4通り
• aの実行後、向きが最初と同じなら、距離が単純に増加していく
• そうでない場合は次の実行でもまた角度が変わる
• よく考えたら4通りどのパターンでも、4回実行したら元の角度に戻る
• 4回愚直にaを実行して、結果の距離をT/4倍してから、T%4回実行すればよい
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_570/RobotHerb.cpp

Div2 Hard (1000) CentaurCompanyDiv2

問題

• 株式会社ケンタウロスにはN台のサーバがある
• 会社を株式会社人間と株式会社馬に分割することにした
• 各サーバは木構造で接続されている
• 各サーバはそれぞれのどちらかに所属する
• 分割後、元々接続されていなかったサーバはケーブルが必要になる
• 馬は十分なケーブルを持っているが人間は持っていない
• 人間側がケーブルを必要とする分割はできない
• 有効な分割が何通りか求める

方針

• 木DPらしい
• なんと弟子がスライドを書いてくれた。わかりやすい!
• https://github.com/atkanon/TopCoder/raw/master/SRM570/srm570div2hard.pdf
• 大まかな手順としては、あるノードを親ノードPとして、P以下だけが選択された場合の数Kを求める
• DFSで子ノードCを親ノードとした場合の数Xを求める
• その子ノードを使わない選択肢もあるので、その子ノードについてX+1通り
• 全ての子ノードについて、あり得るパターンは掛け算なので、X+1の積を取る
• Kを記憶しておく
• Kの総和に、全てのノードを選択しなかった場合(全部馬)の1を加えたものが答え
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_570/CentaurCompanyDiv2.cpp

結果

o-- 198.96pt 246th/740 rating 1364 -> 1449 (+85)

div1 mediumが難しかったためeasyの速解き回。順位はとても良かった。久しぶりの1400台。

easyはアフィン変換でも解けるようなので試してみた。繰り返し二乗法で短縮可能。

div2 hardは問題文が面白い。馬って何だろうと考えてしまった。accumulateの初期値に0と書いたら戻り値がintになってしまいはまった。初心者すぎる。

Codeforces 166

20:02

A. Beautiful Year

問題

• 美しい年とは全ての桁の数値が異なる年である
• 与えられた年以降で最初の美しい年を求める

方針

• ループして調べる
• 提出
• Passed System Test

B. Prime Matrix

問題

• 行列が与えられる
• ある要素を1回の操作で1だけ増やせる
• ある1行全てを素数、または、ある1列全てを素数にしたい
• 最小の操作回数を求める

方針

• 素数を求めてsetに入れておく
• 各要素について、その数以上の素数はlower_boundで求まるので、和を配列に入れる
• 全行、全列のうちの和の最小値が答え
• 提出
• Passed System Test

C. Secret

問題

• 1からNまでのN個の数値からなる集合XをK個の集合Uに分離したい
• Uの任意の2つの要素は互いに素
• Uの全ての和集合はX
• Uの要素は等差数列でないこと
• 条件を満たすUを求める

方針

• 等差数列を満たさないようにするためには要素が3個以上必要
• ということはN >= 3*K が必要 (そうでなければ-1を返す)
• 不規則的に配ればオッケー
• N=9、K=3のとき
• U1に1,2、U2に3,4、U3に5,6,...と2つずつ配ってから、U1に7、U2に8のように配れば不規則
• 余ったら全部U1に配ってよい
• 提出
• Passed System Test

D. Good Substrings

問題

• 文字列Sと、ダメな文字の一覧が与えられる
• ダメな文字を最大でK個まで含む、Sの連続したindexを使用した部分文字列の総数を求める

方針

• とりあえず愚直に
• 提出
• MLE

結果

ooo-- 2682pt 192nd/1677 rating 1687 -> 1680

Cまで解いて40分だったのでまあまあ良かった。

Dはハッシュ使えばいいらしい。

AtCoder Regular Contest #012

21:13

A. 週末

問題

• 週末大好き高橋君
• 週末までの日数を求める

方針

• 比較するだけ

B. アキレスと亀

問題

• カメが大好き高橋君
• カメがいた場所に向かう
• N回移動した後の距離を求める

方針

• 速度abs(A-B)で近づく
• Nが小さいのでループで計算
• 10^-7より小さかったらゼロにする

C. 五目並べチェッカー

問題

• 五目並べ大好き高橋君
• 先手黒で、ありえる盤面か調べる

方針

• 全升目を愚直に調べる
• だめぽ...
• (終了後)
• 最後に置いた石を見つけるには、勝利で終わっている状態があったら石を取り去ってみて、誰も勝利していない状態になるかどうかを調べる、とのこと。頭いい。

結果

oo-- 200pt 72nd/267 rating 6級 → 5級

進級した!