問題 n番目の正四面体数は、n*(n+1)*(n+2)/6に等しい。 Nが与えられたとき、そのNを複数の正四面体数の和で表現したい。(同じ正四面体数を何度も使ってよい) 組み合わせる正四面体数が最小になるようにNを表現したときの組み合わせ数を求めよ。 また、組み合…

問題 N個の数字が与えられ、N-1個の数字の間には＋または-がはいり、その計算結果がN番目の数字になるような計算を考える。 前方から＋または-で計算して、負の数または20を超える途中計算になるような計算が許されない場合、何通りの計算方法があるか？を答…

問題 n段の階段を、各段で1〜3段のどれかを選んで上っていくことができる。 階段を上るパターンを考えるとき、1日10通りの方法で上ることができる場合、何年かかるか？ 考え方 dp[i]:=i段まで上ったときのパターン数 とすると、このパターン数はdp[i+1]とdp[…

問題 1からNの番号が書かれたN枚のカードが下から昇順になるように重ねてある。 「上からp枚目からc枚を取り出してカードの山に持ってくる」というシャッフルをR回繰り返す。 シャッフル後に一番上に来ているカードの番号を返す。 考え方 必要なのは最後に一…

問題 木が与えられる。 木の辺を以下のルールで削除していく。 ・最初にどこかのノードを決める ・ノードから辺を渡って別のノードへ移動する ・今いるノードにつながる辺を一つ削除し、今いるノードにとどまる 辺が無いノードには移動できない。削除や移動…

問題 n個の部屋があり、部屋と部屋を結ぶ通路はn-1本存在している。 通路はどちらの方向へも進むことができ、距離が設定されている。 ある部屋からすべての部屋へ行くことが可能である。危険度とは、ある部屋から別の部屋へ移動するとき、最短で移動するパス…

問題 nが与えられるので、n個の連続した正の整数を求める。 ただし、その正の整数すべてについて、合成数でなければならない。1 考え方 nが大きい。 合成数の連続というのは、2つの連続する素数の差(prime gaps)が1500以上になるところが答えになる。 調べて…

問題 ある無限に広い2次元グリッドの、あるマスにいる。兵士をn人つれており、各兵士の体力が与えられる。 各兵士は上下左右の隣接マスに移動できるが体力が1減る。 通ったマスを占領できるとき、最大でいくつのマスを占領できるか。 考え方 最初に降順にソ…

問題 r*cの2次元グリッド上の2点間マンハッタン距離で最小となる経路の数を返す。 ただし、グリッドは上下、左右がつながっており、右端は左端に移動、などができる。(トーラス) 考え方 2つの座標a,bについて、aを固定して考える。 bについて、グリッドの周…

問題 n桁のIDのチェックを行う。チェックは各桁について、右端を1桁目として、偶数桁の数字を2倍してすべての桁を足したものが10で割り切れるかどうかで確認する。2倍して2桁になった場合はそれらをさらに分割し、それを足したものを用いる。 IDには*が含ま…

問題 各部屋は通路でつながっている。 2つの勢力があり、各部屋をそれぞれの勢力に割り振り、それぞれの勢力の部屋同士が通路でつながっていないようにしたい。(両勢力は少なくとも1つの部屋を所持する) しかし、部屋の数と通路はすでに建設中で、通路を壊す…

0223 BFSで探索した． 一応メモ化して同じ状態を何度も計算しないようにした．

新しい問題を少々．

2185 範囲内ならカウント。 2186 簡単なDP。 2187 全通り調べる。 最初9!*9!(ゲイツの出し方とジャッキーの出し方)を試さないとだめかなぁと思ってdfs書こうと思ったけど、終わるわけないので考え直す。 g{123,132,213,231,312,321}とj{123,132,213,231,312,…

2102 R[i],G[i],B[i]に入力枚数を保持しておいて、(i,i+1,i+2)が1枚以上あったら1セットとして引く、(i)が3枚あったら1セットとして引く、というのをRGBそれぞれについて全探索した。 2103 書いてある通りにシミュレーションするだけ。 2104 一応確認のため…

1154 問題がわかりずらくて泣。理解力がなくて泣。 とりあえず月曜土曜数を生成しておいて、月曜土曜素数かどうかを判定する関数を用意した。 そして、毎回入力に対して、「月曜土曜数で割り切れて」かつ「その月曜土曜数が月曜土曜素数」の時、表示。 毎回…

1136 探す折れ線の始点を原点に直して0,90,180,270度回転させた折れ線とそれぞれ比較する。折れ線の始点から終点までの座標を逆に入れ替えたものとも比較した。 1138 現在位置と馬車券の使用状況でダイクストラ。馬車券は8枚までしかないので、使用状況を2進…

1131 p/qとなる単位分数の和を探す。和はn個以下、分母がa以下、となる全探索する。 現在の値を、分子pp、分母qqで保持してたけど、既約分数で扱うために毎回gcdを計算してたらTLE。 そんなことしなくても「p/q==pp/qq」かどうかは「p*qq==q*pp」なので、既…

1060 No Story LCM(a,b)=Lとなるa,bの組み合わせの数．前はa,bをループでまわしてバッチリTLEもらったはず． wikipediaのページにあるように， とのときとなるので，lcm(a,b)=LのときLを素因数分解すればそれぞれのの値がもとまる． とすると，が0以上以下な…

0179 幅優先探索。 0181 想定解法ではないようだけれども、DFSで無理矢理解いた。枝刈りは「今の段目での長さが今までの最適な本棚の幅よりも長くなったら刈る」でやった。 DPだと一瞬で終わるようなので、想定解法( http://algorithms.blog55.fc2.com/blog-…

0177 球上の2点間の距離。 //(緯度(北+,南-),経度(東+,西-))->地点1(i1,k1)、地点2(i2,k2) double rad = sin(i1)*sin(i2)+cos(i1)*cos(i2)*cos(k1-k2);//i1,i2,k1,k2はラジアン double dist = 6378.1*acos(rad); //2点間距離

0160 モノの大きさは(x+y+h)。 0161 ソートして表示するだけ。 0162 あらかじめbool配列で1000000までハミングナンバーかどうかを計算しておいた。 iがハミングナンバーなら、i*2とi*3とi*5もハミングナンバーなので、1から計算していける。 0164 書いてある…

0168 とりあえず、dfsであらかじめ30まで計算しておいてそれを返すようにしたorz dp[i]がi段目に来るまでのパターン数だとすると、(i-1)段から1段ジャンプor(i-2)段から2段ジャンプor(i-3)段から3段ジャンプなので、dp[i]=dp[i-1]+dp[i-2]+dp[i-3]。 0169 一…

0183 全部チェックするだけ。 0185 あらかじめ2つの素数の和を全部計算しておいて、、、とかやるとTLE。 (n-primes[i])が素数かどうかをチェックして、その数を数えた。 0186 まず会津地鶏はmin{(b/c1),q2}個買える。これが0個ならNA。 あとは、残りの予算で…

グラフな難問．しゅたいなー木．

528 最初、文字列の片方のすべての部分文字列を作って、もう片方とラビンカーブでマッチングとかどうみてもTLEなコードを書いてTLE。 片方の文字列をずらしながら両方の文字列と比較して連続する文字をカウントしていった。 538 パターン文字を作ってしまう…

540 あみだくじ。あらかじめすべての横棒について、番号iの縦棒と番号jの縦棒をswapするかを計算しておいて、横棒を消さない場合の合計点数、横棒kを消した場合swapした後の合計点数をすべて調べて最小の合計点数を返した。 541 Nが大きいので、普通にシミュ…

やるだけ系。

523 やるだけ。 524 星座データの最初の点が写真のi番目の点だとし、そこを起点として写真と星座データが重なるか調べた。0.02sでメモリが872KB。ちょっと遅い。 525 「横の何行かを同時に１回裏返し，引き続き，縦の何列かを同時に１回裏返して」ということ…

209 そのまま,90度回転,180度回転,270度回転した景色を用意しておいて、全部調べる。 全部調べないと、回転したら切れ端の座標がより小さくなる場合を見逃す。 211 iさんが、距離di、速度viで走った場合、di*ki=t*vi。ただし、tはみんながそろう時間、kiはそ…