ferinの競プロ帳

競プロについてのメモ

SRM

SRM699 div1 easy OthersXor

考えたこと 桁別に独立に見てよさそう (0, 0, 0, 1, 1, 1) みたいなのについて考えてみる 0の個数が奇数なら0のところを1に、1のところを0にすれば条件を満たしそう 逆にこれ以外の構成ある? 0のところに0が当てはまっているものと1が当てはまっているもの…

SRM696 div1 easy Gperm

考えたこと 頂点集合はもてないけど辺集合は持てるねみたいな感じのbitDPっぽさ dp[S] = (Sに含まれる辺は両端が赤い頂点な辺) とかをしたくなる どの辺の両端を赤くしたら他の辺で赤くならないといけない辺があったりいろいろ依存関係がある 1-2,1-3,1-4,1-…

SRM695 div1 easy BearPasswordLexic

考えたこと 辞書順最小と言われたので'a'を置けるなら置くみたいなのを書きたくなる 連続している'a'が多すぎて与えられた条件を満たせないときは'b'を置くしか無い {6,3,0,0,0,0} とかが与えられると "aabbaa" をつくれるけど上の規則だけだと "aabaab" が…

SRM693 div1 easy BiconnectedDiv1

考えたこと 二重連結グラフをよく知らなかったのでググる 橋がないことと同値っぽい 最小全域二重連結グラフみたいな問題 グラフの形がかなり特徴的 頂点1,2が繋がるパスは 1-2,1-0-2,1-3-2 の3通りっぽい どの頂点も次数が2以上あれば条件を満たしていそう …

SRM691 div1 easy Sunnygraphs

考えたこと 0,1につながってない頂点はどう選ぼうが全く影響しなさそうなので2^(この頂点数)を掛けるとよさそう 実際は無向辺だけど有向辺として考えた方がよさそう サイクルの部分はどう選択しようが必ず連結性が保たれているっぽい 0と1が連結かどうかで場…

SRM689 div1 easy ColorfulGarden

考えたこと 互い違いにおいていくのが一色を多く置く方法っぽい 一色でn個より多くあるのを条件を満たすようには置けない 逆に全部n個以下なら適当に互い違いにおいていくだけで構成できる 割とすぐ思いつけた ソースコード #include <bits/stdc++.h> using namespace std; </bits/stdc++.h>…

SRM688 div1 easy ParenthesesDiv1Easy

考えたこと 文字列長が1000なのに操作回数10回の制限でよくわからない とりあえず実験するけどよくわからない 括弧列を+1/-1に置き換えるやつをしてみる +1/-1の累積和で-1になったところがあったらそこを1回は操作しないとだめ 操作しないといけない場所が…

SRM687 div1 easy AlmostFibonacciKnapsack

考えたこと ナップザックDPの復元とか考えつつ問題文を読むと制約的に論外 上から貪欲にとっていくやつを考える 7とかが3+4でつくれるけど先に6を取っちゃうとだめ 漸化式の性質を何かうまく使う…? とりあえず漸化式の要素を順番に書いていってみるけどよく…

SRM686 div1 easy BracketSequenceDiv1

考えたこと 開括弧を選んでそれに対応する閉じ括弧のパターンが何通りあるか数えるみたいなので考える 正しい括弧列ならば開括弧の数は(括弧列の長さ/2)になるはず 与えられる括弧列の長さが最大40なのでその半分なら開括弧の選び方を全列挙できる もし開括…

SRM685 div1 easy MultiplicationTable2

考えたこと ある数字iを削除できるのは(j$k) == iとなるj,kが存在しない事みたいな気持ちになる 削除する対象の数字を探索するのにO(n)、削除判定O(n^2)で繰り返すのにO(n)で間に合いそうという気持ちになる 数字が削除できるならするを繰り返すコードを書く…

SRM681 div1 easy FleetFunding

考えたこと つくる数を決め打ったときにそれを実現できるかについて単調性がありそうなのでにぶたんができそう 二分探索部分でO(log(nm)) 判定部分をどうすればいいか 区間と言われたので終端でソートする 終端が遅いものをできるだけ残しておくと後半にも使…

SRM680 div1 easy BearFair

考えたこと 題意がよくわからないのでサンプルを試していると[1,upTo[i]]の要素がquantity[i]個存在するということらしい 区間でソートしておくとよさそう dp[i][j] = (i個目のhintまでの区間で偶数をj個使うのが可能か) みたいなDPを考える 状態数O(nq)、偶…

SRM677 div1 easy DoubleOrOneEasy

考えたこと 2倍の回数はlogオーダーになるので大した回数にならない 3回2倍するとき a +x[0] *2 +x[1] *2 +x[2] *2 + x[3] 8a + 8x[0] + 4x[1] + 2x[2] + x[3] = newA になるようなxを見つける 最小回数なら2進法みたいな感じで貪欲にやれば求まる 適当な実…

SRM676 div1 easy WaterTank

考えたこと 最大の最小化なのでにぶたんをする Rを決め打つとO(n)で可能かどうかの判定ができそう 出すと通る THE典型みたいなにぶたん #include <bits/stdc++.h> using namespace std; using ll = long long; using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #d</int,></vi></int></bits/stdc++.h>…

SRM675 div1 easy TreeAndPathLength3

考えたこと 長さ3の経路ができないような木を考えるとウニしかない 葉が101個のウニをつくる ウニの葉に頂点をつなげると長さ3の経路が+100される これで100,200,300,400,…,10000までつくれる ウニの中心から長さ3の足を生やすと長さ3の経路が+1される これ…

