問題 二項係数同士の除算C(p,q)/C(r,s)を行い、小数点第五位までを出力せよ。p,q,r,sは10000未満で、答えは常に1e7を超えないとしてよい。 やりかた 素直にやると精度が落ちて誤差死する。なので優先度付キューを2つ用意して式の分母と分子の数字をそれぞれ…

問題 デカルト座標上にnxmのグリッドがある。グリッドの格子点では上下左右の格子点に加え対角線方向のグリッドにも移動できる。このnxmの格子点について巡回セールスマン問題を解け。 やりかた 巡回セールスマン問題なのでnxm回の辺の移動がある。なので問…

問題 要素が一つだけの数列a(a[0] = 1)からはじめて、数列a中の任意の2つの要素の和を取り、それが最終項より大きい場合に最終項の後ろにくっつけるという操作を繰り返して、入力として与えられるnをつくりたい。 操作回数が最小であるときの、最終的な数列…

問題 2つの自然数が与えられ、この自然数についてStanとOllieがゲームを行う。プレーヤは大きい方の数から小さい方の数の倍数を引いて相手プレーヤに渡すことができる。ただし、大きい方から小さい方の倍数を引いて残った数は0以上にならなければいけない。…

問題 "s1<s2>s3<s4>s5" という形式の文字列が与えられる。もう一つ "s..." という形式の文字列が与えられる。元の文字列からカッコを取り除いた文字列と、もう一つの文字列を "ss4s3s2s5" という形式に直したものを出力せよ。 やりかた Javaであれば正規表現を使える</s4></s2>…

問題 複数種類の硬貨があり、その重さと価値が与えられる。重みの和がちょうどE-Fになるように硬貨を取り出したときの価値の和を最小化せよ。硬貨は各種類とも無尽蔵にあるとしていい。 やりかた dp[i]:=（重みの和がiであるときの価値の最小値）でDP。硬貨j…

問題 ビーカーAとBの容量Ca、Cbが与えられる。ビーカーに水を入れる操作を行って、どちらかのビーカーに入っている水がNになるようにしたい。行ってよい操作は以下の6種類である。 Aいっぱいに水を入れる Bいっぱいに水を入れる Aを空にする Bを空にする Aの…

問題 アルファベットとアンダーバーからなる文字種を[a-i]、[j-r]、[s-zと_]の3グループに分ける。 文字置換による文章の暗号化を行いたい。暗号化の方法は平文の文字を一つずつ見ていき、その文字がグループiに属する時、その文字の右側を見ていって、グル…

問題 4x4のオセロの盤面が与えられる。盤上の石を一つひっくり返すと4近傍の石もひっくり返るとする。すべての石が同じ色になるために必要なひっくり返す動作の最小回数を求めよ。どうひっくり返しても達成できない場合は"Impossible"を出力せよ。 やりかた …

問題 リボルバー式の拳銃があり、シリンダー内の弾の装填の情報が与えられる。ロシアンルーレットで遊ぶとして、どの薬室からスタートしたかわからないが相手の手番では発砲しなかった。次の番はあなたで、そのまま打つか、シリンダーをランダムに回転させて…

問題 チェス大会のチーム編成を考えたい。各チェスプレーヤについて、白チームとして戦った場合の強さと黒チームとして戦った場合の強さの2つが与えられる。30人以上のプレーヤの強さが与えられる。これらプレーヤから選抜で白チーム15人、黒チーム15人の編…

問題 x,y座標が幾つか与えられる。0番目の点から1番目の点に向かって、直接、もしくはその他の点を経由しながら移動する。点から点へのジャンプにかかるコストは点と点のユークリッド距離で表される。移動中にかかる最長のコストを最小化せよ。 やりかた 二…

問題 アルファベット大文字からなる平文に対し、A=1、B=2、…、Z=26と置き換える暗号化を行う。この暗号文は一意に復号化できない可能性がある。暗号文が与えられるので何通りの復号化があるか求めよ。 やりかた DP。 dp[i]:=（i桁目までの復号化パターン数）…

