問題 問題概要 省略 解法 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…

問題 問題概要 期待値の線形性を使う問題。 期待値の線形性を使う類題 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>…

問題 問題概要 強連結成分の分解を利用する問題。強連結成分を１つの頂点に置き換えて、DAGにして、トポロジカルソートをする。 解法 N個のステージを頂点と考える。(先に指定しておくと良いステージ) -> (ステージ)の向きに有向辺をはっていき、有向グラフ…

問題 問題概要 桁dpの問題 類題の私のメモ mmxsrup.hatenablog.com 解法 dp[i][j][k][l][m]という配列を作り埋めていく。 整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 k=1の時…

問題 問題概要 桁dpの問題 解法 dp[i][j][k][l]という配列を作りdpで埋めていく感じ。 整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 k=1の時はすでにi番目までに数字3を含んでい…

問題 問題概要 漸化式で表されている数列の第n項を求める問題。 解法 3項間漸化式を解いて、一般項を求めた。一般項は a(k) = 4*(3/4)k (k >= 0) となるので、これを利用した。 ミス 高校数学忘れるね。 コード #include <iostream> #include <cstdio> #include <cmath> using namespa</cmath></cstdio></iostream>…

問題 問題概要 門松行列の判定を複数回行う問題。 解法 7つの数字が与えられる。それを並び替えることによって、左から順に3つずつの数字を見て、それが門松列になっているかを調べる。それを左から右へ一つずつずらして、すべて調べ、すべての場合において…

問題 問題概要 数字を並び替えた時に、条件を満たし、もっとも得点を獲得できる時の得点を求める。 解法 数字の数の最大値が14である。数字をすべて並び替える解法だと、計算量が(n!)になるので、TLE。そのためには計算量を(2n)にしなければならない。そこで…

問題 問題概要 数列の隣合う数字の間隔が素数で表されるとき、すべてでいくつの数列が構成できるか求める問題。 解法 入力が5 12の時を考える。 素数2の時 0 2 4 6 8 1 3 5 7 9 2 4 5 8 10 3 5 7 9 11 4 6 8 10 12 上のような4つの数列が存在する。 このとき…

問題 問題概要 隣合う二点間の距離がすべて等しいかを見分ける。 解法 x座標がソートされていないのでまずはソートする。そのあと、順番に隣り合う区間の距離が等しいかを見ていけばいい。私は、x0とx1の距離を出しておいて、その値と他の隣り合う2点間の距…

問題 問題概要 時計の針が何時を指しているかを求める問題。 解法 modを取って計算していく。時計の針の{"XII", "I","II","III","IIII","V","VI","VII","VIII","IX","X","XI"}を先頭から順にmod12を利用して、0,1,2.......,11とする。これをさらに、T時間後…

問題 問題概要 省略 解法 forで回す。 ミス 特になし。 コード #include <iostream> #include <cstring> using namespace std; int main(void){ string s, ans; cin >> s; for (int i = s.size() - 1; i >= 0; --i){ if(s[i] == '>') ans += '<'; else ans += '>'; } cout << an</cstring></iostream>…

問題 問題概要 チェビシェフ距離の最大のものを探す 解法 表を左上から右下へ、右下から左上へ、右上から左下へ、左下から右上へチェビシェフ距離を動的計画法で埋めていった。例えば、左上から右下へ埋めていく場合を考えると、現在見ているマスの左下、左…

問題 問題概要 数字の一か所を入れ替えて、最も大きい数字を求める。 解法 数字を文字として扱う。文字列の一か所を入れ替えたものを全探索している。出来上がった文字列をstring型のvector配列にいれて、ソートする。数字だけじゃなくて、文字列もソートで…

問題 問題概要 サイコロを降って、目の合計がK以上になるサイコロを振る回数の期待値を求める問題。 解法 漸化式を用いて動的計画法で解く。 ミス 漸化式をすこし間違えた。dp[i] := (これまでの目の合計が i のとき、合計が k になるまでに降ることになる回…

問題 問題概要 文字列を数式ととらえて、計算していく、構文解析の問題。 解法 *,+が出てくるまで、いくつ数字が並んでいるかを確認した後、数字の並びの前に出ていた記号によって、数字を足すのか、かけるのかの処理を行えばいい。ただ、実装が少しめんどく…

問題 問題概要 文字列の中で最も左のもの、またはもっとも右の文字を任意の順番で取り出していき、取り出した順番で並べる。何種類の文字列が作れるか。 解法 全探索する。左または右から取る順番をbitを用いて実装した。今回はbit列iのpos番目のbitが立って…

問題 問題概要 省略 解法 dp問題。 ミス オーバーフローに注意。dp[何番目の変数か][合計値] := (整数の組みの個数) とおく。変数を一つずつ増やしてみていく。漸化式はdp[i][j] += dp[i - 1]=%20k">j - kとなる。それぞれの変数は0からnまでとるので、kを0…

問題 問題概要 省略 解法 bitDP。どの商品をすでに購入したかを示す集合を要素として持ち、dpをすればいい。集合が決まっている時の、支払う金額の最小値を求めておけば、その集合内でどの順番で商品を買ったかは関係ないので、dpで解ける。 dp[mask] := (ma…

問題 問題概要 省略 解法 誤差を全く許さない問題。このような時は整数型で計算する。そのためには、1.08倍をするのではなく、108倍をすればいい。ここで100で割るのではなく、下から２桁目に小数点をつけて表示すればいい。 ミス 特になし。 コード #includ…

問題 問題概要 省略 解法 多く進んでもいいのだから、割り切れればそのままでいいし、割り切れなければ、+1すればいいことになる。 ミス 特になし。 コード #include <iostream> using namespace std; int main(void){ int a, b; cin >> a >> b; int ans = b / a; if(b</iostream>…

問題 問題概要 省略 解法 簡単に漸化式がたつ、dp。dp[i] := (iマスに行く方法のパターン)とおくと、漸化式は、dp[i] = dp[i - 1] + dp[i - 2]となる。これは、iマス目に行くには、i-1マス目から1で進む、または i-2マス目から2で進むのどちらかであるっこと…

問題 問題概要 省略 解法 まず、任意の２点間の距離の最小値を求めておく。その後、滞在する２点を全探索で全て調べる。 全探索で dist[0][i] + dist[i][j] + dist[j][n - 1] + s[i] + s[j] の最小値を求めればいい。 ミス 特になし。 コード #include <iostream> #inc</iostream>…

問題 問題概要 省略 解法 少し、考えると、平均を最大にするのは、最も大きいものが１つだけ含まれる集合であり、平均を最小にするのは、最も小さいものが１つだけ含まれる集合のときである。 ミス 特になし。 コード #include <iostream> #include <algorithm> #include <vector> using n</vector></algorithm></iostream>…