SRM674 div1 easy VampireTree

考えたこと 子の数の和が頂点数-1なら木構造がつくれそう つくれるなら適当な木を構成して直径を求めればよさそう 木の構成で悩む トポソみたいに葉としてしか使えない頂点を子にした頂点をつくるを繰り返して構成したらいい気持ちになる 木が構成できたら直…

SRM673 div1 easy BearCavalry

考えたこと とりあえずソートしない理由はなさそう 明らかに二部マッチング 完全二部マッチングの個数の数え上げ NPなので無理です ソートしてあるとwarriors[i]とマッチングできるhorse[j]についてjの区間は[0,x]になって単調増加する warriors[i]がマッチ…

SRM672 div1 easy Procrastination

考えたこと 操作回数が多いのでうまくまとめる系の問題 時刻hで従業員nがtaskを持っているとき交換が起きるのはn-1,nの約数でh+1以上の最小の時刻 約数の列挙はO(sqrt(n))でO(n)個分やってたら当然TLE 交換回数がO(logn)とかO(sqrt(n))になってくれるとうれ…

SRM671 div1 easy BearCries

考えたこと _の配置の組み合わせ数を無視してとりあえず;の方だけ数えてみようとする ;でペアを組めるのは_を挟んでるやつだけ i番目を始点, j番目を終点とできるなら辺i→jを張るみたいなグラフを考える DAGのマッチングに落ちたと思ったけどマッチングが何…

SRM670 div1 easy Bracket107

考えたこと 括弧列で定番の+1/-1の累積和とか考えるけどよくわからないので実験する 括弧列の長さがnのとき、LCSがn-1の括弧列が絶対につくれる気がする 1文字をずらしていったような括弧列はLCSがn-1になるはず 括弧を飛び越すようなずらし方をすれば異なる…

SRM668 div1 easy PaintTheRoom

考えたこと 全てのマスを一回ずつ通って始点に戻るような経路(ハミルトン閉路)があればその経路をぐるぐる回ればいいのでどんなKでも必ずできる 実験してるとRかCの片方でも偶数であればハミルトン閉路が絶対にあることがわかる 奇数 * 奇数のときにハミルト…

SRM667 div1 easy OrderOfOperations

考えたこと bitDPをしてくださいみたいな雰囲気をしている 制約的に考えると dp[S] = (集合Sのセルを実行しているときの最小コスト) みたいな持ち方になりそう n個全部を実行したことについての判定をどうするかちょっと悩んだけど命令s[i]の和集合が全て実…

SRM666 div1 easy WalkOverATree

考えたこと この間勉強した全方位木DPを思い出す 頂点数n<=50なのでただの木DPでO(n^2)でいい 頂点iの部分木の頂点を全部訪れるのにかかる手数は一番深いところを後回しにすればいいので簡単に求まる 頂点iの部分木の頂点を全部訪れるわけではないので dp[i]…

SRM664 div1 easy BearPlays

考えたこと 操作回数KでO(K)はできないならどうせ周期性という気持ちになる 周期性で O(min(A+B, K)) くらいにはなりそうという気持ちになるが足りない 適当に実験したら実は周期が短いのがわかるのでは?と思い実験する 3*10^6回実行しても周期性がないのが…

SRM663 div1 easy ABBADiv1

考えたこと とりあえずinitial→targetじゃなくて逆に戻していく動作を考える 先頭にBなら取り除いて残りを反転、末尾にAなら取り除くの2パターンがある 愚直にやると2Nくらいかかりそうだけど冷静に考えるとそこまでパターン数は多くない気がしてくる 2通り…

SRM730 div2 med ExpectedMinimumPowerDiv2

概要 1~nまでの数からx個をランダムに選ぶ。このとき選んだx個のうち最小のものをSとし2Sをその集合のスコアとする。スコアの期待値を求めろ。 考えたこと 数mが最小の数Sになるのはどんなときか x個にmが含まれていてm未満の数が含まれていない したがってm…

SRM730 div2 easy IntervalIntersections

概要 区間[x1,y1]、[x2,y2]が与えられる。この区間どちらとも共通部分を持つような最小の区間の長さを求めろ。 考えたこと 間の区間を取るかそもそも区間が被っているかのどっちか x1 < x2 と x2 > x1 で場合分けすればいいね x1の方が右ならx1-y2かすでに区…

SRM730 div1 easy StonesOnATree

概要 各頂点iに重みw[i]が設定されているn頂点の木が与えられる。 ある頂点に1つ石を置くか、石を一つ取り除く操作を繰り返すゲームをする。ある頂点に石を置くとき、その頂点の子全てに石が置かれている必要がある。 ゲーム中に取りうる、石が置かれている…

SRM659 div1 easy ApplesAndOrangesEasy

考えたこと 問題文を理解するのに時間がかかる i番目をりんごにできるならりんごにせずに後ろに回した方がいい場合はなさそう 貪欲に前からりんごにできるならりんごにするみたいなのを書く O(K)で区間のりんごの数を数えられるので合計O(NK)で解けそう 区間…

SRM658 div1 easy OddEvenTree

考えたこと よくわからないので実験をする ある頂点からOな頂点ならEOの列を反転した列になる 距離が1ずれるんだからそれはそう この条件で可能どうかの判定はできそうな気持ちになる 条件を満たしていれば適当に構築してえい サンプルが弱すぎるだろ サンプ…