hotpepsiの練習帳

SRM 567

22:34

Div1 Easy (250) TheSquareRootDilemma

問題

• 整数AとBが与えられる
• (sqrt(A)+sqrt(B))^2が整数になる組み合わせの総数を求める

方針

• AとBをループさせて全探索すれば一応求まる
• AとBをGCD(A,B)で割った商がともにn^2ならOK
• 処理時間は間に合わなさそう
• n^2だけ試せばよいっぽい
• 提出
• Challenge Succeeded
• (修正)
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_567/TheSquareRootDilemma.cpp

Div1 Medium (500) StringGame

問題

• 文字列の集合Sが与えられる
• 最初のプレイヤーがSから文字列をひとつ選び、並び替えてXとする
• 最初のプレイヤーがアルファベットの並び順を選ぶ
• XとS内の全ての文字列を並べ替えた文字列のうち、Xが単独の辞書順最小にできるかどうかを求める

方針

• 使用された文字数をカウントしておく
• 他の文字列より文字数が多い場合は、必ず答えに加える
• 同数のときは、引き続きマッチング
• サンプル合ったので提出
• Challenge Succeeded
• (解き直し)
• 辞書順で大きいものは除外していく
• 評価する文字を決める
• 除外していない全ての文字列のうちで、最大か同数であるとき、最大より文字数が少ないものを除外する
• 全ての文字列が除外できた場合は答えに加える
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_567/StringGame.cpp

結果

xx- 0pt 488th/654 rating 1373 -> 1309 (-64)

easyは77777を7777にして落とした。たぶん部屋が寒かったせい。定数はコピペすべき。

Aでループを回して、Bに関しては答えにsqrt(M/x)を足せばよいという綺麗な問題だった。

mediumは26回ループみたいな感じで書いたらOKだった。シンプルに書けた。