内容 n種類の商品がそれぞれv[i]個ある。 同じ種類の商品は区別しないが、別の種類の商品は区別するとき、これらの商品からM個取り出す組み合わせの数 考え方 dp[i+1][j]:=商品iまで使って個数j個選ぶ組み合わせの数 漸化式は、商品i-1まででj-k個選んで、商…

問題 木が与えられる。 ある頂点を取り除いてできる連結成分の最大のサイズを各頂点について計算する。 N 考え方 木が与えられたらとりあえず適当な頂点を選んで根付き木にして考える。 木DPで、その頂点以下の部分木の頂点数を求める。 これによって子ノー…

問題 n個のパターン文字列が与えられる。パータン文字列は、小文字アルファベットか'*'で構成される長さMの文字列。 '*'の場合は任意のアルファベット1文字にマッチする。 与えられるパターン文字列は、文字列集合Xのどれか1つの文字列にマッチするように作…

組み合わせ回。

AOJ出てないので確認できてないけど、アルゴリズムだけ。

参加記。

問題 XY座標の原点からゴール(X,Y)までジャンプで移動する。 ジャンプは、X,Y軸に平行に上下左右のどれかにDだけランダムに移動する。その確率は1/4。 ちょうどN回ジャンプしたときにゴール地点にいる確率を求めよ。1 1 -10^9 考え方 まず、X,Yはそれぞれ絶…

Haskellで挑戦したけどダメで、C++で書いても間違えるという・・・

Haskellで挑戦。

Haskellで挑戦。

問題 2人が2つの「石が積まれた山」から交互に好きな方を選んで取っていく。 石には数字が書かれており、取った石の数値の合計が最終得点となる。 両者が最善を尽くしたとき、先手の得られる最終得点を答える。 考え方 ゲーム木の探索(先読み)。 ゲームの状…

マラソンマッチに参加した。

1494位あたりでTシャツゲットならず。。。(TシャツラインはABとD-small早解き) いくつか既出な問題だったようで、日頃勉強してないのが悔やまれる。

教 育 的 問 題。 勉強になった。

large解法は解説でたら確認したい。

Round1Cで通過。 去年はRound1が通過できなかったのでよかった。参加記録だけ。

問題 N(1 これを無作為に一列に並べ以下の操作をする。 1.最初にすべて表にする 2.左端から淳に、そのコインより右にあり、かつ、そのコインの倍数であるコインをすべて裏表を変える 最終的に、コインが表を向いているコインの枚数の期待値を求める。 考え方…

4問中ABCが解けて60pt、2654位。

問題 プログラミングコンテストの部屋割りをする。 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…