ホームに戻る
TopCoder SRM div2 Medium 100問100答
０、はじめに
div2 Medium は div2 Easy より圧倒的に難しいイメージ。
div2 Easy は簡単なループさえ書けば解けるものが多いですが、
Div2 Medium はひと工夫加えないと解けないものが多い。
SRM div2 Medium を 500 から 599 までやってみました。
どんな傾向があるかを探ってみます。
これ以降の記述の利用方法としては、
・問題の意味を簡単に知りたい。
・どんな問題がでるかの傾向を知りたい。
・各問題の解き方の考え方を知りたい。
以上で利用できるかと思います。
１、傾向分析
ジャンルを以下の７ジャンルに分けてみます。
・実装問題（８７問）
・動的計画法（７問）
・数学問題（２問）
・確率、期待値（３問）
・幾何の問題（１問）
・グラフ（３問）
・数え上げ（０問）
実装は総当りや貪欲、シミュレーションなど。
動的計画法はそのまま動的計画法を使うもの。
数学問題は素数や約数を使って解くような問題。
確率、期待値はそのまま確率、期待値を求める問題。
幾何は図形などを使った問題。
グラフはグラフ構造を使った問題。
数え上げは n! や nCr を使うような問題
以上のように決めました。
傾向をみると実装問題が多い。
動的計画法も多少出る傾向にあるので、
動的計画法も覚えておくと良い。
実装問題はやるだけ問題やシュミレーション問題もある。
実行時間を見積もって余裕で回りそうであれば、
問題に書いてある処理をそのまま書けば良い。
SRM529、SRM571、SRM583 などはまさにやるだけ。
実装問題では特に順列、ビット探索の問題が出ている。
順列、ビット探索は制約のNが小さいので、
問題から解法を逆読みすることが可能になる。
順列、ビット探索はできるようにしておいたほうが良い。
２分探索や２部マッチング、ワーシャルフロイドの問題も出ている。
テンプレで解けるので覚えておくと良い。
難しいのは普通にやるだけでは実行時間が足りず、
ひと工夫加えることで実行時間を間に合わせるような問題。
アプローチ法にはある程度パターンがあると思うので、
たくさん引き出しを持っておくと良い。
決め打ちはよく使う方法。
前提が場合によって動く場合には、
固定してその可能性を全探索すれば良い。
2つ以上の要素がありすべて探索すると間に合わない場合、
1つを探索して他を探索無しでいけないか考える。
圧縮探索。すべての場合で探索するのではなく、
特徴のあるポイントのみで探索していく方法。
気づき問題は問題の性質を利用してあるポイントに気づけば、
より問題を簡単に解けるようになる問題。
気づき問題は難しいが気づけば解くのが楽しい問題。
２、実装問題のおすすめ問題
SRM503:
気づき問題。
分け方は最大でも2と分かれば-1と1と2を判定するだけ。
SRM504：
実際に文字列操作をしてはいけない問題。
みなしでやると解ける問題。
SRM510:
片方探索。また、範囲でのポイント探索もある。
SRM512:
決め打ち問題。
決め打ちすることで計算が可能になる場合は本当に多い。
SRM526:
これも決め打ち問題。
コインが縦、横に1つしかないことを利用した良問。
SRM533:
順列探索の練習に最適。SRM554、SRM591も順列。
SRM539:
ビット探索の練習に最適。SRM561、SRM596もビット探索。
SRM541:
幾何の問題。
2倍の工夫はよくあるので覚えておくと良い。
SRM547:
動的計画法の練習に最適。SRM565も良い。
動的計画法とは何かを知るのに良い問題かもしれない。
SRM548:
2分探索の練習に最適。
SRM549:
2部マッチングの問題。
SRM552:
気づき問題。法則に気づけばあとは場合分け。
SRM556:
終点の無いような探索を終わらせる問題。
メモを用いて終わらせる。
SRM562:
数が少ない場合はシュミレート、
数が大きくなったら法則を使う問題。
SRM563:
幅優先探索の練習に最適。
メモを使って終わらせる工夫も必要。
SRM568:
決め打ち。問題として面白い。
SRM575:
動的計画法の交互でやる対決問題は必修。
SRM576
決め打ちと幅優先探索。
SRM580:
圧縮探索。探索ポイントを絞る問題。
SRM584:
グラフの問題。ワーシャルフロイドを用いると簡単。
SRM589:
決め打ちを全探索。
SRM592:
片方のみ探索。順列探索も使う。
SRM594:
決め打ち。組み合わせ固定。
SRM599:
数学問題。因数分解はできるようにしておきたい。
３、全１００問についての簡単なコメント
SRM500
N 人が互いの人に投票を行う。自分にも投票可能。
投票が決まっている人が誰に投票するかのリストがある。
まず先に投票が決まっている人がリスト通りに投票する。
次に、投票が決まっていない人がその時点の最低票の人に投票する。
最高票が何人かいればその人数に対して再度 N 人が投票する。
このときリストの人がすでに落選していれば、
その人は投票が決まっていない人の扱いで投票をすることになる。
これを繰り返して最終的に 1 人が当選した場合に、
もともといた人の中で最も当選確率が高かった人の当選確率は？
無限ループして当選者が確定しない場合は 0.0 を答えとする。
考え方：
問題の読解がいちばんの難関。
サンプルも不親切で何をやっているのかわかりにくい。
普通にシミュレーションを行えばよい。
１、リスト通りに投票する。
２、決まっていない人の投票をする。
３、最高票の人の人数 a を数える。
４、a が 1 なら 1.0 が答え。
５、再投票を繰り返し 1 まで人数が減れば 1/a が答え。
６、再投票を繰り返し人数が 1 まで減らなかったら 0.0 が答え。
確率を答える問題だが確率の要素は少ない。
SRM501
最初の数字は 0 である。
これに paramA/1000.0 をちょうど nA 回足し算し、
paramB/1000.0 をちょうど nB 回掛け算する。
足し算と掛け算の順番を変えて最大値を作れ。
考え方：
足し算を２つに分離する意味は無い。
よって、足し算は固めて考えることができる。
掛け算は最初に 0 に掛けることで自由に回数を消費できる。
したがって、
nA*paramA/1000.0*pow(paramB/1000.0,i) // i は 0 から nB まで
この最大値をとれば良い。
場合分けでもできるがかなりしんどい。
SRM502
宝くじがある。
当選は下何桁かの数字が一致すればよい。
"4" と "7" であれば 0.2 の確率で当たりである。
"4" と "77" であれば 0.11 の確率で当たりである。
"7" と "77" であれば 0.1 の確率で当たりとなる。
当選番号が与えられるので当選確率を求めよ。
考え方：
文字数が少ないものから set に入れていく。
このとき下１桁目からチェックして、
すでに set に入っていればその数値は無効とする。
例えば、"58" がすでに set に入っているのであれば、
"2458" は下１桁目から "8"、"58"、"458" をチェックして、
すでに "58" が set に入っているので "2458" は入れない。
などの判断をしていく。
最終的な確率は pow(0.1,当たり番号の文字数) の和が答え。
SRM503
焼けてないトーストと焼けたトーストを２つに分けたい。
図のように分けるが条件がある。
１、焼けてないトーストが左、焼けたトーストは右
２、トーストは互いに最低１枚以上
地点をいくつか設けて２種のトーストを分けたい。
分ける地点は最低で何個必要か？
また、分けることができない場合は -1 を返せ。
考え方：
数値が最小の焼けたトーストの左に焼けてないトーストが存在しないと不可能。
数値が最大の焼けてないトーストの右に焼けたトーストが存在しないと不可能。
この２つのケースのときに -1 を返す。
１地点で２つに分けられるなら 1 が答え。
それ以外は 2 が答え。
最小の焼けていないトースト１枚を使うパターンと、
最大の焼けているトーストを１枚使うパターンですべて解決できる。
SRM504
ボールの情報とリピート回数が与えられる。
'W' は白いボール、'B' は黒いボール。
"WWB" の 3 であれば "WWBWWBWWB" のボールが１列にある。
先頭から W のボールを取り出した場合は残りの W と B を反転。
先頭から B のボ−ルを取り出した場合は残りの文字列を反転する。
この操作をボールをすべて取り出すまで繰り返す。
黒いボールを取り出した回数はいくつか？
考え方：
シュミレーションすれば正解。
ただし、文字列をそのまま変換してはならない。
文字列の変換は思ったより処理が重いので時間が足らない。
この場合は先頭と末端の位置の情報を覚えておき、
白いボールがでたら W と B を入れ替えて考える。
黒いボールがでたら文字列の向きを逆として考える。
みなして考えるだけで実際に文字列の変換をしてはならない。
みなしでシュミレーションすれば時間は間に合う。
SRM505
PerfectSequences はすべての和とすべての積が等しくなる。
例えば 1,2,3 は 1+2+3 = 1*2*3 で PerfectSequences といえる。
数値がいくつか与えられるので１つだけ数値を自由に変えて、
（ただし０以上の整数でなければならない。）
PerfectSequences にすることができるかを判定せよ。
考え方：
場合分けが面倒な問題。
seq[i] 以外の 和と積を求めて、
和+seq[i] = 積*seq[i] なので、
和/(積-1) が 0 以上の整数であれば良い。
ただし、要素の中に 0 が含まれる場合は例外であるし、
積-1 が 0 のときの対応も必要になる。
要素数が 1 の場合も例外として処理しなければならない。
また、積のオーバーフローも考慮しなければならない。
ただ面倒なだけの問題といえるかもしれない。
SRM506
住んでいる人数の違う村がいくつかある。
村と村は合併すると人数の多い村の名前になる。
合併を繰り返すと最後に１つの村になる。
すべての合併順番を試した場合に名前が残る村の数はいくつか？
ただし、同じ人数の村どうしが合併する場合は２つの村の名前が付く。
人数の等しい0村と1村が合併したとき0村と1村の名前が残る。
考え方：
まずある村を選んでいちばん小さい村から有利に合併をすすめていく。
もし名前が残らなければその村の名前は残らない。
すべての村に対してこの作業を行い名前が残る村の数を数える。
SRM507
6面の箱にステッカーを貼る。
ただし隣り合った面に同じステッカーを貼ってはならない。
ステッカーが文字列で与えられるので6面すべてに貼れるかを判定せよ。
考え方：
２枚以上ある同じ文字列のステッカーが３種類以上なら可能。
２枚ある同じ文字列のステッカーは１枚のみのステッカー２種類で置き換えできる。
ステッカーの種類と数を数えてから以上のように判定。
SRM508
N の長さの列の M 番目にいる。
列は素数で割り切れれば１回の操作でその数で分断できる。
例えば 14 の長さであれば 2 を 7 個 もしくは 7 を 2 個にできる。
また、１回の操作で順番をひとつ前もしくは後ろにシフトできる。
この２つの操作を使って順番を列の１番にしたい。
最低何回の操作が必要か？
考え方：
分断とシフトを交互にやると考えると間にあわない。
すべての分断を先にやってシフトを最後にやると考える。
シフトの結果は現在の列の先頭か次の列の先頭に来れば良い。
分断後にいちばん最後の列にいる場合は次の列は無いので注意。
1000000 以下の数字は素因数分解すると最大でも要素数は 19 しかない。
よって分断のパターンは 2^19 通りで探索できる。
SRM509
ある数字(例えば 123)について、
super(123)=123+12+13+23+1+2+3=177
というような法則で新たな数字を作成するとする。
このとき新たにできた数字を9で割った余りを答えよ。
考え方：
できた数字の桁の数字の和を9で割った余りが答えになる。
例えば 177 であれば (1+7+7)%9 が答えになる。
よって、例えば最初の数字が 123 であれば 1 2 3 がそれぞれ 4 回出現するので、
(1*4+2*4+3*4)%9 が答えになる。
1234 であれば 1 2 3 4 がそれぞれ 8 回出現する。
これは n 桁であれば 2^(n-1) 回出現するという法則があるので、
最大が 50 桁であってもすべての数字の和を求めることができる。
桁の数字の和を9で割って余りを評価する方法を知らないとできない問題。
SRM510
4 と 7 のみでできた数字をラッキーナンバーとする。
下限の数字 a と上限の数字 b がある。
この中から John が連続した jLen 個の数字を選択する。
次に Brus が John の選択した数字のうち連続した bLen 個の数字を選択する。
Brus はできるだけラッキーナンバーをたくさん選びたい。
逆に John はBrus がたくさんラッキーナンバーを選択するのを阻止したい。
互いに最善を尽くした場合、ラッキーナンバーはいくつ選ばれるか？
考え方：
John の選択を全探索し Brus の選択を最善で行う。
John の選択に対して Brus の選択でのラッキーナンバーが最小のものが答え。
ただし範囲を全探索をすると間に合わない。
上下限の a b や47 や 77 の前後などのポイントのみを使って探索すれば間に合う。
SRM511
ウサギとネコの２種類がいる。
すべてのウサギは背の高さが異なる。
すべてのネコも背の高さが異なる。
すべての動物にあなたより背の高い同じ同種の動物は何匹いますか？と聞きました。
ウサギとネコのありえる組み合わせの数をすべて答えよ。
ただし、動物の答えが嘘で、ありえない場合には 0 を答えとする。
考え方：
ウサギとネコが共に1匹いれば必ず 0 と答える動物が 2 匹いるはずである。
続いて共に 2 匹ずついれば 1 と答える動物が 2 匹いるはずである。
よって、
ウサギ: 0 1 2 3 4 5
ネコ: 0 1 2
などはありうるパターンである。
このとき 0 1 2 と答えた動物の組み合わせ 2^3 通りと、
3 4 5 はどちらかの動物なので 2 通りがあり 2^3*2 が答えである。
すなわち 0 から各種の2匹ではじまりどちらかの1匹になって収束する。
これ以外はありえないので 0 を返す。
SRM512
レストランでは毎日価格の違う複数のメニューが選べる。
ただし、このレストランは同じ週であれば同じ順番のメニューを選ばなければならない。
１週間は７日である。
例えば、初日に１番目のメニューを選んだら、
７日後も１４日後も２１日後も以降ずっと１番目のメニューを選ばなければならない。
レストランには初日から毎日通うが所持金が無くなれば通えない。
所持金が決まっているので最大何日目まで通えるかを答えよ。
考え方：
１日目まで可能か？２日目まで可能か？と日数を１日ずつ延ばしていく。
日数を決め打ちすれば週ごとに何番目のメニューを選べば得かが選択できる。
SRM513
点と板の長さが与えられる。
この点を通る条件で端が整数座標であるように板を移動できる。
上からいくつかのボールが落ちてくる。
板の配置方法は何通りか？
考え方：
１枚ごとの板で分けて考える。全探索が可能なのでやるだけ。
SRM514
(1,n)で８方向に移動できる変則ナイトがある。
（通常のチェスのナイトは(1,2)で移動する。）
原点から移動して指定された位置につけるか判定せよ。
考え方：
n がどの値でも２回の移動で上下左右に２マス動ける。
よって、偶数、奇数のマスに移動できるかどうかだけ考えれば良い。
n が奇数であれば（遇、遇）、（奇、奇）のマスに移動できる。
n が偶数であればすべてのマスに移動できる。
SRM515
長針と短針の位置がわかっている丸い時計がある。
しかし、どこが上かはわからない。考えられるいちばん早い時間は？
考え方：
時間で全探索。
時間を決めてその時間で短針が正しい位置にあればそれが答え。
SRM516
0と1からなる文字列がある。
これを0と1からなるキーでXORをとって0と1からなる暗号文を作る。
暗号化前の文字列と暗号化された文字列が与えられる。
暗号化された文字列は暗号化前の文字列のいずれかを暗号化したものである。
キーの候補は何通り考えられるか？
考え方：
考えられるキーを全部試すと間に合わない。
すべての暗号化前と暗号化後の文字列を組み合わせてキーの候補を作成する。
キーの候補ですべての暗号化が可能であれば１カウントしていく。
SRM517
数字Nが与えられる。
このNをN=A*Bが成り立つようにAとBに分解していく。
どのように分解してもtargetにたどり着くことができるかどうか判定せよ。
例えば、N=16、target=4のとき、
N=2*8、N=4*4の２通りに分解できる。N=4*4は条件をクリアしている。
N=2*8は8を2*4に分解できるのでこれも条件をクリアする。
よってどのように分解していってもtargetの4にたどり着く。
例えば、N=12、target=6のとき、
N=2*6は条件をクリアするがN=3*4は条件をクリアしない。
よって、これはすべての場合でtargetの4にたどり着かない。
考え方：
問題の意味がわかりづらい。
分解してすべてのパターンにたどり着けるか調べる。
再帰を使って全探索しても間に合う。
SRM518
与えられた文字列から部分文字列を抜き出す。
辞書順で最大のものを答えよ。
考え方：
第１にできるだけ大きなアルファベットを優先的に用いて、
第２にできるだけ文字列を長くすれば良い。
SRM519
２次元座標上の地点Aから地点Bにたどり着きたい。
途中でテレポート地点が３つ与えられ、
この地点はテレポートで与えられた距離の扱いで移動することができる。
地点Aから地点Bへの最短の距離を求めよ。
考え方：
３つのテレポート地点を使うか使わないかの 2^3 の場合分けに加え、
テレポートの向きによる 2^3 の場合分けで距離を求め最短のものを選ぶ。
ダイクストラ法を使っても良いが使わなくても解ける。
SRM520
３問の問題と配点が与えられる。
それぞれの問題を解いた時間が与えられる。
それぞれ７５分以内に解けていなければ０点である。
７５分以内であれば解いた時間によってそれぞれ点数が計算される。
最後に luck が与えられる。
この luck のぶんだけ各問題だけ時間を減らせる。
luck だけ自由に時間を減らしたとき、
最大の得ることができる点数を求めよ。
考え方：
luck は得点計算表からわかるように、
より高い点数で使ったほうが有利であることがわかる。
ただし、７５分以内にならなければ損をする。
単純に大きいものから減らすだけだとこの問題は解けない。
よって、３問のうちどれを使うかを全探索する。
使う問題を決めたら大きい点数のものから時間を減らす。
SRM521
括弧が ( ) で正確に組になるように ( か ) を追加する。
最小でいくつ追加する必要があるか？
例えば、")(()(" の場合、"()(())()" と３つ追加すれば成立する。
考え方：
() を消せるだけ消していく。
すると ")))((((" のような形で残るはず。
この数が答え。
SRM522
一列のAとBの書かれたマスがある。
AさんとBさんがこのマスの連続した区間にコインを置く。
コインはいくつでも置けるが最後の１マスには置けない。
最後に残ったマスが自分の文字であれば勝ちである。
どちらが勝つかを判定せよ？
考え方：
両端のどちらかにAがあればAが勝つ。
両端が共にBであればBが勝つ。
この手の問題は全探索する場合もあるが、
法則を見つけて簡単に解ける場合も多い。
SRM523
初項a、公比bの等差数列、初項c、公比dの等比数列が与えられる。
２つの数列で計算される数値は与えられた区間内にいくつあるか？
考え方：
等差数列と等比数列で重複する値を２重で数えないようにしたい。
まず d = 1 のときだけ別に考える。
このとき等比数列は１つの値なので簡単。
d が 1 でないときは等比数列の値が意外に少ないことを利用する。
c = 1、d = 2 のときですら値は36個程度しかない。
よって、まず区間の等差数列の数を割り算で求め、
等比数列は等差数列と重ならないときのみ数を加算すれば良い。
等比数列の値だけをループ探索する。
等差数列の値をループで探索してしまうと時間が足らない。
SRM524
数字Nが与えられる。
できるだけ少ない数の非素数の和に書き直したい、
いくつの要素の和になるか？
例えば17は素数である。17=9+8とでき、9と8は2つの非素数である。よって、答えは2になる。
考え方：
1は非素数であり、2以外の偶数は非素数であるから。
素数であれば、必ず(N-1)+1の和の形にできて答えは2になる。
ただし、N=3のとき3=1+1+1なので答えは3になる。
N=3なら答えは3。Nが素数なら答えは2。それ以外は答えは1になる。
SRM525
コインの乗った盤面が与えられる。
盤は上下左右を選んで１つスライドさせてコインを落とすことができる。
指定されたコインの数を残したいとき、スライドの最低回数はいくつか？
ただし、不可能な場合は-1を答えとする。
考え方：
すべての四角い領域内のコインを数える操作をすればよい。
スライド回数の計算は少ない端の幅に2を掛けて、大きい幅を足せば良い。
例えば、左の4列と右の5列、上の1行と下の3行を落とすなら、
最低のスライド回数は ((4*2)+5)+((1*2)+3)と計算できる。
普通に全探索で間に合う。
SRM526
コインの乗った盤面が与えられる。
コインは同じ列、行に複数存在しない。
コインは１つの操作で上下左右に移動できる。
最小の操作で１列に並べたい。その回数はいくつか？
考え方：
全ての座標をスタートして縦と横に並べるすべての場合を試せば良い。
1列もしくは1行に複数コインが無いという制約があるので、
例えば左から右に並べると決めたら、より左のコインから使って並べていくのが最善。
SRM527
N個のノードをエッジでつなぐ。回路は無い。
このときノードにつないだエッジの数で得点が異なる。
自由にエッジをつなぐとき最高得点はいくつか？
考え方：
N個のノードがあるのであればエッジの接点は2*N個である。
N個のノードにエッジをどのように振り分けるかを動的計画法で求める。
dp[現在のノード][使える残りのエッジの端の数]
SRM528
異なる長さのうなぎが何匹かいる。
切ることのできる最大の回数が与えられるので、
うなぎを切って長さが10のうなぎがいくつできるか求めよ。
考え方：
例えば長さ20のうなぎは1回で2つの10ができる。
よって、10の倍数のうなぎを先に切っていけば良い。
SRM529
名前とローマ数字が与えられる。
名前を辞書順で、名前が同じならローマ数字でソートせよ。
考え方：
面倒くさいがやるしかない。
SRM530
カット後のケーキとカット型が与えられる。
カット型を使ってカット後のケーキができるか判定せよ。
考え方：
まず全くカットされていない状態を用意する。
カット後を見て型を使ってすべてのカット位置がカットできるならカットする。
この操作をすべての箇所で行ってできた形がカット後と等しければＯＫ。
SRM531
N個の曲があり、M曲の間は同じ曲をかけてはいけない。
すべての曲を使ってP曲の再生リストを作れ。
考え方：
動的計画法。
dp[現在の曲][今まで使った曲数]
もしいままで使ったことのない曲を使う場合、
使ったことの無い曲は N-j 曲でM曲の制限は無いので、
dp[i][j+1] += dp[i-1][j]*(N-j)
となる。
もしいままで使ったことのある曲を使う場合、
使ったことのある曲は j 曲でそのうちM曲は使えないので、
使える曲は j-M 曲であるから j>=M のとき、
dp[i][j] += dp[i-1][j]*(j-M)
となる。
SRM532
数字の列をつなげて連続した数字の和を最大にせよ。
ただし . は数字では無いので . で数字の列は切れる。
考え方：
. を含まない列があればすべて結合する。
結合したものにそれ以外を左と右につけるパターンを総当たりする。
..999999999.. などのパターンも考えるのを忘れずに。
SRM533
星がいくつか並んでいる。
星を破壊すると両側の星の重さの積の点数が得られる。
点数を最大化せよ。
考え方：
星の数が少ないので順列で総当たりできる。
SRM534
o を右に１つ動かすか o を o を右に２つ飛び越す作業ができる。
最右にくれば o は消える。最初に動かせなくなったほうが負け。
どちらが勝つか？
考え方：
２つの移動方法はともに奇数なので、
すべての o から右のマスの数を数えて和を求める。
マスの数の総和の偶奇で勝敗を判定できる。
SRM535
2つの数、A と B の最大公約数 G と最小公倍数 L が与えられる。
A+Bの最小値を求めよ。無い場合は -1 を返せ。
考え方：
A=x*G、B=y*G とすると、L=x*y*G で x と y は素である。
L の最大値は 10^12 であり、G の最小値は 1 であるから、
x*y の x について 1 から 10^6 まで探索すれば良い。
L=x*y*G であり x と y が互いに素であるもののうち、
x*G+y*G が最小になるものを求めれば良い。
SRM536
サイコロの面は 1 から M の連続した数字である。
この M の異なるサイコロがいくつかある。
これらのサイコロをいくつか選んで N 回投げる。
出た目の結果が記録される。
それぞれのサイコロの目であり得る最大の目の和を求めよ。
考え方：
結果を小さい目からソートし、その順番で数が最大のものがあれば更新する。
最終的な結果の和を求める。
SRM537
ある国では A と B の通貨があり、その通貨ですべてのものが買える。
A と B を新たに X と Y の通貨に切り替えたい。
ただし、A と B のころのものがすべて買えないといけない。
A と B と X が与えられるので Y は何通りか答えよ。
無限にある場合は -1 を答えとする。
考え方：
A と B が X で割り切れれば Y は無限にある。
そうでなければ Y を総当たりし、
A=a*Y+b*X、B=c*Y+d*X が成り立つ X を数える。
SRM538
座標を1つ移動することを1ステップとする。
原点をスタートし与えられた地点を自由な順番ですべて辿るとき、
総ステップ数が奇数、偶数かが指定されるので、
その移動が可能かどうかを判定せよ。
考え方：
ステップ数の偶奇は辿った最終地点のみで決定する。
よって、すべての最終地点についてステップ数の偶奇を調べ、
１つでも有効な地点があれば可能といえる。
SRM539
最低から最高まで石を入れることができる箱がある。
各箱に石を入れるか入れないかを決め可能な数の石を入れる。
石の総数が9000を超える数はいくつあるか？
考え方：
どの箱に入れるかは箱が少ないので総当たりできる。
最小と最大の場合を得ることができるので、
どの箱に入れるかごとで結果を結合する必要がある。
このとき1つ1つ値を覚えることはできない。
よって、複数の上限と下限を管理していく方法を使う。
SRM540
ある足し算と引き算からなる計算式が与えられる。
計算式中には正の整数しか用いられない。
この計算式の途中の計算結果を残して記録していたが、
元の計算式の数字のみが消されてしまった。
足し引きの符号と途中の計算結果から復元できる元の計算式は何通りか？
無限にある場合は -1 を答えとする。
考え方：
最初の値の最小値を 1 最大値を十分大きな値とし更新していく。
SRM541
蟻の初期位置と移動方向が与えられる。
それぞれの蟻が指定された方向に均等なスピードで進むとき、
蟻同士がぶつかると消滅する。残る蟻は何匹か？
考え方：
すれ違いへの対応が必要。
よって最初にすべての座標を２倍しておく。
移動はシュミレーションしても間に合う。
SRM542
X*Yのフィールドに地点 A B C が存在する。
各地点の X Y 座標はそれぞれ異なる。
この３地点をマンハッタン距離で１週する距離を時間とすると、
１週するのに必要な最低時間と最大時間が与えられる。
時間の範囲で１週できる A B C の配置方法は何通りか求めよ。
考え方：
３点が x*y の四角形にちょうど収まると考える。
すると１週する時間は ((x-1)+(y-1))*2 とできる。
時間が指定の範囲内に収まるかをチェックし、
x*y 内への3点の配置と x*y を X*Y 内に配置するパターンを考慮し加算していく。
SRM543
数値 L から R までの XOR をとるとき最終値はいくつか？
考え方：
L から R までの XOR 値は
1 から L-1 までの XOR と 1 から R までの XOR で XOR をとれば求められる。
1 から x までの XOR は周期性があり法則で求められる。
XOR の法則について知らないとできない問題。
SRM544
必要な板の長さと数が与えられる。
指定された長さの板が無数に与えられる。
与えられた板はカットにコストが 1 かかる。
接着にはコストを要しない。
必要な板を用意するために必要な最小のコストを求めよ。
考え方：
切らなくていい部分は考えずに端数のみ考えれば良い。
切る板を端数に合わせて切っていけば良いが、
切る板と端数が一致する部分は切らなくて良い。
最小公倍数を求めて一致する部分を計算できる。
SRM545
ある文字列があるとき i 番目 j 番目の文字について、
i s[j] が成り立つとき 1 ポイントと数えると、
与えられた文字列の辞書順で次の n 文字で x ポイント以上の文字列を求めよ。
考え方：
先頭から文字を確定していく。
ある文字を試しそれ以降を最もポイントが高くなるように文字を設定する。
これが条件を満たすとき試した文字は確定して良いと言える。
確定した場合は次の文字に進む。
SRM546
2つの四角形の対角の２点の座標がそれぞれ与えられる。
2つの四角形が少しでも面と面が重なるのか、
辺と辺が接するのか、点と点で接するのか、全く接しないかを判定する。
考え方：
場合分けしてやるしかない。
SRM547
高さが変更できるポールが1直線に均等な間隔 w で置かれている。
ポールは最大の高さが与えられており、最小はどれも 1 である。
すべてのポールの高さはどれも範囲内で自由に調整できるとして、
端のポールから端のポールまでてっぺんにたるまず紐を張るとき、
紐の長さを最大にできるときその長さはいくつか？
考え方：
動的計画法。
まず高さは1つのポールにつき 1 か最大しかない。
左から 1 を選んだ場合と最大を選んだ場合を記録していく。
ひとつ前の 1 と最大からそれぞれ現在の 1 と最大につないだ場合に、
最大になるケースを更新していく。
最終的に右端の結果で 1 の場合と最大の場合で長いほうを答えとする。
SRM548
一列に木が並んでいて高さが与えられる。
魔法を使うと長さ d 以内で長さを長くしたり短くできる。
木の高さを左から右に昇順にしたい。
必要な d の値の最小値を求めよ。
考え方：
すべての d を試せば良いが木の高さが最大 1000000000 で間に合わない。
よって２分探索を使う。
SRM549
２つの円錐を組み合わせて帽子を作る。
上の円錐と下の円錐のグループが与えられる。
下の円錐がちょうど帽子のひさしの部分になる。
下の円錐が上の円錐より尖っていれば帽子はできない。
下の円錐の底面の直径が上の円錐より小さくてもできないだろう。
このような条件のもと与えられた部品でできるだけたくさん帽子を作る。
最大いくつの帽子ができるか？
考え方：
2部マッチングの問題。
2部マッチングは可能な組み合わせをグラフで作成しておくことで、
組み合わせの最大数を求めることができる。
SRM550
四角の部屋にいて最初は右を向いている。
まっすぐ歩いて壁に当たるかすでに歩いた位置に当たると左に向きを変える.
向きを変えるまでに歩いた歩数が与えられるので、
部屋の大きさはいくつと考えられるかその面積を返せ。
そのような部屋があり得ない場合は -1 を答えとする。
考え方：
実際にシュミレーションしてやってみるしかない。
工夫次第で実装を簡単にしたりバグを減らせそうな問題。
SRM551
文字列が与えられる。
1回の操作で隣り合った文字を入れ替えることができる。
操作回数の最大値が与えられるので同じ文字が連続する最長部分を作れ。
その長さはいくつか？
考え方：
すべての文字について同じ文字を近づける試みをする。
近づける順番は近い方から近づけていけば良い.
SRM552
３種類の色のついた玉がある。
図のように玉を使って同じ色が隣り合わないように高さ N の三角形を作る。
各色の玉の数と N が与えられるので、
作ることができる三角形の数を求めよ。
考え方：
N を3で割って1余る場合とそれ以外で分けて考える。
SRM553
スタックがある。
配列の数字を左からスタックに入れていくが、
配列の数字が 0 のときだけ特殊なことをする。
数字が 0 のときはスタックの上２つを加算して1つにする。
この操作を最後まで行ったときスタックの最上の数値を得る。
配列の途中にひとつだけ -1 がある。
この数字を０以上の整数に自由に変更して目的の値を得たい。
どのような数値を入れれば良いか？
可能な最小の値を返せ。不可能なら -1 を返す。
考え方：
まず -1 を 0 にしてシュミレーションする。
これが目的の値になれば 0 とする。
次に -1 が計算した結果スタックの最上の値に影響するか調べる。
影響しないのであれば最小の値を返す。
影響するのであれば目的の値を計算する。
最小値を用いても目的地をオーバーするときは不可能なので -1 が答え。
SRM554
数本のブロックの高さが与えられる。
すべてのブロックを一直線に並べるとき、
どれが倒れても他のブロックに当たらないようにしたい。
端から端までの距離が最短になる並べ方は？
複数ある場合は辞書順で最短を返せ。
考え方：
本数が少ないので順列で総当たりができる。
辞書順で検索し、最短になった時点で数値を記録するか、
先に最短値を求めてから、辞書順探索し最短値になったら答えを返す。
SRM555
1 と 0 からなる文字列がある。
これを 5 の累乗を2進数表示した文字列に分割したい。
最も少ない文字列に分割にする場合、いくつに分割できるか？
考え方：
動的計画法。
上のビットから見ていき最小になる値を覚えていく。
SRM556
スタート地点から別地点への移動の可否が与えられる。
各地点は数値を持っており現在の数値と XOR をとる。
任意の移動によって得られる最も大きな値はいくつか？
考え方：
移動可能なすべての位置への移動を試す。
いちどその地点でその値になったのであれば探索を止める。
可能な最大の数値を返す。
SSR557
N人の少女がいる。
それぞれの少女は互いに守るべき少女を持っている。
守るべき少女は自分自身であるかもしれない。
少女は魔法使いになると守るべき少女を守ることができる。
また守られた少女も守るべき少女を守る。
守られている少女は魔法使いになることはできない。
魔法使いでありかつ守られていない少女を最大にしたいとき、
その数はいくつか？
考え方：
順番は関係ないので誰を魔法使いにするかを全探索。
N は最大10なので十分間に合う。
SRM558
壁にスタンプを押す。
色は赤か緑か青の３色である。
長さ L のスタンプを1本用意できる。
このとき L*stampCost だけのコストが必要。
塗っていない場所の上もしくは同じ色の上にスタンプを押せる。
このとき1回につき pushCost がかかる。
コストを最小にするときそのコストはいくらか？
考え方:
動的計画法。
まず L はすべての場合を総当たりする。
左から順番に更新し右端で押すか押さないかでコストを最小化する。
SRM559
動き方が変則のナイトがある。
置くと１手で移動できる次のマスがちょうどk個である
盤面上のマスは盤面上にいくつか？
考え方：
kの値で場合分けするしかない。
探索すると間に合わないのでアウト。
SRM560
携帯電話がある。
ボタンは1回押すと1つめの文字、
2回押すと2つ目の文字というような入力形式である。
例えば、1つ目の文字が a で2つ目の文字が b であるとき、
a は1回ボタンを押せば打てるが、 b は2回押さないと打てない。
打つ文字に対する回数のリストと、
ボタンの数と割り当てられる文字数が与えられる。
自由にボタンに文字を割り当てられるとき、
すべての文字を打つために必要なボタンを押す回数はいくつか？
考え方：
たくさん押す必要のある文字を押す回数の少ないボタンに割り当てるだけ。
SRM561
中サイズと大サイズの異なる色のボールがある。
これを複数のグループに必要な数だけ用意したい。
ただしグループのボールは同じ色同じ大きさでないといけない。
色はコスト1で自由に色を塗り替えることができる。
最小のコストを求めよ。不可能な場合は -1 を返す。
考え方：
ボールの数が多い色をよりたくさん必要とするグループに分ければ良い。
問題は大と中のボールの振り分けかたであるが、
グループの数が少ないので大と中の振り分けは総当たりしてしまう。
SRM562
指定されたドットの図柄のスタンプをT回押す。
このとき1回ごとに右と下に1ドットずつずらす。
T回押し終わったときに総ドット数はいくつか？
考え方：
T回までシュミレートすると実行時間が足りなくなる。
100回くらいまではシュミレートし、
101回以降は1回増えるごとに増えるドット数が固定されてくるので、
100回の結果にそれ以降の増加ぶんを加算する方法をとる。
SRM563
板の上の2枚のコインを上下左右に動かす。
# は壁でコインは壁側には移動できない。
1セルずつ好きなように上下左右を選んで動かすとき、
盤面上のコインを残り1つになるようにしたい。
動かす回数の最小値はいくつか？不可能な場合は -1 を返す。
考え方：
幅優先探索で実際にやってみる。
SRM564
赤、青、緑色のボールがそれぞれ何個かある。
左からボールを赤、青、緑色で１個ずつ並べていく。
色のボールがなくなっても残りのボールで続ける。
左から i 番目のボールは何色か？
考え方：
3色でいつまでつづけられるか？
残り2色でいつまでつづけられるか？
残り1色でいつまでつづけられるか？
求める順番がどの区間であるかを考えればすぐにわかる。
SRM565
モンスターのいる谷を通る。
コイン1枚か2枚でモンスターは仲間になる。
自分の仲間のモンスターの強さの合計が、
いま通るモンスターの強さを上回ると素通りできる。
できるだけコインを使わず谷を通り抜けたい。
最小のコインはいくらか？
考え方：
動的計画法。
dp[i匹目のモンスター][コインの数]=合計の強さ
コインの数ごとに強さを覚えて更新すれば良い。
SRM566
円になった赤と青のペンギンがいる。
同じ色のペンギンを交差せずに線で繋ぐとき、
最大いくつのペアができるか？
考え方：
隣り合う同じ色のペンギンを消していく。
すべて消えればすべてのペアができる。
すべて消えなければ1つのペアが残る。
SRM567
Aは1からNまでの数、Bは1からMまでの数である。
(sqrt(A)+sqrt(B))^2が整数であるAとBの組み合わせはいくつか？
考え方：
Aの1からNは総当たりする。
するとA=(x^2)*yであることがわかるので、
B=(i^2)*yで探索し成り立つ i の数を数える。
SRM568
赤、青、緑のボールの入った箱がいくつかある。
ボールを移動してすべての箱のボールを単色にしたい。
ボールの移動回数は最小でいくつか？
考え方：
赤、青、緑を入れる箱を1つずつ決める。
この場合は最大50P3通りである。
決めた3つの箱の中身はボールを他の箱に移して単色にする。
決めた3つ以外の箱は色の多いボールを残せば良い。
出したボールはすべて決めた3つの箱に移す。
SRM569
ある装置はビットのプレートを2枚入れると、
各ビットについて AND か OR か XOR の演算をする。
すべてのプレートを使って、
どのビットがどの演算かを当てることができるか？
考え方：
1 1 があれば XOR を判別できる。
0 1 があれば AND と OR を判別できる。
よって、1 1 0 が各ビットに存在すれば良い。
SRM570
まずaの配列をT回繰り返す。
ロボットはa[i]だけ歩いたあとa[i]回だけ右に90度回転する。
全部の移動を終えたときスタートからの移動マンハッタン距離は？
考え方：
シュミレーションして間に合う。
SRM571
曲数が与えられるので、
名前でソートして最大50曲まで表示せよ。
考え方：
名前でソートして50曲まで表示する。
なんのひっかけも無い。
SRM572
最初の文字列と目的の文字列がある。
文字をひとつ進めるか戻すかでコストが決められている。
最初の文字列を目的の文字列にしたいが、
途中で文字列中に同じ文字が2つ以上あってはならない。
コストを求めよ。不可能なら -1 を返せ。
考え方：
コストを求めるのは簡単である。
難しいのは可能か不可能かの判定。
上りと下りがぶつからないか？
上りと上りもしくは下りと下りで、
追い越しが発生しないか？を判別する。
SRM573
3人でチームを作る。
配列の最初の3つは自分のチームの強さである。
3つの強さのうち強さの大きい2つが実際の強さになる。
残りの人で自由にチームを作るとき、
自分のチームの強さの順位が最も低くなるのは何位か？
考え方：
残りのチームは最も大きい強さと、
より小さい強さで最も大きい強さと足すと自分のチームより強くなる人で作る。
この方法で作ったチームが自分のチームより強いチームである。
SRM574
数字からなる文字列がある。
反転と10で割る操作が選べる。
目的の数字にするための最小の操作数は？
できない場合は -1 を返す。
考え方：
基本的には最大の手順でも次の手順でできる。
下を１０で割って消して反転し１０で割って消し反転で戻す。
場合分けしてどの操作が必要なのかを考える。
SRM575
数字があり2人のプレーヤーが1とその数字を除く約数で交互に引き算する。
引き算できなくなったほうが負けのとき、勝敗を判定せよ。
両者は最善を尽くすものとする。
考え方：
動的計画法。
素数が与えられたら負けなので、
負けから勝ち負け表を作成する。
SRM576
Xと.からなるフィールドが与えられる。
最下段はすべてXで最下段がスタートである。
横にはXを通って移動できるが、
縦にははしごを使って移動する。
はしごの長さが1であればひとつ上のもしくは下のXに移動できる。
長さが2であれば2つ以下の上のもしくは下のXに移動できる。
はしごの長さは最初に1回だけ決定できる。
Xのある地点にゴールがある。
最も短いはしごを使ってゴールできるとき、はしごの長さは？
考え方：
はしごの長さを1から増やしてシュミレーションする。
初めてゴールに着くことができたとき、その長さが答え。
SRM577
N人のコンテストの参加者がいる。
参加者は最大20人のグループに分ける。
Nが20で割り切れればN/20個のグループができる。
割り切れなければN/20+1のグループができる。
N人のレートが与えられ最初が自分である。
レートは降順にソートされ、
先頭から順にまず1人目をグループに割り振る。
2人目は先頭から順にランダムで各部屋に人を割り振る。
3人目以降も同じ作業を繰り返す。
自分が最もレートの高い人と同じグループになる確率は？
考え方：
自分が部屋に1人目として割り振られたとき、
自分が最高レートであれば確率は1.0であり、
自分が最高レートで無ければ確率は0.0である。
2人目以降であればグループの数分の1になる。
SRM578
vと.からなるフィールドが与えられる。
vはアヒルかガチョウであるがどちらかはわからない。
わかっていることは少なくともガチョウは1匹はいる。
また、ガチョウとガチョウはマンハッタン距離がdist以内であれば、
ともにガチョウであると言える。
ガチョウとアヒルの配置のパターンは何通りか？
考え方：
すべてのフィールドでマンハッタン距離がdist以内のグループを作る。
(グループ数^2)-1が答え。
SRM579
与えられたいくつかの文字列を順に入力する必要がある。
文字列をキータイプしエンタータイプで登録される。
ただし、この際にアンドゥリストが作成され、
2回のキータイプで過去に出現した文字列に戻ることができる。
過去に出現した文字列は空白も含む。
目的の文字列リストをすべて登録するのに、
必要な最小タイプ数はいくつか？
考え方：
シュミレーションする。
アンドゥを使う場合はアンドゥしたほうがいいのか、
タイプしたほうが早いのかを考えれば良い。
SRM580
異なる長さのうなぎが上流から同じ速さで流れてくる。
うさぎが一列に並んだ区間に存在するうなぎをキャッチする。
キャッチは2回まで行える。
キャッチできる最大のうなぎの数は何匹か？
考え方：
うなぎは長いのですべての時間でキャッチを試せない。
各うなぎの先頭と末尾だけキャッチする。
うなぎが最大50匹でも最大100回のキャッチで間に合う。
100C2を総当たりすれば良い。
SRM581
一列に並んだ空間がある。
Xはコンテナが置いてあり、-は何も置いていない。
カメラがコンテナを監視している。
1台のカメラはLの範囲を監視しいくつコンテナがあったかを左からreportsで報告する。
カメラは台数はわかるがどの位置にあるかはわからない。
必ず監視されていると言える区間を+、可能性があれば?、確実に無ければ-として返せ。
考え方：
左詰めでカメラを配置する可能性を考える。
次に右詰めでカメラを配置する可能性を考える。
このとき両方で監視されている部分が+、
両方で監視されていないのが-、それ以外が?になる。
SRM582
強さの異なる魔法少女がN人いる。
強さの異なる敵とその数が与えられる。
魔法少女の強さが敵の強さ以上であれば勝てる。
1対1の戦いで魔法少女は疲労が1増える。
疲労が最高になる魔法少女の疲労を最小化せよ。
考え方：
疲労を最小化するには全員が同じ数だけ戦えば良い。
また、強い敵ほど強い魔法少女に戦わせる。
よって、戦闘数を1から増やしてすべてに勝てるか試していく。
すべてに勝てるとき疲労の最小値となる。
SRM583
人民コードのフォーマットが与えられるので、
コードが正しいか間違いかを判定せよ。
考え方：
やるしかない。
SRM584
ある国にはN人の市民がいる。
市民と市民には友人関係が与えられる。
友人同士の所持金の差はちょうどD円であるという。
この国で最も金持ちである人と金持ちで無い人の差額はいくらか？
考え方：
市民の関係でグラフを作る。
友人関係であれば距離を1にして、
友人関係で無ければ距離を十分大きな値にする。
それぞれの市民の最短距離をワーシャル。フロイドなどで求め。
十分に大きな値が1つでもあれば-1を返す。
そうでなければ最大距離*Dが答え。
SRM585
図のような完全2分木の高さが与えられる。
この木を分岐しないまっすぐな線で埋めたい。
点も線とみなす。
必要な最小の線の数はいくつか？
考え方：
高さが奇数と偶数で増え方が違う。
増え方の法則を見つける。
SRM586
図のような線グラフが与えられる。
yの値がいくつか与えられるので、
そのyに対するグラフとの交点の数を求めよ。
無数にあれば -1 を答えとする。
考え方：
シュミレーション。
yの値とグラフの線が重なれば -1。
SRM587
無限に続く階段を昇る。
このとき1、2、3、4、・・・、N段ずつ昇っていく。
毎回その数を昇るか昇らないかは選択できる。
途中に壊れた部分が1つありそこに止まることはできない。
最高で何段昇ることができるか？
考え方：
すべての昇り方を使うとき壊れた部分を通るか調べる。
通らないのであればすべての昇り方を使う。
通るのであれば最初の1を選択せず、すべての場合-1が答え。
SRM588
歌う歌の時間と曲のトーンが与えられる。
曲を自由に並び変えて制限時間T内に多くの歌を歌いたい。
ただし、トーンの違う曲はそのトーンの差の時間だけ休む必要がある。
最大何曲歌うことができるか？
考え方：
トーンで曲をソートする。
あとは歌うか歌わないかで全探索する。
SRM589
円の状態でギアが組まれている。
Lは左周り、Rは右周りである。
右回りと右周りがかみ合っていると回らない。
左周りと左周りも同じく。
いくつかのギアを外してすべてのギアが回るようにしたい。
最小でいくつのギアを外す必要があるか？
考え方：
外す必要が無ければ0が答え。
でなければ外すギアを1つ決めてから、
残りのギアが動くようにギアを外していく。
最初に外すギアを総当たりする。
SRM590
碁盤がある。
.が空白、xが自分でoが相手の石である。
1手で取れるo石の最大数はいくつか？
ルールは碁に基づく。
考え方：
1つのo石について連結するo石のグループを調べる。
そのグループについて隣接する.が1つであれば取れる。
取れる石の最大値が答え。
SRM591
単語の変換表を作る。
例えばA->CやG->Dなどである。
変換は重複しないA->CかつB->Cなどはありえない。
変換表通りに変換前と変換後で変換を行いたい。
しかし、変換表通りにはいかないので、
変換前と変換後の文字列から同じ位置の文字をいくつか消して、
変換が成功するようにしたい。
消す箇所を最小化するときその数はいくつか？
考え方：
変換表のパターンをすべて試す。
SRM592
順列は1からNまでの順列とします。
magic(Aの順列,Bの順列)
=max(Aの0番目,Bの0番目)+max(Aの1番目,Bの1番目)+・・・+max(AのN-1番目,BのN-1番目)
と定義する。
Aの順列とBの順列はすべて試す。
結果がK以下になるパターンは何通りか？
考え方：
Aは固定してBのみ順列で回し実際に数を数える。
実際はAも順列で動くので上の結果にN!をかける。
SRM593
w,o,l,fの順番で文字が形成されているか判定せよ。
wolfは同じ文字列内であれば各文字を同じ回数繰り返して良い。
例えば繰り返しが3回のときwwwooolllfffは許される。
また2つ以上繋がっていても良い。
wwoollffwwwooolllfffも許される。
考え方：
まず最初がwであるかチェック。
wの数を数えて以降のolfが正しいかをチェック。
これを文字列が終わるまで繰り返す。
SRM594
２回に渡って星の大きさを観測した。
星はどちらも左から右に大きくなっていた。
2回の観測では倍率が異なっていたかもしれない。
考えられる最も少ない星の数はいくつか？
考え方：
Aの星1つとBの星1つが同じだと想定する。
倍率を調節して星の数を数える。
Aの星1つとBの星1つの組み合わせをすべて試す。
SRM595
白いボールがN個並んでいる。
与えられる左から右の範囲で順に白か黒に塗る。
最後の状態としてありえる状態は何通りか？
考え方：
i番目に塗った結果が最後まで残るか調べれば良い。
残るものの数をカウントし2^カウント数が答え。
SRM596
RGBからなる道を左端から右端に移動する。
このとき次の2つのルールがある。
RGBの順番でいどうする。
dの距離だけ移動するとd*dのコストがかかる。
コストを最小化せよ。
考え方：
マスが少ないので止まる場所と止まらない場所を総当たりする。
SRM597
文字列Aを文字列Bに変換したい。
文字列Aは1回の操作で1つの文字を先頭に移動できる。
最小の回数はいくつか？
考え方：
Bを後ろから順に見てAの後ろからと共通するものの数をカウントする。
全体の文字数からカウントを引いたものが答え。
SRM598
容量300のビンが無限にある。
容量101から300までの品物をビンに入れたい。
最小で何本のビンが必要か？
考え方：
品物を降順に並べる。
順番に入るスペースに入れていけば良い。
1つのビンに入る品物がせいぜい2つなのでこれで良いが、
3つ以上であればこの解法では解けない。
SRM599
A^BをC^Dで割り切れるかを判定せよ。
考え方：
実際にA^Bを計算できない。
よって、Aを素因数分解して乗数にBを乗算する。
例えば、A=72、B=5 のとき A=2^3*3^2 であるから、
A^B=2^(3*5)+3^(2*5)とできる。
A^Bの要素がC^Dを上回っていれば良い。
