hotpepsiの練習帳

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に分離できて、ちょっと速くできる。