問題 アルファベット表記された数字を英数字に変換して表示せよ。 やりかた 数字をthousand未満、thousandの桁、millionの桁に分けて各桁を英数字に直して、桁の数字をかけて足し合わせた。以下ソース。 int main(int argc, char **argv){ map<string, int> p; p["negativ</string,>…

問題 ロボットが2次元座標上で原点から出発して左回りに動いて再び原点に戻ってくる。動作は格子点から格子点への直線運動の繰り返しで行われ、毎回の移動量dx, dyが入力として与えられる。この一周の動作で囲われた領域の内部にある格子点の総数、動作した…

問題 [0...k](0 やりかた DP。 dp[i][j]:=（長さiの文字列で最後の文字がjであるようなtightな文字列が発生する割合（百分率））とする。dpでtightな文字列の総パターン数を求めて(k+1)^nで割ることもできるが、C++では多倍長整数を使わないとできないのでこ…

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

問題 'x'を変数とする1次方程式が文字列形式で与えられる。この方程式をxについて解き、解を床関数にかけたものを出力せよ。ただし解が不定の場合は"IDENTITY"を、不能の場合は"IMPOSSIBLE"を出力せよ。なお入力文字列は空白を含まない。 やりかた 単にやる…

問題 トランプがnセット（1セットあたりジョーカーなしの52枚）与えられ、このカードデッキを使ってブラックジャックを行う。 この中からディーラーが1枚、あなたが2枚をランダムにピックアップし、場にお互いが見えるように置く。ディーラーがランダムにも…

問題 木の名前がいくつか入力される。各木の種類について、それが入力された総数のうち何%を占めているか木の名前のアルファベット順にパーセンテージで出力せよ。 やりかた mapに木の名前と出現数を入れて総数で割って、、、というだけ。入力はgetsを使えば…

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

問題 自然数Nが与えられる。N 1から数えてN番目に出現する回文形式の整数を返せ。 やりかた ある桁数の整数中に回文整数がいくつあるかというと、 1桁：1 ～ 9 9個 2桁：11 ～ 99 9個 3桁：101 ～ 999 90個 4桁：1001 ～9999 90個 5桁：10001 ～ 99999 900個…

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

問題 直径Dの円に内接する複数の直径dの小円を考える。小円同士の中心が少なくともs+d以上離れているように配置したい。最大でいくつの小円を配置できるか。 やりかた 配置する間隔は等間隔にする。間隔は円の個数に対して単調減少なので二分探索できる。C個…

問題 一直線の道路上にN個のぬかるみがありそれが[s,e)の形で与えられる（s,eは非負整数）。なお与えられる範囲に重複はない。長さKの木板が無数にあり、これらを使ってぬかるみをすべて覆いたい。最小でいくつの木板が必要か。 やりかた 貪欲。 領域の左端…

問題 略 やりかた 見開きのページ番号の和はどの見開きであっても一定（ページ数以上の最小の4の倍数+1になる）になるので片一方の番号がわかれば見開きのもう片方の番号は自動的に決まる。コード上では見開き上の若番の番号から老番のページ番号を求めて、…

問題 やりかた 与えられる文字列の長さはせいぜい12文字なので、全探索でも1ケースあたり程度の計算でOKなので全探索で。 ただvectorやstringを引数に関数の値渡しをすると簡単にTLEしてしまった。参照渡しにしたら簡単に通った。以下ソース。 vector<ll> c(5); </ll>…

問題 1～3の数字からなる数列がある。この数列を単調非減少もしくは単調非増加にするために書き換える必要のある数字は最小でいくつか求めよ。なお数字は1～3にしか書き換えられない。 やりかた DPでやった。 数列のうちの単調非減少なLISの長さをもとめると…

問題 1からNまでのラベルが付いたノードが与えられる。このグラフの有効辺がM個与えられる。トポロジカル順序が厳密に決まっているノード数を返せ。 やりかた トポロジカルソートできるグラフだとして、あるノードのトポロジカル順序が厳密に決まっている場…

問題 nxnのマスに1～nまでの数字がn個ずつ割り振られている。同じ数字が割り振られているマスがすべて4-連結しているか判定せよ。入力形式が少しわかりにくくて、各テストケースのi行目が数字iを持つマスのy座標、x座標を連続で表している。テストケースはn-…