yukicoder
問題 問題概要 省略。 解法 解説スライド見るとわかりやすい。 kmjp.hatenablog.jp スターリング数は、S(n, k) 区別できるn個のものを区別できないkグループに分類する方法の場合の数を漸化式と表すことができる。 S(n, k) = s(n - 1, k - 1) + k * S(n - 1,…
問題 問題概要 省略。 解法 ほぼ実装問題。文字の長さは短いので、数字で始まり終わる１周分の文字列をすべて全探索すればいい。このときに、sを２倍に伸ばしておくと、前に戻ってくる処理を簡単に省くことができる。あとは、前から見ていき、数字の部分num…
問題 問題概要 木の上での最短経路(根からの距離、葉からの距離)を求める問題。 解法 根から葉、葉から根へ向けて、bfsをすればいい。その時に注意することはbfsで次に進む方向を決めるときに、来た方向に戻ってしまうと、正確な値が求まらないので、queueの…
問題 問題概要 バスが通るのを記録する。それぞれの系統に対して、最終１つ前のバスと最終のバスはほかのバスとその他のバスをそれぞれ異なるように記録している。その記録が条件に沿ったものかを判定する問題。 解法 それぞれの系統のバスは、WGRの順に出て…
問題 問題概要 門松列になる組み合わせを求める問題。 解法 この問題の注意点は並び順が違っても、同じ竹の組み合わせなら同じとカウントするという点である。よって、門松列になる竹の組み合わせが何通りあるかを求めるには、３本の竹が異なるようにとるこ…
問題 問題概要 条件を満たす最大の値を求める問題。 解法 求める棒の長さは条件を満たす最大の値であり、その値より棒の長さを短くしても条件を満たすが、それより大きくすると条件を満たさなくなる。よって、このような場合は、二分探索をして効率よく求め…
問題 問題概要 期待値問題。 解法 期待値の線形性を使うと簡単にできる問題。 ミス 数学ガール読みます。 コード #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だろうなというのはわかる。ただ、どうやって、実装するかわからん。箱を使う最小値を求めればいいのだから、箱は大きいものから使用していけばいい…
問題 問題概要 省略 解法 幅が小さいものから貪欲に選んでいけばいい。 ミス なし。 コード #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通りである。まず、スタートからゴールまでオアシスを使わずに、ゴールに行けるかを調べる。調べ方…
問題 問題概要 省略。 解法 区間に値を足して、区間の和がわかればいいので、segtree使えばいいぽい。けど、 魚を加えるO(1) 区間の数を数得るO(n) 1マスずらすO(n) よって、O(q * n)でできる。ギリ通るかも。 ミス 平衡二分探索木の練習だったけど、スライ…
問題 問題概要 個数制限なしナップザック問題。 解法 dp[x] := ita[0]~ita[2]を使い、長さxの板を作るのに、必要な最小の板の枚数と置き、ループで回して埋めていった。 したのは、同じものを選ぶ時に、ループを回して、取れる数まで同じものを取るようにし…
問題 問題概要 最大フロー. 解法 sから作画に与えられたjで辺を貼り、作画から条件を満たす監督に、辺の流量無限大で流し、監督からtへ与えられた、cで辺を貼る.このグラフを使って、 最大フローを求めればいい. ミス なし. コード #include <iostream> #include <algorithm> #inc</algorithm></iostream>…
問題 問題概要 区間の和と1つの要素に値を加算減算を拘束にできればいい. 解法 BITを使った. BITは -区間の和 -1つ要素に値を加える ことができるデータ構造. 今回の問題では積荷をBITで管理した. w>0の時はw以上の重さのものがk個より少なければ、その積荷…
問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 この問題とほぼ同じことをするだけ. mmxsrup.hatenablog.com 変更するのは以下の3点 (1)遅延情報の適用方法 -segは区間におけるAとBの色の数を…
問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 さっぱりわからなかった。蟻本に書いてある、segtreeで範囲に対する最小値を求めるRMQは変更する値が1つなので、値を変更するのに(logn)で済む…
問題 問題概要 閉路検出 解法 考え方が悪かった。閉路検出のためにある始点から初めて、1周してその点に戻るかを判別すればいいなと思い、dfsもどきのbfsみたいなのを書き出したが完全に悪かった。閉路検出は「ある始点からスタートして、探索方向はfrom以外…
問題 問題概要 省略 解法 dpでできるみたい。 dp[i][j][k][l] := i番目まの審査員まで考えて(0origin)、最小値がj、最大値がkで合計がlの時の場合の数。としてループを回せばいい。言われればそうだなという感じ。 最大最小と合計があれば、状態を区別するこ…
問題 問題概要 省略 解法 dpで解いた。直線になっていれば即座にdpだろうなと思ったけど、円になっていたからすぐにわからず苦戦した。円になっている時に注意しなければならないことは、0オリジンで考えた場合、頂点0を選んだ場合、もし頂点n-1も選んだら、…
問題 問題概要 省略 解法 誤差の許容が大きいため、モンテカルロ法を使えばいいらしい。やっていることは、確率pで1枚目を選ぶとあるので、乱数で0~1までだし、pより小さければ1枚目を選び、そうでなければ、その他のものを等しい確率で選ぶというシミュレー…
問題 問題概要 頂点1からnまで達するために、必要な辺の長さの最小値。ただし、最小値は10の倍数 解法 大まかな方針として、必要な辺の長さを求めるので、Xcm以下の辺の長さだけでunion-findを使いグラフを形成して、1からnに達するか(同じ連結成分に含まれ…
問題 問題概要 けんけんパーが何通り考えられか。 解法 dpで解いた。dp[i][j] := i番目まで考えて、j回連続ケンをした時の場合の数を入れて、ループで回した。漸化式は、何回ケンを連続で行っているかによって、場合分けした。 ミス すんなり行けた。 コード…
