問題 試合結果「A-B」が与えられ、Aは自分の点数、Bは相手の点数になっている。 今、2つの試合運びを考える。 「stress-free」な試合運びとは、最初に1-0になって、そのあとは、A-Bになるまで常に相手に点数が勝ち続けた状態で試合が進むことをいう。 「stre…

問題 distinctなN個の文字列が順番に与えられる。 自動補完機能のために、与えらえた文字列毎に1文字以上のprefixを登録しておかなければならないが、以下の条件を満たす必要がある。 i番目に与えられた文字列の登録するprefixは、 ・その文字列全体 または …

問題 整数Xを素因数分解したときの素因数の種類数をw(X)とする。 整数A〜Bのなかで、w(X)=Kとなる整数の数がいくつかるか？2 1 考え方 2が素因数として含まれる＝2の倍数 3が素因数として含まれる＝3の倍数 5が素因数として含まれる＝5の倍数 ・・・ である…

問題 N個の遺跡isekiがあり、iseki[i]にはl[i]〜r[i]までの(宝石番号の連続した)宝石がある。 遺跡に訪れると、上記の宝石をすべて入手し、報酬としてs[i]だけ得られる。 しかし、宝石はM種類あり、すべてそろえてしまうと、魔王が復活してしまう。 魔王が復…

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

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

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

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

問題 木が与えられる。 ある頂点を取り除いてできる連結成分の最大のサイズを各頂点について計算する。 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位。

問題 (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だけ通した。