問題 高さの違うN個の積み木が並べてある。 隣り合う2つを交換する操作を何回か繰り返して、h_1 h_i+1 > ... > h_Nとなるようにしたい。 そのようにする最小交換回数を返す。N 積み木の高さ 考え方 高さの小さい積み木から左右のどちらかにその積み木より高…

問題 各頂点が整数点の多角形と線分Lが与えられる。 多角形を線分が分断し複数の多角形に分割するとき、分割後の多角形の数を返す。 線分は多角形をちゃんと分割するように与えられる。 考え方 よく考えると(←)、「線分によって分割される切断面の数＋1」が…

問題 n頂点の有向グラフが与えられ、各頂点にはアルファベット1文字が書かれている。 任意頂点から進んで、アルファベットを順番に回収して長さkの文字列を作る。 頂点にたどり着いたとき、アルファベットを回収してもしなくてもよい。 このとき、可能な辞書…

ISUCON4に初参加した。 予選通過ならずっぽいけど、いろいろ勉強になったので、記録しておく(だらだら書き)。 チーム aomoriringoさん、matsu4512さん、自分。 おおよその役割分担は、 aomoriringo : アプリ周り中心 matsu4512 : DB周り中心 自分 : その他 …

問題 無向木が与えられる。 クエリとして、頂点a,bが与えられるとき、aとbに辺を追加したら閉路ができる。このとき、閉路を形成する辺の数を返す。V Q 考え方 Qが10^5まであるので、O(n)な解法だと間に合わない。 頂点aから頂点bまでの距離がわかっていれば…

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

内容 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位。