問題 問題概要 期待値問題。 解法 期待値の線形性を使うと簡単にできる問題。 ミス 数学ガール読みます。 コード #include <iostream> #include <cstdio> #include <set> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int </algorithm></set></cstdio></iostream>…

問題 問題概要 条件を満たす最長の文字列の長さを求める問題。 解法 白のブロックをいじることはないので、赤と青のブロックさえいじればいい。ブロックのいじりかたも、そのブロックを使用するか、しないかだけであり、いじらなければならないブロックの総…

問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 すぐbitDPだろうなというのはわかる。ただ、どうやって、実装するかわからん。箱を使う最小値を求めればいいのだから、箱は大きいものから使用していけばいい…

問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 区間が始まる点を+1、区間が終わる点を-1することで、[a, b]をインクリメントする必要がなくなり、最後に一度だけ、全体をなめるだけで、最大数がわかる。 ミ…

問題 問題概要 LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。 解法 全探索で、やろうと思うと、2k(k=30)でTLE?? ただし、2分探索をしていく途中で、 (T …

問題 問題概要 省略 解法 dpで解いた。dp[i][j] := i回数字を引いて、jになるなら、true、とおいてループで回して埋めていった。 dp[i][j+k]=trueならdp[i][j]=trueとなるので(ただし、jはngでない)、このことから漸化式らしきものが立てられる。 ミス nがい…

問題 問題概要 省略 解法 幅が小さいものから貪欲に選んでいけばいい。 ミス なし。 コード #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int main(void){ int l, n; cin </algorithm></vector></cstdio></iostream>…

問題 問題概要 省略 解法 grundy数をメモ化再帰で求めることにした。 grundy数の求め方だが、 grundy数は -負けの状態で0 -遷移先のGrundy数に含まれない最小の整数 なので、状態遷移先を列挙していき、最小のgrundy数を求めに行けばいい。今回の問題は、nか…

問題 問題概要 省略 解法 grundy数をメモ化再帰で求めることにした。 この問題は竹が分裂していくが、竹が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。 grundy数の求め方だが、…

問題 問題概要 省略 解法 grundy数をメモか再起で求めることにした。 この問題は山が分裂していくが、山が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。 grundy数の求め方だが、…

問題 問題概要 省略 解法 Mが与えられ、その中で、同じ素因数であれば1回以上2回まで同時に割ることができる。よって、それぞれのMの中でさらに素因数ごとに山に分ける。そうすると、それぞれの山をmod3とった値がgrundy数となる。 mmxsrup.hatenablog.com …

問題 問題概要 省略 解法 grundy数とNimの勉強しました. 参考サイト pekempey.hatenablog.com d.hatena.ne.jp 上のサイトを参考にgrundy数を、１つの山について考えると、 残り枚数:0 1 2 3 4 5 grundy:0 1 2 3 0 1 のような関係になっている。 よって、n1,n…

問題 問題概要 省略 解法 dpで解いた。dp[i][j] := i番目のアトラクションまで見て、待ち時間の総和がjの時の満足度の最大値、をループで回して埋めていった。やり方は、個数制限なしナップザック問題を解くイメージ。実装方法はcntでi番目のアトラクション…

問題 問題概要 省略 解法 2次元座標のなかで、スタートからゴールまで最短距離で行けるかを判定する問題。最短経路を求めるのだから、bfsで解けばいい。ただし、よくある迷路のような問題で最短距離を求める問題は、状態が座標のみでよいが、今回は残りの体…

問題 問題概要 省略 解法 スタートからゴールにたどりつく方法が、スタートからゴールまでオアシスを使わずに行くか、オアシスを利用して、ゴールに行くかの2通りである。まず、スタートからゴールまでオアシスを使わずに、ゴールに行けるかを調べる。調べ方…

問題 問題概要 HxWの２次元マスの中で考えられる3x3のマスを考え、それぞれの3x3のマスの中に黒のマスがいくつあるかを調べる。 解法 HxWのマスを持つことはできない。また制約を見ると、ほとんどの部分が白のマスであり、黒の部分は少数である。よって、与…

問題 問題概要 省略。 解法 bit全探索。sの長さがnのとき、n-1個の場所に+を入れることができるので、+を入れる場所を2n-1通り全部試せばいい。実装方法は、bitを使い、1であればその部分に+を入れて、0であればその部分に+を入れない。例えば、s=125の場合…

問題 問題概要 省略。 解法 書かれていた通りに、シミュレーションをする。 ミス なし コード #include <iostream> #include <cstdio> using namespace std; string s[3]; int main(void){ cin >> s[0] >> s[1] >> s[2]; int now = 0; while(1){ if(s[now].size() == 0){ if(no</cstdio></iostream>…

問題 問題概要 省略。 解法 台形の面積の公式を利用。 ミス なし コード #include <iostream> #include <cstdio> using namespace std; int main(void){ int a, b, h; cin >> a >> b >> h; printf("%d\n", (a + b) * h / 2); return 0; }</cstdio></iostream>

問題 問題概要 省略。 解法 しゃくとり法を使った。右を進めていき、条件を満たしたら、左を進めていく、最小の長さが出るようにしゃくとり法を使う。mapで全ての文字が、[l, r]に含まれているかを判定している。 ミス なし コード #include <iostream> #include <cstdio> #inc</cstdio></iostream>…

問題 問題概要 省略。 解法 行、列、別々に、何個ずつ埋まっているかを見て、それを使い、計算すればいい。行、列が埋まるごとに、小さくなっていく。 ミス なし コード #include <iostream> #include <cstdio> #include <set> typedef long long ll; using namespace std; #define </set></cstdio></iostream>…

問題 問題概要 省略。 解法 数字をソートして、一番前と一番後ろから順にとっていく。 ミス なし コード #include <iostream> #include <algorithm> #include <cstdio> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int main(void){ int n; cin >> n; vector<pair<int, int> </pair<int,></vector></cstdio></algorithm></iostream>…

問題 問題概要 省略。 解法 よくあるのは、used[y][x]で(x, y)へ行くことができたことをメモしてbfsをやったりしていたが、今回は、何回壁を壊して、(x, y)へ到達できたかの情報も必要なので、used[y][x][k]として、k=0なら壁を壊さず、(x, y)へ到達できてお…

問題 問題概要 省略。 解法 領域からでたら、ベクトル(dx, dy)の方向を変更して、進むような形で、実装した。 ミス こういう問題どうとこうか迷う。 コード #include <iostream> #include <string> #include <queue> #include <cmath> #include <cstdio> using namespace std; #define rep(i,n) for(i</cstdio></cmath></queue></string></iostream>…

問題 問題概要 省略。 解法 sからgまでの経路が存在するとき、答えを小さくすれば、条件を満たし、答えを大きくしていくと、条件を満たさなくなる。そのため、答えを2分探索していけばよいことになる。また、ある地点まで、最短でいったときが、そのますの明…

問題 問題概要 省略。 解法 区間に値を足して、区間の和がわかればいいので、segtree使えばいいぽい。けど、 魚を加えるO(1) 区間の数を数得るO(n) 1マスずらすO(n) よって、O(q * n)でできる。ギリ通るかも。 ミス 平衡二分探索木の練習だったけど、スライ…

問題 問題概要 省略。 解法 モジュール使うと楽だね。 ミス なし。 コード import datetime y, m, d = map(int, raw_input().split('/')) t = datetime.date(y, m, d) while t.year % (t.month * t.day) != 0: t += datetime.timedelta(1) print"%04d/%02d/%…

問題 問題概要 s->iへ到達できるか。ただし、通れる頂点に制約あり。 解法 思いついたのは、逆からunion-find。頂点iに行けるかを見る場合、i以上の頂点を使い、sからiへたどり着けるかを見れば良いので、i=n-1からi=0の順に調べ、そのつど、追加できる辺を…

問題 問題概要 省略 解法 1つだけのものだけで、kこ買うパターン セットだけで、kこ以上買うパターン 1つとセットでkこ買うパターン の3つを試して、それらの最小値を出せばいい。 ミス なし コード #include <iostream> using namespace std; typedef long long ll; i</iostream>…

問題 問題概要 個数制限なしナップザック問題。 解法 dp[x] := ita[0]~ita[2]を使い、長さxの板を作るのに、必要な最小の板の枚数と置き、ループで回して埋めていった。 したのは、同じものを選ぶ時に、ループを回して、取れる数まで同じものを取るようにし…