解いた問題のソースコードと解説など。


整数問題

POJ 1855 Mint

問題 数種類の長さの棒がある。各種類とも棒は無尽蔵にあるとして良い。棒をつなぎ合わせて4本足の机を作る。各足は同じ種類の木を使い、4本の足の長さが揃うように作る時、決められた高さ以下で作れる最高の高さと、決められた高さ以上で作れる最小の高さを…

POJ 2954 Triangle

問題 3つの格子点の座標が与えられる。この格子点からなる三角形の内部にある格子点数を求めよ。ただし、辺上の格子点は数えない。また、与えられる三角形の面積は必ず0より大きい。 やりかた ピックの定理を使った。(ピックの定理) 頂点がすべて格子点上…

POJ 1730 Perfect Pth Powers

問題 整数Xが与えられる。X=b^pを満たすような整数bおよび自然数pが存在するとき、Xをp-th perfect numberという。pの最大値を求めよ。 制約: やりかた 例えばなのでmax(p)=4となるように、Xを素因数分解して、各素因数の指数の最大公約数が答えになる。答え…

POJ 3270 Cow Sorting

問題 要素のスワップを繰り返して数列を昇順にソートしたい。数列中のXとYを入れ替える時のコストをX+Yとする。ソートに必要な最小コストを求めよ。 やりかた 数列を巡回置換のまとまりに分解する。 例えば(3,5,7,4,2,1,6)であれば(3,7,1,6)(5,2)(4)となる。…

POJ 2407 Relatives

問題 n(1自然数の個数を求めよ。 やりかた 包除原理。 nの素因数p[]を求めておく。するとnと互いに素でないn未満の自然数の数は、をn未満のp[i]の倍数の集合とするとで求めることができる。これは包除原理をもとにすぐ計算できる。(Kはnの素因数の個数)以下…

POJ 2247 Humble Numbers

問題 素因数が2,3,5,7のみであるものをHumble Numberという。n番目のHumble Numberを出力せよ。(1 やりかた setにhumble numberを突っ込んでいって一番小さいものから取り出してそれらに2,3,5,7をかけてもう一度setに突っ込んで、また一番小さいものから取り…

POJ 2739 Sum of Consecutive Prime Numbers

問題 2以上10000以下の整数nが与えられる。nを連続する素数の和で表したい。何通りの方法があるか求めよ。素数一つで表せる場合も該当する。 やりかた エラトステネスの篩をして10000以下の素数の数列を求めておき、それらの部分数列の和を全列挙して該当す…

POJ 2909 Goldbach's Conjecture

問題 4以上の整数は2つの素数の和で表せる、という予想をゴールドバッハ予想という。4以上2^15以下の整数nが与えられるので和がnとなるような素数の組数を返せ。ただし(p1,p2)という組と(p2,p1)という組を別々に数えてないけない。 やりかた エラトステネス…

SRM 392 Div1 Medium RoundAboutCircle

問題 円周上にノードが配置してあり、時計回りに1からNまでの番号が振られている。数字iのノードからはiの各桁の数字の和だけ時計回りに進むことができる。あるノードからスタートして移動中にすでに訪れたノードについたら終わりとする。任意のノードからス…

SRM 365 Div1 Medium ArithmaticProgressions

問題 やりかた 以下ソース。 class ArithmeticProgressions { public: ll N, m, M; vector<ll> s; ll floor(ll a, ll b){ ll m = a % b; if(m < 0) m += b; return (a - m) / b; } ll ceil(ll a, ll b){ ll m = a % b; if(m < 0) m += b; if(m > 0) m = b - m; r</ll>…

SRM 354 Div1 Medium RemissiveSwaps

問題 整数Nが与えられる。好きな桁を2つ選んで、それらの数字を1つずつ減らしてそれらを交換するというゲームを行う。このゲームでとりうる最も大きい数字を求めよ。なおLeading Zeroができてはいけない。 やりかた ゲーム中に桁が増えるようなことはなく、…

SRM 574 Div1 Easy TheNumberGame

問題 プレーヤーが二人いて各々が数字をひとつ持っている。この数字は10進数表記で0を含んでいない。1ターンごとに交互の順番で以下の2つの操作のうち好きな方を選んで行う。 数字を逆順にする 数字を10で割る 先方のプレーヤーが1000ターン以内に後方の持つ…

SRM 545 Div2 Hard SpacetskE

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=12030&rd=14737 xy座標のX軸上を原点から座標(L,0)までの整数座標上において、ロケット任意の方向に1つだけ発射される。放たれたロケットはその方向に直線で進行し、0 やりかた XY座標における…

SRM 540 Div2 Hard FractionInDifferentBases

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11135&rd=14732 P / Q(既約とは限らない)をX進数で表現した時に割り切れないとする。AからBの間にこのようなXはいくつ存在するか。 やりかた Editorialを参考にしました。まずP、Qをこれらの最…

SRM 522 Div2 Hard CorrectMultiplicationTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11609&rd=14547 a * b = cという等式が与えられる。しかしこの等式は成り立っていないのでa,b,cをA,B,Cに書き換えてA * B = Cが成り立つようにしたい。の最小値はいくつか。1 やりかた Aを1から1…

SRM 519 Div2 Hard BinaryCards

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11552&rd=14544 カードが複数枚あり、2^0, 2^1, 2^3, ...というように各々に2のべき乗のいずれかが書かれている。このカードを表にすることでそのカードを使用するということをあらわす。自然数…

SRM 510 Div2 Hard TheLuckyBasesDivTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11466&rd=14439 自然数nが与えられる。これをb進数で表した時に各桁に4か7しか現れないようなb進数(ただしb >= 2)はいくつか(つまりbはいくつの値を取りうるか)。 やりかた 全探索ではもちろ…

SRM 507 Div2 Hard CubeRoll

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11322&rd=14436 数直線上に落とし穴があり、落とし穴の位置はholePos[i]で与えられる。最初initPosにある石をgoalPosに動かすことを考える。一回の移動で数直線上で平方数移動することができる。…

POJ 1338 Ugly Numbers

問題 http://poj.org/problem?id=1338 2,3,5のみが素因数の数をUgly number という。便宜上1もUgly number とする。n番目のUgly number を求めよ。n やりかた プライオリティキューに生成した数を入れていきながら幅優先探索。要long long。 setに発見した…

POJ 2262 Goldbach's Conjecture

問題 http://poj.org/problem?id=22624以上の偶数は2つの奇素数の和で表せるという予想をゴールドバッハ予想という。入力nに対しそのような2つの奇素数を返せ。複数ある場合は絶対値の差が最大になるペアを返せ。 やりかた エラトステネスの篩をしたあと…

しょげないでよBaby 眠れば治る