読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.198 キャンディー・ボックス2

問題 問題概要 省略 解法 それぞれの箱にいれる数を決めると、作業の回数が決まる。求めるものは作業回数の最小値。すこし考えると、仮にそれぞれの箱にx個入れた時が答えとなるとすると、x個以下でそろえようとしたときは、作業回数は増え、またx個以上でそ…

yukicoder No.180 美しいWhitespace (2)

問題 問題概要 省略 解法 与えられた関数は、下に凸の関数となるので、最小値は3分探索で探すことができる。 ミス よくわからんけど、rの大きさが大きすぎて、バグらした、3分探索を練習したい。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> </algorithm></vector></set></cstdio></iostream>…

yukicoder No.66 輝け☆全国たこやき杯

問題 問題概要 トーナメントで勝ち進んでいく確率。 解法 dpで解いた。 dp[i][j] := i回回目の試合にj番目のひとが勝つ確率 として、漸化式にそって、ループで値を埋めていく。漸化式は簡単で、 dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y] のように…

yukicoder No.58 イカサマなサイコロ

問題 問題概要 省略 解法 dpで解いた。 dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率 dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率 とおいて、漸化式でi=1からi=nまでループを回して埋めていった。 漸化式は単純で、いか…

yukicoder No.424 立体迷路

問題 問題概要 省略 解法 bfsで解いた。よくある、2次元座標上での迷路問題などで、ゴールまで行けるかの問題と同じようにやる。ただし、4方向への移動が高さの条件で制限されるので、それを確認すればよい。また、dyとdxを2倍して、2倍の距離の移動も同様に…

yukicoder No.423 ハムスター語初級(数詞)

問題 問題概要 省略 解法 2進数で表したときに、2倍すると、1桁左に移動するので、末尾に0をつければよい。すなわち、hamをつければいい。 ex1) 101(5) 1010(10) ex2) 111(7) 1110(14) 注意しなければならないのは、n=hamの時0なので、2倍しても0のまま。 ミ…

yukicoder No.124 門松列(3)

問題 問題概要 省略 解法 bfsで解いた。進める方向は、進もうとするマスと、現在のマスと過去のマスの3つが門松列をなしているとき。注意しなければならないのは、基本的な最短経路問題で使うbfsのように、座標のみを状態として最短距離をメモしていくと、解…

yukicoder No.123 カードシャッフル

