hotpepsiの練習帳

SRM 556

00:55

Div1 Easy (250) XorTravelingSalesman

問題

• N個の都市があり、それぞれの都市の値と、都市Aから都市Bへ遷移可能かどうかが与えられる。
• 別の都市へ移ると、現在の値と、移動先の都市の値のXORが現在値となる。
• 最初の都市の値を初期値として、最大値を求める。

方針

• なんか一見典型問題っぽい
• でも同じ場所に戻ってきたときに違う値になる
• 1024までしかないので、[都市数][値]の配列で全探索できそう
• 提出
• Failed System Test
• 問題文をちゃんと読んでなかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_556/XorTravelingSalesman.cpp

Div1 Medium (500) LeftRightDigitsGame2

問題

• N枚のカードが積まれている。
• 上から1枚ずつ取り、左か右に並べてN桁の数を作る。
• 生成可能な数のうち、lowerBound以上で最小の数値を求める。

方針

• 貪欲に置いたらできるのかな
• サンプル合わず
• おにぎりさんのを参考に、kusanoさんのを写経
• 原理はへーそうかという感じだけどこれは書けないな...
• 左から置いたのと右から置いたのがmixされるようになってる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_556/LeftRightDigitsGame2.cpp

結果

x-- 0pt 414th rating 1378 -> 1319 (-59)

XORって色んな問題作れるんだなあと感心した。