問題 プログラミングコンテストの部屋割りをする。 N人の登録があるとする。 Nが20で割り切れるなら、部屋数はN/20。割り切れないならN/20+1(/は、整数割り算を表す)。 レートについて降順にならべ、R人ずつ、ランダムに部屋がかぶらないように部屋を割り当…

絶望的にできてないけど焦ってもしょうがないし、ゆっくり進めてく。 最終的な目標は「どんな問題でも時間内で解ける」なので、 時間がかかっても(時間内に終わらなくても)解く あとまわしはよくないかもしれない 問題を読んだ日からあまり開けずに解く わか…

問題 上流からうなぎが流れてくる。 うなぎiは、長さがl[i]で、最初に-t[i]にいて、原点方向へ向かって流れてくる。 すべてのうなぎは1単位時間に1だけ動く。 ある時刻で、原点に来たすべてのうなぎを捕まえることができるが、2回までしかその行為を行えない…

問題 店がN個あり、0からインデクスがふってある。 0〜M-1の店に興味があり、そこで商品を買いたい(1度だけ購入することができる)。 興味のあるお店については、開店時間、閉店時間、買い物にかかる時間が与えられる。 また、いくつかの店間には道があり、そ…

問題 n個の非負の整数a1,a2,...,anが与えられる。 これを2^a1,2^a2,...と書き直して総和を求める。 これに2^b(b>=0)形式のものをいくつか加えて、その総和が2^{v}-1(vは任意)になるようにしたい。 いくつ加えればよいか。 1 0 考え方 各ビットで考えられる。…

問題 n個まで連分数展開されたa0+1/(a1+1/...)の配列aと、分数p/qが与えられる。 この連分数展開されたものと分数p/qが等しいかどうかを返す。1 1 考え方 多倍長があれば、それを使って連分数をpp/qq形式に直して、pp*q == qq*pかどうかを判定。 または、p/q…

問題 非負で100以下の異なる整数がいくつか与えられる。 このとき、「任意のペアが、それらの各桁について少なくとも0を含む」ようにサブセットを作る。 2つの整数を同時に、1の位、10の位、100の位で見て、どちらかが0になるようにする。サブセットは満たす…

問題 2つの文字列X,Yを考えたとき、前方からどちらかを選んぶことを続けてマージした文字列Sを考える。 ここで、YはXを並び替えたものとすると、Sが与えられたとき、Xとしてありうる文字列の辞書順最小を答える。 考え方 一文字ずつ残りが可能かどうかチェッ…

問題 テキストエディターを操作している。 結果表示画面、テキストバッファ画面、アンドゥ履歴画面から構成される。 今、結果表示画面に表示したいテキストが与えられる。 1行単位で処理していくとき、テキストバッファに入力し、エンターを押すことで結果表…

問題 赤玉がr個、緑玉がg個、青玉がb個あり、以下のルールを上から順に繰り返す。 ・赤玉が残っていれば、赤玉を1つ取り除く ・緑玉が残っていれば、緑玉を1つ取り除く ・青玉が残っていれば、青玉を1つ取り除くしかし、合計数r+g+b=n個だったこととk回目に…

問題 w*hのチェスボード上をチェスのナイトが動く。 ナイトツアーとは、任意の場所からスタートし、スタート地点に戻ってくる経路のことを言う。 ここで、同じ場所は何度も通ってよい。 ナイトサーキットのサイズとは、1度でも訪れたチェスのマスのuniq数を…

問題 (0,0)から(X,Y)まで移動する。 各ターンで、上下左右に動けるが、iターン目にはiだけ移動する。移動方法をNSEWを並べた文字列で返す。 考え方 (0,0)から(X,Y)までtターンで移動できるかどうかを考える。 移動するための条件として、 1+2+...+t >= abs(X…

問題 アルファベットの文字列Sと整数nが与えられる。 長さLは、0 考え方 dp的に考える。文字列の0〜iまでの、求めたい個数をdp[i]とする。この値を求めたい。 dp[i-1]がすでに計算されているとして、今考えなければいけない文字列は、 部分文字列0〜i、1〜i…

通過できませんでした。日頃のサボりが如実に表れています。。 Aだけ解いた。

問題 白黒の円を交互に描きたい。 同心円で、半径rの白い円の外に半径1の黒い丸を描き、その外に半径1の白い丸、その外側に半径1の黒い丸、のように描いていく。 白い円は今回描く必要はなく、黒い丸を描いていきたい。 今、tミリリットルの墨があり、1ミリ…

問題 文字列Sが与えられる。 これは、元の英文からスペースが取り除かれ、いくつかの文字が別の文字に代わってしまっている文で、別な文字に置き換わっているものは、隣接する4文字以下には置き換わっている文字がないことが保障される。 例として、 元の文…

通過してない。 AとC-smallだけ通した。

通過してない。A-small,B-small,C-small1だけ通した。

4問中ABCが解けて170pt、636位。

問題 バラとユリが何本か入った箱が与えられる。箱iについて、バラの本数とユリの本数がわかる。 この箱をいくつか使って、R*Lのグリッドの各グリッドに花を植えるために使う。 ただし、各グリッドについて、隣接する4つのグリッドはそのグリッドに植えた花…

問題 文字列がいくつかと、文字列a,b,cが与えられる。 各文字列が以下の条件を1つ以上満たすとき、悪い文字列であるという。 ・接頭辞が文字列a ・接尾辞が文字列b ・接頭辞と接尾辞以外の部分文字列にcを含む いくつ悪い文字列があるか数える。 考え方 実際…

問題 チェスボードと、複数のナイトかポーンがある。 初期配置と最終配置が与えられる。 1手で1つのコマを1回動かせる。各コマの動きは以下。 ・ナイトは、ボードからはみ出ないように全方向の桂馬飛びで移動できる ・ポーンは、1マス進める。一番端まで移動…

問題 整数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つを時計回り…