hotpepsiの練習帳

Codeforces 147 Div2

20:18

A. Free Cash

問題

• 店に来る客の時間がわかっている
• レジは1分かからないが、いっぱいだと客は帰ってしまう
• レジをいくつ用意すればよいか

方針

• 直前と同時刻のものをカウントするだけ

B. Young Table

問題

• テーブルに並んでいる数値を、左から右、上から下へ昇順となるように交換により並べ替えたい
• 交換手順を答える

方針

• 左上→下→ひとつ右の上→下...と昇順に並べることにする
• 左上から、今の値と目標が違う場合は交換手順として出力

C. Primes on Interval

問題

• aからbまでの範囲の連続するl個の整数にk個以上の素数を含めたい
• 最小のlを求める

方針

• 全探索しか思いつかない...とにかく愚直に求める
• 残り30秒前ですべりこみ提出
• Passed System Test

結果

ooo-- 2000pt 356th rating 1507 -> 1581 (+74)

Cは二分探索らしいが理解できてない。

SRM 558

05:47

Div1 Easy (275) Stamp

問題

• 升目をスタンプで3色に塗る。
• スタンプを作るコストと塗るコストが与えられる。
• 最小のコストを求める。

方針

• 常に重ね塗りOKと誤読
• Failed System Test
• 解き直し
• DPで位置[i]までのvalidなパターンのコストを求めていく
• 塗ることができる最大長がわかっていればよく、色は気にしない感じ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_558/Stamp.cpp

結果

x-- 0pt 329th rating 1378 -> 1354

せっかくのオンサイトだが何もできずに終わってしまった。

pushCost * ((j+L-1)/L)をpushCost * (j+L-1)/Lとしたら最初の掛け算が先に評価されてしまいはまった。

Codeforces 144 Div2

03:04

A. Perfect Permutation

問題

• 「完璧な順列」とは、i番目の要素p_iの値をjとしてp_j＝iかつi≠jのものをいう。
• 与えられた長さの完璧な順列を求める。

方針

• 要素数1だと不能、3もだめっぽい
• 偶数だと交互に入れ替えればいける
• たぶん奇数がだめということでsubmit
• AC

B. Non-square Equation

問題

• ある数xの10進数表記の各桁の数値の和をs(x)として、x^2+s(x)x=Nとする
• nからxのうちの最小のものを求めよ

方針

• xはsqrt(N)より小さい
• sqrt(N)からループで調べる
• なんとかAC

C. Cycles

問題

• 頂点100個以内で3つの辺からなる閉路をk個生成せよ

方針

• 全ての辺をつなぐとn_C_3個になる
• 近い値まで規則的に生成してからランダムでいけるらしいので、やってみたら通った
• 2つのかたまりをマージするみたいな感じでも解けるっぽい

結果

oo--- 451st 1122pt rating 1500 -> 1507 (+7)

div1は絶壁

SRM 557

03:31

Div1 Easy (250) FoxAndMountainEasy

問題

• スタート地点の高さがh0で終点の高さがhnの登山路がある。
• 登山路はなだらかで±1の高低差からなる。
• 部分的なアップダウンの情報が与えられる。
• 登山路が成り立つかどうかを求める。

方針

• 高さは0以上という制約を踏まえてシミュレーション
• なんとか提出、AC
• (解き直し)
• h0からシミュレーションしてみて、途中もし負になったら、先頭にシーケンスUを追加する
• 長さが足りないか、残りの偶奇が合っていなければ不能
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/FoxAndMountainEasy.cpp

Div1 Medium (550) Incubator

問題

• インキュベーターが少女と契約する。
• 少女は契約すると魔法少女となり、自分が守りたい少女を守る。
• 誰かに守られた少女もまた、自分が守りたい少女を守る。
• 守られていない魔法少女の最大人数を求める。

方針

• (終了後)
• LayCurseさんのところとか色々読む
• 少女Aを魔法少女にしたとき、最終的に保護されることになる全少女は、ワーシャルフロイドで求める(少女iが少女kを保護し、かつ、少女kが少女jを保護するなら、少女iは少女jを保護することになる)
• 保護者から被保護者へ辺を張る
• 被保護者をなるべく生じさせないようにする＝相互につながっていない集合を求める＝典型問題(Dilworthの定理)らしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/Incubator.cpp

Div2 Easy (250) GreatFairyWar

問題

• N匹の妖精を倒したい。
• 倒されていない妖精は毎秒ダメージを与えてくる。
• 妖精にダメージを1ずつ与えて順番に倒す。
• 受けるダメージの総和を求める。

方針

• 全体の経過秒を加算していく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/GreatFairyWar.cpp

Div2 Medium (550) IncubatorEasy

問題

• div1でN<=10

方針

• 全探索
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_557/IncubatorEasy.cpp

結果

o-- 144.32pt 343rd rating 1319 -> 1378

mediumはいまいち理解してない

Codeforces 143 Div2

03:06

A. Team

問題

• プログラミングコンテストに3人で参加する
• 解けるかどうかが与えられる
• 2人以上が解ける問題の総数を求める

方針

• 足すだけ

B. Magic, Wizardry and Wonders

問題

• カードの枚数と上限値が与えられる
• 右端のカードの数値の差を求めていき、dにできるかどうかを求める

方針

• dが正なら奇数の場所に、負なら偶数の場所に足していく

C. To Add or Not to Add

問題

• 数列が与えられる
• どれかをk回インクリメントできる
• 同じ数が現れる最大の回数と、その最小値を求める

方針

• ループで適当に書いたらTLE
• ソートしてしゃくとり法
• 負の値が混じってたりとか罠がある

結果

oox 1374pt 638th rating 1555 -> 1500

Cがなかなか解けない