hotpepsiの練習帳

SRM 598

greedy, ソート | 23:15

Div1 Easy (250) BinPacking

問題

• 制限重量が300の容器がいくつかある
• 重さ100以上300以下の品物がいくつか与えられる
• 必要な容器の最小の個数を求める

方針

• 3つ詰め込めるのは100のときだけ
• それ以外は最大2個しか入らない
• 重い順に貪欲に詰め込んでいけばよさそう
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_598/BinPacking.cpp

Div1 Medium (550) FoxAndFencing

問題

• 1直線状の升目があり2人でゲームを行う
• 二つの駒を距離d離して配置する
• それぞれの速度と射程が与えられる
• それぞれが最善手でプレイするときの勝者を求める

方針

• (a)1手目で決まる(b)2手目で決まる(c)それ以外、に場合わけ
• (c)は、速い方が勝者の候補
• Challenge Succeeded
• 自分のターン終了時、相手が1歩動いても相手の射程内にぎりぎり入らない状態でいる必要があるが、相手は最大限離れるので、自分の速度 > (相手の速度×2+射程差) が必要条件
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_598/FoxAndFencing.cpp

Div2 Easy (250) ErasingCharacters

問題

• 誕生日に文字列をもらった
• 長すぎるので、連続する2文字を削除していくことにした
• 最終的に得られる文字列を求める

方針

• 単純に消していく 再帰でもよさそう
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_598/ErasingCharacters.cpp

結果

ox- 211.32pt 212nd/484 rating 1400 -> 1439 (+39)

easyはまあまあ良かった。このmediumが解けないのは痛い。

SRMでも誕生日プレゼントが文字列に。

SRM 597

greedy | 19:57

Div1 Easy (250) LittleElephantAndString

問題

• 同じ長さの文字列AとBがある
• Aの任意の文字を先頭に移動できる
• AとBを等しくするための手数を求める(不可能なら-1)

方針

• ソートして一致しない場合は不可能
• 例としてA=edcba,B=abcdeで考える
• 先頭への移動しかできないので、末尾の文字eより後ろの文字は全て移動する必要がある
• dについて考えると、e以外の文字は全て移動する必要がある
• と考えていくと、末尾から、移動不要なものをe->d->cと一つずつ見つけ、それ以外のものは全て移動すればよい
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_597/LittleElephantAndString.cpp

Div2 Easy (250) LittleElephantAndDouble

問題

• 数値の配列が与えられる
• どれかの要素を2倍にできる
• 全ての要素を等しくできるかどうかを答える

方針

• 任意の2要素が2の累乗倍になっているかどうかを調べる
• 先頭の要素と、それ以外の全ての要素について確認できればよい
• 小さいほうを2倍して一致するかどうか見る
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_597/LittleElephantAndDouble.cpp

結果

o-- +1 198.95 + 50 = 248.95pt 69th/740 rating 1236 -> 1400 (+164)

初の二桁順位。

SRM 596

math | 23:26

Div2 Easy (250) FoxAndSightseeing

問題

• N個の都市の位置が与えられる
• 一つだけ飛ばしてN-1個の都市を順番に観光したい
• 移動距離の最小値を求める

方針

• 全て試す
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/FoxAndSightseeing.cpp

Div2 Medium (500) ColorfulRoad

問題

• RかGかBの升目がある
• R→G→Bの順に進まなければならない
• 移動コストは距離の二乗
• 左端から右端に移動するコストの合計の最小値を求める

方針

• 到達可能な場所についてコストを更新するDP
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/ColorfulRoad.cpp

Div2 Hard (1000) SparseFactorialDiv2

問題

• F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2) とする
• 除数Pが与えられる。(ただしPは素数)
• lo以上hi以下のnについて、Pで割り切れるF(n)の個数を求める

方針

• F(n)はk+1個の項からなる。いくつか列挙して眺めてみた
• Pが素数なので、項同士の掛け算でPの倍数になるケースを考えなくてよい
• a番目の項をn-a^2=xとして、1からxまででPの倍数になるものはx÷P個ある
• aを1ずつ増やしていき全列挙する。aは2乗で増えていくのでせいぜい数十回列挙するだけ
• ただし、それまでに列挙したaと同じものは数えない。同じとは、n-a^2の余りが同じもの(P^a≡P^bのとき、Pの倍数になる位相が同じなので重複する)
• 倍数の個数を求める関数をG(n)とするとG(hi)-G(lo-1)が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/SparseFactorialDiv2.cpp

