hotpepsiの練習帳

SRM 529 Div2

00:07

Easy (250) PairingPawns

問題

• N個のセルにポーンを何個か配置する。
• セルXに2個あるポーンを消して、セルX-1にポーンを1個増やす操作ができる。
• セル0の最大のポーンの数を求める。

方針

• 難読化のため「同じ場所を占有する」みたいな書き方になっている
• 一番うしろの要素から半分にするだけ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_529/PairingPawns.cpp

Medium (500) KingSort

問題

• 王様の名前を辞書順に並べたい。
• 名＋代(ローマ数字) の配列が与えられる。
• 名でソートした上で、代については数値順に並べよ。

方針

• よく読んだら、代は1～50で、特定の文字列
• 代を01～50に変換してソートしてから元に戻す(やっつけ)
• std::set<std::pair<string, int> >に突っ込んだほうがスマート
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_529/KingSort.cpp

Hard (1000) MinskyMysteryDiv2

問題

• あるルールに基づいて、5つの袋からビー玉を足したり引いたりする
• 0から10^12まで処理できるようにせよ

方針

• わからん
• 実験したところ、偶数は半分になり、素数はほぼそのまま、その他の合成数は謎ルール
• つまり最初に割ることのできる数を求めているっぽい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_529/MinskyMysteryDiv2.cpp

結果

oo- 234.12+330.86=564.98pt 163rd 1093 -> 1133

いまいち。

mediumは、小さい数が前置されているのをパースするのは面倒だなあ(たとえばIILとか)と思ったら固定でよかった。ゆっくりしすぎた。

hardは面白い問題。機械式計算機っぽい。