問題 問題概要 省略 解法 がんばって実装しよう。 ミス なし。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int n, m; int main(void){ cin >> n >> m;</algorithm></vector></set></cstdio></iostream>…

yukicoder No.421 しろくろチョコレート

問題 問題概要 省略 解法 2部マッチングでできるのか、て感じ。公式解説を見ればわかる。実装はs,tを追加して、最大フローを求める感じで書いたもの。 ミス 制約が小さければ、bitDPでもできるぽい。グラフ問題に落とせるようにしたい。 コード #include <iostream> #i</iostream>…

yukicoder No.101 ぐるぐる!あみだくじ!

問題 問題概要 省略 解法 まず、1つ分で、どこからスタートしたら、どこに到達するかをメモしておき、そのあと、すべてのスタート時点に対して、何回で同じ位置に戻ってくるかを計算し、それらの最小公倍数を求めれば、答えとなる。 ミス なし。 コード #inc…

yukicoder No.140 みんなで旅行

問題 問題概要 省略。 解法 解説スライド見るとわかりやすい。 kmjp.hatenablog.jp スターリング数は、S(n, k) 区別できるn個のものを区別できないkグループに分類する方法の場合の数を漸化式と表すことができる。 S(n, k) = s(n - 1, k - 1) + k * S(n - 1,…

yukicoder No.193 筒の数式

問題 問題概要 省略。 解法 ほぼ実装問題。文字の長さは短いので、数字で始まり終わる1周分の文字列をすべて全探索すればいい。このときに、sを2倍に伸ばしておくと、前に戻ってくる処理を簡単に省くことができる。あとは、前から見ていき、数字の部分num…

yukicoder No.277 根掘り葉掘り

問題 問題概要 木の上での最短経路(根からの距離、葉からの距離)を求める問題。 解法 根から葉、葉から根へ向けて、bfsをすればいい。その時に注意することはbfsで次に進む方向を決めるときに、来た方向に戻ってしまうと、正確な値が求まらないので、queueの…

yukicoder No.154 市バス

問題 問題概要 バスが通るのを記録する。それぞれの系統に対して、最終1つ前のバスと最終のバスはほかのバスとその他のバスをそれぞれ異なるように記録している。その記録が条件に沿ったものかを判定する問題。 解法 それぞれの系統のバスは、WGRの順に出て…

yukicoder No.118 門松列(2)

問題 問題概要 門松列になる組み合わせを求める問題。 解法 この問題の注意点は並び順が違っても、同じ竹の組み合わせなら同じとカウントするという点である。よって、門松列になる竹の組み合わせが何通りあるかを求めるには、3本の竹が異なるようにとるこ…

yukicoder No.67 よくある棒を切る問題 (1)

問題 問題概要 条件を満たす最大の値を求める問題。 解法 求める棒の長さは条件を満たす最大の値であり、その値より棒の長さを短くしても条件を満たすが、それより大きくすると条件を満たさなくなる。よって、このような場合は、二分探索をして効率よく求め…

yukicoder No.57 ミリオンダイス

問題 問題概要 期待値問題。 解法 期待値の線形性を使うと簡単にできる問題。 ミス 数学ガール読みます。 コード #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>…

yukicoder No.38 赤青白ブロック

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

yukicoder No.50 おもちゃ箱

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

yukicoder No.5 数字のブロック

問題 問題概要 省略 解法 幅が小さいものから貪欲に選んでいけばいい。 ミス なし。 コード #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>…

yukicoder No.7 プライムナンバーゲーム

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

yukicoder No.361 門松ゲーム2

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

yukicoder No.153 石の山

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

yukicoder No.103 素因数ゲーム リターンズ

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

yukicoder No.102 トランプを奪え

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

yukicoder No.37 遊園地のアトラクション

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

yukicoder No.34 砂漠の行商人

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

yukicoder No.20 砂漠のオアシス

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

yukicoder No.151 セグメントフィッシング

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

yukicoder No.27 板の準備

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

yukicoder No.177 制作進行の宮森あおいです!

問題 問題概要 最大フロー. 解法 sから作画に与えられたjで辺を貼り、作画から条件を満たす監督に、辺の流量無限大で流し、監督からtへ与えられた、cで辺を貼る.このグラフを使って、 最大フローを求めればいい. ミス なし. コード #include <iostream> #include <algorithm> #inc</algorithm></iostream>…

yukicoder No.59 鉄道の旅

問題 問題概要 区間の和と1つの要素に値を加算減算を拘束にできればいい. 解法 BITを使った. BITは -区間の和 -1つ要素に値を加える ことができるデータ構造. 今回の問題では積荷をBITで管理した. w>0の時はw以上の重さのものがk個より少なければ、その積荷…

yukicoder No.230 Splarraay スプラレェーイ

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 この問題とほぼ同じことをするだけ. mmxsrup.hatenablog.com 変更するのは以下の3点 (1)遅延情報の適用方法 -segは区間におけるAとBの色の数を…

yukicoder No.318 学学学学学

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 さっぱりわからなかった。蟻本に書いてある、segtreeで範囲に対する最小値を求めるRMQは変更する値が1つなので、値を変更するのに(logn)で済む…

yukicoder No.13 囲みたい!

問題 問題概要 閉路検出 解法 考え方が悪かった。閉路検出のためにある始点から初めて、1周してその点に戻るかを判別すればいいなと思い、dfsもどきのbfsみたいなのを書き出したが完全に悪かった。閉路検出は「ある始点からスタートして、探索方向はfrom以外…

yukicoder No.398 ハーフパイプ(2)

問題 問題概要 省略 解法 dpでできるみたい。 dp[i][j][k][l] := i番目まの審査員まで考えて(0origin)、最小値がj、最大値がkで合計がlの時の場合の数。としてループを回せばいい。言われればそうだなという感じ。 最大最小と合計があれば、状態を区別するこ…

yukicoder No.324 落ちてた閉路グラフ

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

yukicoder No.173 カードゲーム(Medium)

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

yukicoder No.168 ものさし

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

yukicoder No.314 ケンケンパ

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

yukicoder No.73 helloworld

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

yukicoder No.72 そろばん Med

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

yukicoder No.71 そろばん

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

yukicoder No.70 睡眠の重要性!

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

yukicoder No.157 2つの空洞

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

yukicoder No.242 ビンゴゲーム

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

yukicoder No.241 出席番号(1)

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

yukicoder No.240 ナイト散歩

問題 問題概要 省略。 解法 幅優先探索。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>…

yukicoder No.19 ステージの選択

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

yukicoder No.260 世界のなんとか3

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