問題 整数aを素数の和で表現できる組み合わせの数を考える。 10の場合、5通りの表現ができる。 5000通り以上の表現ができる最初の整数を求める。 考え方 素数を列挙しておいて、実際に組み合わせを計算。 1から試していって、最初に5000通りを超えるものを返…

問題 1〜100のうち、無理数のもので、平方根を計算したとき、100ケタ分の各桁の和をもとめ、それらの総和を求める。 考え方 64で連分数展開の数列が得られているので、それを使って実際に100ケタ分計算。 それらの和を求める。

問題 sqrt(N)の連分数展開を考える。 連分数の各分母の整数部分の数列をa_nとするとき、a_nの周期が奇数になっているものを答える。 考え方 連分数展開を例通りに実装する。 n=1000程度まで求めて、周期を求める。 周期は、ループで周期を決め打ちし、その周…

問題 素数a,b,cについて、a^2+b^3+c^4を考える。 この和が5*10^7未満となるような数はいくつあるか。 考え方 実際に試してみる。答えは「a,b,cの組の数」ではなく「和の数値がいくつあるか」なので注意。

問題 フィボナッチ数列F_kで、先頭9個と末尾9個の桁の数字がどちらも1〜9の数字で構成されるようなkを求める。 考え方 見当がつかないので、多倍長で実際に試してみた。

問題 80x80の行列が与えられる。 左上から右下までの経路で、その経路上の数値の和が最小になるものを求める。 各マスでは、上下左右に移動できる。 考え方 ダイクストラ。

問題 ある整数nとその反転rev(n)の和n+rev(n)の各桁がすべて奇数であるようなnは10^9未満でいくつ存在するか。 考え方 実際に試す。

問題 magic 5-gon ringというものを考える。 各直線にならぶ数字の和がすべて同じになるものをいう。 このとき、これを満たすとき、数字に直して16ケタになるもので最大のものを答える。数字は、角の中で一番小さいところから直線にならぶ数字3つを時計回り…

問題 各要素が整数の80x80の行列が与えられる。 一番左の列のどこかから一番右側の列のどこかまでの経路の中で合計が最小となるものを答える。 各マスでは、上、右、下のどれかに移動できる。 考え方 一番左の各要素から一番右側のどこかにたどり着く最短距…

問題 nとdを正の整数とし、n 考え方 分母がdの時を考える。 1/3

問題 nとdを正の整数とし、n 考え方 分子がn(1〜N-1)の時に、nの素因数で割り切れないdの個数を求めれば、分子がnの既約分数の個数を求められる。 N以下の整数の、素因数リストの少なくとも1つで割り切れるものの個数は、包除原理で求められるので、各nにつ…

問題 オイラーのφ関数についてφ(n)の各桁の数を並び替えたものがnになるものを考える。 1 考え方 実際に試してみる。

問題 三角形の各頂点の座標が与えられる。その三角形が原点を内部に含むかどうかを判定する。 考え方 3点の回転方向を求める関数を用意する。 三角形の頂点x,y,zについて、 xy,yz,zxの線分上に原点がある x->y->0, y->z->0, z->x->0の回転方向がすべて同じな…