Div1 Easy (250) IncrementAndDoubling

問題

• 要素数がNの配列が与えられる
• どれかの要素を+1するか、全ての要素を2倍にすることができる
• 初期値を0として、その配列と同じにするまでの最小の手数を求める

方針

• 1を足すより倍にするほうが効率的なので、最小限必要な数だけ足して倍にするはず
• 逆に0に戻すことを考える
• 2で割り切れない場合は1をひく
• その他は2で割る
• 全てゼロになったら終了
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_596/IncrementAndDoubling.cpp

結果

ooo 241.53 + 426.74 + 617.78 = 1286.05pt 8th/1153 rating 1088 -> 1236 (+148)

hardが通ると気持ちがいいですね。

SRM 595

着想 | 01:39

Div1 Easy (250) LittleElephantAndIntervalsDiv1

問題

• 何個かの白いボールが横一列に並んでいる
• ロボットがコマンドに従ってボールを白か黒に塗る
• 一つのコマンドは開始位置と終了位置と色からなる
• 塗り方の総数を求める

方針

• 2^塗った結果の境界の数を求める
• Failed System Test
• 塗ったパターンが残っているかどうかを調べればよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_595/LittleElephantAndIntervalsDiv1.cpp

Div2 Easy (250) LittleElephantAndBallsAgain

問題

• 3色のボールが横一列に並んでいる
• ボールの先頭または末尾を取り除いて、全て同じ色にする
• 最低何手必要か求める

方針

• 開始位置を全て試す
• 連続したボール以外全部消す
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_595/LittleElephantAndBallsAgain.cpp

結果

x-- -1 -25.0pt 395th/410 rating 1227 -> 1088

塗るか塗らないかを選択できるときのパターン数を求めてしまった。

SRM 594

DP | 01:38

Div2 Easy (250) FoxAndClassroom

問題

• 座席がN×Mある
• ひとつずつうしろと右にずれていったとき、全ての座席に座れるかどうかを答える

方針

• GCDが1なら全て通るぽいがいまいち自信ない
• N×Mでループさせて全て通るか調べるのを提出
• Passed System Test
• GCDでよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_594/FoxAndClassroom.cpp

Div2 Medium (500) AstronomicalRecordsEasy

問題

• 惑星系に関する記録がAとBの二つある
• 各要素は太陽からの相対距離である
• AとBは同じ惑星系の記録だが、倍率は異なる可能性がある
• 全ての惑星が記録されているとは限らない
• 少なくともいくつの惑星があるか求める

方針

• A[i]とB[j]が同じであると仮定する
• Aの全要素をB[j]倍して、Bの全要素のA[i]倍して、共通のものが最多の組み合わせを見つける
• setに突っ込んだ要素数が答え
• A[i]とB[j]のGCDをかけたが必要なかった
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_594/AstronomicalRecordsEasy.cpp

Div1 Easy (250) AstronomicalRecords

問題

• 惑星系に関する記録がAとBの二つある
• 各要素は太陽からの距離順に並んでおり、数値が相対的な大きさを表す
• AとBは同じ惑星系の記録だが、倍率は異なる可能性がある
• 全ての惑星が記録されているとは限らない
• 少なくともいくつの惑星があるか求める

方針

• div2medと微妙に違う
• Aの全要素をB[j]倍して、Bの全要素のA[i]倍して、共通のものが最多の組み合わせを見つける
• 共通部分を求める=LCSを求める
• AとBの長さ-LCSの長さが最小のものを見つける
• long longにキャスト
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_594/AstronomicalRecords.cpp

結果

oo- +1-1 244.72+371.76+50-25=641.48pt 28/995th rating 1141 -> 1227 (+86)

vector<int> x(N)でx[N]に代入しているコードがあったので、N=8でchallengeしたが失敗。system testではN=6で落とされていた。

glibcのmalloc(dlmalloc?)の最小割り当てサイズは24バイトで、4(int)×6(要素)のときにぴったりのサイズになり、隣接する管理領域のnextを破壊して死ぬということのようだった。N=10でも別のエラーで死んだ。

div1medは、A[i]とB[j]が同じであると仮定すると、A[i]より前とB[j]より前のLCSと、A[i]より後とB[j]よりあとのLCSに分離できて、ちょっと速くできる。