hotpepsiの練習帳

SRM 526.5 Div2

03:06

不参加のため練習

Easy (250) MagicStonesStore

問題

• 2n個の石がある。
• 2つの素数の和で表せるかどうかを求める。

方針

• 素数表を作っておく
• 2nから素数を引いて、残りが表にあるか調べる
• https://github.com/firewood/topcoder/blob/master/srm_526/MagicStonesStore.cpp

Medium (500) MagicCandy

問題

• 1-nまでの番号がついたn個のキャンディーがある。
• x^2番目のキャンディーを取り除き、残ったy個に1-yの番号を割り当てなおす。
• 残りの1個になったとき、最初のどの位置だったのかを求める。

方針

• 想定位置がnであると仮定する
• k個あって、k番目を取り除くときだけ、想定位置を-1する
• nが2まで実行する
• https://github.com/firewood/topcoder/blob/master/srm_526/MagicCandy.cpp

Hard (1000) MagicNaming

問題

• 住人が発明した呪文がある。
• 呪文は住人の名前を結合したもののうち、辞書順で最小のものである。
• 最大で何人の住人が含まれるか求める。

方針

• あとで解いた
• 末尾からDP
• ある範囲に名前がa+bという形で含まれていると仮定して、辞書順でb+aより小さければOK
• https://github.com/firewood/topcoder/blob/master/srm_526/MagicNaming.cpp

感想

easyについては、表作らなくてもその場で判定すればよかった。

が、素数生成はコードをコピペしてくればよいので、表あってもよいかなと思う。

nがいくつまでならその場で計算してよいかすぐわからないし。

mediumは本番で出たら解けたかどうかあやしい。図を書いて納得した。

今年の目標

年末にdiv2に落ちてしまったが、今年は一瞬でも黄色になるのを目指す。

div2 mediumまたはdiv1 easyは毎回解くことにする。