問題 正N角形の各頂点だけが配置されている。 ある頂点リストpoints(M個、N 考え方 bitDP。蟻本の「3-4 動的計画法を極める！」と同じような感じで、dp[辿った頂点集合][今いる頂点]で2重ループで書ける。今の辿った頂点集合stと今いる頂点vについて、まだた…

問題 ある整数nの2乗が1_2_3_4_5_6_7_8_9_0(_は1桁の数字)となるようなnを求める。 考え方 桁数の関係からn>10^9で、最大値は193000...00までなので、n 4*10^8 * 判定ぐらいなので、見つかるまで回した。

問題 ポーカーのカード2組が与えられる。プレイヤーAとプレイヤーBのカードで、1000回分ある。 プレイヤーAが勝っているのは何組あるか。 考え方 がんばって実装する。

問題 0を含まない整数AとBがあり、交互に各ターンでそれぞれ以下の2つの操作ができる。 ・いまの数字をreverseする(123->321) ・いまの数字/10する(123->12) 2人でそれぞれの数字を操作していくゲームを考える。 このとき、AがBと同じ数字にすることができた…

問題 整数aの各桁の数値を階乗したものの和をbとする、bの各桁を、、、ということを繰り返す。 大体の整数はループするが、1000000未満で、60回以上繰り返してもループが発生しない数が存在する。いつくあるか。 考え方 実際に試す。

問題 eの連分数展開を100まで行った時の近似分数a/bの分子aの各桁の和を求める。 考え方 eの連分数のときに出現する値は与えられているので、それを愚直に実装し、a/bを求める。 あるa/bがあるとき、a+=b*v[i]としたうえでswap(a,b)というのを繰り返すと求め…

問題 立方数a^3の各桁を入れ替えて別の立方数を4つ作れるような立方数の最小のものを見つける 考え方 ある程度まで立方数を生成しておく。 生成した数を桁の数字をソートして、ハッシュなどで何個できるかカウント。 最終的にこの数が5個になるものを求める。…

問題 既約分数n/d(ただし、n>d)を考える。 d d 考え方 dが決まった時に、nの値は、n これはO(1)で求められるので、dについて回して、3/7より小さいもので最大となるものを答える。 誤差があるかもしれないので、できるだけ整数で扱う。 a/b

問題 h*wの長方形格子の中にi*jの長方形がいくつあるか考える。(1 長方形の合計数が2000000に一番近い個数の時の面積を答える。 考え方 DP。実際に試そうとすると時間がかかりすぎてしまう。 h*wの時の個数は、\sigma_{i=1}^{h} \sigma_{j=1}^{w} {i*j}とか…

問題 オイラーのφ関数で、n/φ(n)が最大となるものをn 考え方 実際に試す。

問題 euler28のように渦巻き状に数を並べていく。 対角線上の数値について、素数の割合が10%以下になる最小の幅を求める。 考え方 幅がiのとき、新たに追加された部分の4つ角の数値は、法則性から (i-1)*(i-1) - (i-2) (i-1)*(i-1) - (i-2) + i-1 (i-1)*(i-1…

問題 2の平方根の連分数展開を1000項まで考える。 i項まで展開したときの分子と分母のうち、分子の桁数の方が分母の桁数を超えるものはいくつあるか。 考え方 多倍長で実際に計算する。

問題 10000000未満の数で、以下の操作をしたとき、89が出現するものはいくつあるか。 ・各桁を2乗したものの和を取る ・その和をまた各桁を2乗したものの和を取ることを繰り返す これを繰り返すと1または89のどちらかが出現し、繰り返すことがわかっている。…

問題 ある暗号化された文がバイトごとに区切られたものが与えられる。 あるアルファベット3文字によってXORを取ったものであることがわかっている。 元の文のasciiコードの数値の和を求める。 考え方 3文字をどういう風に使ってXORとるか書かれていない。 考…

問題 自然数をn乗したものがn桁になるものはいくつあるか。 考え方 自然数をaとすると、 10^{n-1} を満たすので、変形すると、 (n-1)/n を満たさなければいけない。aは自然数なので、右側の不等式から、1〜9までを調べればよい。 各aについて、nを1から(n-1)…

問題 あるパスコードがあったとして、ランダムに左から3つ選んで入力するセキュリティシステムがある。 50回分の入力に成功している3つの数字のリストが与えられる。 可能なパスコードのうち、一番短いものを見つける。 考え方 パスコードを見てみると、同じ…

問題 五角数とはPn=n(3n-1)/2であらわされる数をいう。 あるPk,Pjについて、その和と差が五角数になるもののうち、差D=|Pk-Pj|の最小値を求める。 考え方 五角数の判定は、あるaが五角数ならば3n^2-n-2a=0の解nが整数になるはずなので、n=(1+sqrt(1+24a))/6…