hotpepsiの練習帳

SRM 639

01:12

Div1 Easy (250) AliceGame

問題

• 2人でターン制のゲームをする
• 各ターンの勝者はターン番号×2－1ポイントを得る
• 2人の総ポイントxとyが与えられる
• xポイントを取るための最小のターン数を求める

方針

• 提出できず
• 総和がN^2でない場合は不可能
• 片方が2の場合も不可能
• 2以外の数は作れる
• N*2-1からはじめて、x以上、かつ、偶奇が合うまで足す
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_639/AliceGame.cpp

Div1 Medium (500) BoardFolding

問題

• 升目上に白か黒が書かれた紙がある
• 模様が完全に重なるとき、端から折りたたむことができる
• 折りたたみの状態数を求める(結果的に残った範囲が同じなら重複して数えない)

方針

• 縦方向と横方向の折りたたみ方は独立しているので、最後に掛け算する
• 縦方向の折りたたみについて考える
• 1列単位で同じかどうかのテーブルを作る
• ある列を右端として左にK列折りたためるかと、左端から右にK列折りたためるかのテーブルを作る。ある列Xについて、K=1から左右の両方が同じかどうかで1列ずつ広げていく
• あとはDFS
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_639/BoardFolding.cpp

Div2 Easy (250) ElectronicPetEasy

問題

• 二匹の電子ペットに餌をやる
• 餌やりは時刻stから周期pでt回
• 同時に2匹の餌やりが発生するかどうかを求める

方針

• setに入れた
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_639/ElectronicPetEasy.cpp

Div2 Medium (500) AliceGameEasy

問題

• 2人でターン制のゲームをする
• 各ターンの勝者はターン番号と同じポイントを得る
• 2人の総ポイントxとyが与えられる
• xポイントを取るための最小の勝利ターン数を求める

方針

• 総和がN×(N＋1)÷2でない場合は不可能
• Nから足していく
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_639/AliceGameEasy.cpp

結果

--- -1 -25pts 493rd/539 rating 1522 -> 1368 (-154)

足し算してループするときにTLEすると勘違いしてチャレンジ失敗した。

http://togetter.com/li/751044