問題 問題概要 省略 解法 dpで解いた。直線になっていれば即座にdpだろうなと思ったけど、円になっていたからすぐにわからず苦戦した。円になっている時に注意しなければならないことは、0オリジンで考えた場合、頂点0を選んだ場合、もし頂点n-1も選んだら、…

問題 問題概要 省略 解法 誤差の許容が大きいため、モンテカルロ法を使えばいいらしい。やっていることは、確率pで1枚目を選ぶとあるので、乱数で0~1までだし、pより小さければ1枚目を選び、そうでなければ、その他のものを等しい確率で選ぶというシミュレー…

問題 問題概要 頂点1からnまで達するために、必要な辺の長さの最小値。ただし、最小値は10の倍数 解法 大まかな方針として、必要な辺の長さを求めるので、Xcm以下の辺の長さだけでunion-findを使いグラフを形成して、1からnに達するか(同じ連結成分に含まれ…

問題 問題概要 木の直径を求める。 解法 木の直径を求めるアルゴリズム。 適当な頂点から最も遠い頂点xを選び、さらに、xから最も遠い頂点yを選ぶ。xとyの距離が木の直径となる。 ミス 直径は初めて。 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #incl</queue></vector></algorithm></iostream>…

問題 問題概要 ２次元累積和。 解法 このサイトを参考にした。 paiza.hatenablog.com 白か黒をマイナスの数字として扱うことで、２次元累積和を用いて計算することができる。やり方は、まず、横方向の累積和を取り、次は、それを縦方向に累積和をとる。この…

問題 問題概要 けんけんパーが何通り考えられか。 解法 dpで解いた。dp[i][j] := i番目まで考えて、j回連続ケンをした時の場合の数を入れて、ループで回した。漸化式は、何回ケンを連続で行っているかによって、場合分けした。 ミス すんなり行けた。 コード…

問題 問題概要 省略 解法 参考サイト imulan.hatenablog.jp 上のサイトを見たらだいぶわかった。 ダブリングと２分探索を使うらしい。蟻本の最後の方にもかいてあった。 int now = a; for (int i = 19; i >= 0; --i){ if(nx[i][now] < b){ now = nx[i][now];…

問題 問題概要 省略 解法 dpでとく。dp[i][j][k] := x[i]まで見て、選んだ数がj個で、合計値がkの時の場合の数 として、漸化式を立てて、ループを回して計算し、dp[n - 1][j][j * a]の和を取れば回答となる。 ミス 特になし。 コード #include <iostream> #include <cstdio> us</cstdio></iostream>…

問題 問題概要 省略 解法 単純に全ての状態を全探索すると、2nで無理。 dpで解きました。状態を決めるために、何文字目までで'('が何文字あり、最後に反転させた位置が同じであれば、同じ状態とみなせると考えた。 dp[i][j][k] := s[i]文字目まで見て、'('が…

問題 問題概要 省略 解法 helloworldと並べるが、それに含まれていない文字は全く気にしなくていい。d, e, h, r, wについては、helloworldの文字の中で、一部分しか出てこないので、すべて連続しておけばいい。考えるのは、lとoである。ともに、hellowoldの…

問題 問題概要 そろばんの一列でいくつ数得られる? 下の制約強化版 mmxsrup.hatenablog.com 解法 そろばんの上の玉がy、下がxとすると、数得られる数は、 (x + 1)y + x -(1) という式で表されて、 条件から、 x + y = n -(2) という式も導かれるので、 yを消…

問題 問題概要 そろばんの一列でいくつ数得られる? 解法 そろばんの上の玉がy、下がxとすると、数得られる数は、 (x + 1)y + x -(1) という式で表されて、 条件から、 x + y = n -(2) という式も導かれるので、 yを消去すると求める答えは、下の式が最大とな…

問題 問題概要 省略 解法 分になおして計算するだけ。ただ引くだけだとおかしくなるので、後半の時間の方が小さい値の場合、時間に+24時間をして、単純に引くことができるようにした。 ミス (h1 == h2 and m1 > m2)この時を忘れていて、1wa コード n = input…

問題 問題概要 省略 解法 まず、穴が2つあることがわかっているので、bfsでana1とana2にそれぞれ穴の座標を入れる。ana1とana2の全ての穴に対して、それぞれの穴をつなげる時に退ける壁の数を求め、それらの最小値が 答えとなる。 ミス なし。 コード #inclu…

問題 問題概要 お菓子に１ミリずつ切り目があり、切れ目ごとに切るためのコストが異なる。コストを最小にして、お菓子を半分ずつに分ける方法は。 解法 dpでとく。 dp[i][j][k] := (お菓子の長さがiでAさんの文がjの時で次ににkさんがお菓子をもらう時の切断…

問題 問題概要 複数のスタート場所があり、地点までの最短距離を求める。 解法 まず、ダイクストラを利用して、店から他の地点までの最短距離を入れる。このときの店というのは複数ある場合があるので、一番近い店からの距離を求めなければならない。最短距…

問題 問題概要 期待値の線形性を使う問題。 期待値の線形性を使う類題 No.144 エラトステネスのざる - yukicoder 解法 この問題のよくわからないところは、縦、横、斜めが独立でないので、どうやれば?て感じになる。ただ、どこか１列だけがビンゴする期待値…

問題 問題概要 省略。 解法 tmpに0からn-1まで入れて、それらを条件を満たすまで、シャッフルし続ける感じで解いた。WAだろうなと思ってひとまず書いてみたが、通った。条件を満たす場合が多いらしい。 ２部マッチとかで解けるみたいなので解きます。 ミス …

問題 問題概要 省略。 解法 幅優先探索。qに座標を入れて、numに何回目の動きなのかを入れてやった。 ミス 特になし。 コード #include <iostream> #include <vector> #include <queue> #include <cstdio> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int dx[8] </algorithm></cstdio></queue></vector></iostream>…

問題 問題概要 省略。 解法 動的計画法でやった。 dp[y座標][x座標][1つ飛ばしジャンプの回数] := (y, xに行くまでの最小の危険度)というdpを考えた。y座標が常に大きくなるので、DAGと考えるので、このようなやり方でやった。また、うまいやり方が思いつか…

問題 問題概要 nが与えられた時、1からn2まで使いn x nのますを縦横斜め全ての和が奇数になるように、埋めていく。 解法 縦横斜めの和が奇数になるのは、それらの一列に、奇数が奇数個ある時。この条件を満たすには、真ん中に十字形に奇数と配置し、４隅に階…

問題 問題概要 x座標上のnこの点が与えられる。それらの点の中から、他の点までの距離の合計が最小となるものを見つけろ。 解法 中央値は母集団の各要素から絶対距離の和が最も小さくするという意味で母集団を代表していると見ることができる(Wikipedia)とか…

問題 問題概要 チェスのキングのコマの位置が与えられる。次の手で何通りの進み方があるか。 解法 キングは周囲8方向に1マスずつ進めるので、周りがマスに囲まれていれば、8通りの進み方がある。ただし、隅っこの場合などは変わる。8方向に動かして、範囲内…

問題 問題概要 試合結果が渡されて、順位がどのように決まるかを求める問題。 解法 まず、試合結果がわからないものは無視して、与えられた試合結果のみを使い、トポロジカルソートをする。aチームが勝ち、bチームが負けた場合、b -> aのような形で辺を貼る…

問題 問題概要 高校数学で出てくる場合の数の問題。 解法 dpで解きました。(x,y)=(0,0)への行き方を１通りとして、(1,0)は(0,0)からの1通り、(0,1)は(0,0)からの1通りの方法で行くことができ、(1,1)は(0,1)と(1,0)から行く方法があり、(0,1)と(1,0)へ行く方…

問題 問題概要 与えられたグラフに対して、幅優先探索を使い、条件を満たした新たなグラフを表す隣接行列を作り、ダイクストラで最小コストを作る。 解法 与えられたグラフのままでは、多くの条件あり、そのままではダイクストラをすることができない。そこ…

問題 問題概要 省略 解法 今回の問題は毎回すべての城を調べていたら、TLEになってしまう。そこで、ポイントは、「n回目の波で崩れる城はn - 1回目の波で崩れた城の周囲8方向の城に限られる」ということである。そこで、まずは、城が存在する座標をq1に入れ…

問題 問題概要 文字列bの連続した文字列が文字列aの部分文字列(連続していなくてもよい文字列)で作れる時の、最長の長さを調べる。 解法 連続文字列の先頭の文字を決め(b[i])、その文字が文字列aを先頭から見ていき、存在するかを調べ、文字存在するなら(a[k…

問題 問題概要 該当する文字列がいくつ存在するか求める問題。 解法 与えれた文字列(s)にIOIOI等の文字列があるかを調べる。sの先頭から調べていき、Iの文字であれば、その位置から、2*n + 1文字を切り取り、該当する文字(ans)と一致するからを調べている。…

問題 問題概要 ３つの辺の長さが与えられる。それを使って、最も辺の長さの合計が長い三角形の辺の長さを求めさい。 解法 三角形の成立条件を使えばいい。成立条件を満たすのなら３辺の和そのものが答えとなり、条件を満たさないなら、最大辺を短くして、ギ…