問題 各要素が整数の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…

問題 bouncy数とは、数字の各ケタについて、増加列でも減少列でもない数字をいう。 1からnまでの数で初めにbouncy数の割合が99%となるnを求める。 考え方 各桁ごとに分解した数字列を求め、それをソートする。 そして、もとの数字列と昇順ソートしたもの＆降…

問題 a^bのaとbが複数与えられる。 与えられたa^bの中で一番大きいものを返す。 考え方 対数をとっても大小関係は変わらないので、b*log(a)を使って比較する。

問題 80*80の配列に数字が入っている。 各マスで右または下に移動できるとき、左上から右下までの経路で数字の和が最小となるものを見つけ、その和を返す。 考え方 ダイクストラ。

問題 4ケタの数が3つa,b,cあり、 ・それぞれが等差(b-a==c-b) ・すべて素数 ・a,b,cの各桁の数値は並び替えると、他の2つの数値を作り出せる ようなa,b,cを見つける。 1487,4817,8147以外にもう一つあるので、それを連結した12ケタの数字を答える。 考え方 …

問題 各桁の数字が0〜9までが1回ずつしか出ないような10ケタの数字を考える。 d[i]がi桁目を表すとすると、 d[2]d[3]d[4]が2で割り切れる、d[3]d[4]d[5]が5で割り切れる、、、と素数で割り切れれるようなものの総和を求める 考え方 各数字が1回ずつしか出な…

問題 28433*2^7830457+1 の末尾10桁を求める。 考え方 多倍長で繰り返し2乗法で計算。

ox- 638位で敗退。500もオーバーフローだけで、アルゴリズム的には間違ってなかったのでよしとする。。 (凡ミス再提出はだめだったけど) 今回、500で線形探索してる人結構部屋にいたけど、作っておいたテストケースが貼り付けたとき最後になぞのスペースが入…

問題 プログラミングコンテストをやっている。 部屋がn+1部屋あって、0〜n-1までの番号の部屋にはそれぞれ何人か人がいる。 自分はn番の部屋に1人でいて、ほかの部屋の人数は知ることはできない。 各部屋のスコアの合計点数の配列が与えられる。 今、自分よ…