問題リンク 愚直に座圧して行列累乗をする。 いけない区間は座圧した座標でimosほうでやればよい。 1からスタートするときだけに注意 提出コード codeforces.com

問題リンク なんか適当なdpをやってもACは出たんですが、正当性が見抜けないのでそうじゃない方の解説で。 解説 dp[i] := i文字作るときの最小コスト としましょう。 パターンとしては、1文字追加、倍にする、削除、が考えられるが、1文字追加した後に1文字…

問題リンク バチャ中に解けなかったけど、おもしろかった。 解説 実はコストに関する二部探索でいい。 あるコストを決め打ったときに、より大きい辺のみで、グラフを構築して、それがDAGであればokそうじゃなければngっていう二部探索をしよう！ この時DAGで…

易しい なんかFで2610書いちゃったのにpretest通ったやべぇｗｗって全完して暇だったから思ってresubしたんだけど、よく見たら26*10( * 10)だった 頭がついてない ま、本来のrated対象を考えるとこれぐらいの難易度がいいかもね。 紫ぐらいあれば楽に全完は…

問題リンク 想定よりいい解法でできたので 解説 SWAGを知っていますか？ 知らない人はこれを読みましょう。 scrapbox.io これを用いて尺取り法をすれば、で求めることができました。 提出コード codeforces.com

問題リンク tourist回のセット TutorialにBonusと書いてあったの解法が初手に思いついたので(しかも実装がかなり簡単！！) 解法 イメージはしゃくとり法(とスライド最小値)です。 が条件を満たすなら、が条件を満たすのはいいでしょう(もちろん です) そして…

問題リンク (コンテストページです) 解説 各区間における右端を右に移動させながら、条件を満たす左端が各右端について何通りあるか求める方針でいきます。 ここで、 とします。当然、任意の区間で、 を満たします。 ある区間が条件を満たす必要十分条件は、…

問題リンク 公式の解説とちょっと違いそうなので 解説 まず、全部使うのが最適なのは明らかでいいでしょう(どうしても証明したい人は公式の解説の最初を読んでください。それはそうとなります) 最後に残るのを、消すやつをとしましょう。 内 と内での順番を…

問題リンク Tutorialのやり方は良く分かってません。 解法 が大きい順に見ていこう。そうすると、今見てる点が必ず手を広げる番であるので、条件を満たす周波数の中での中に何個点があるかをみたらいい。 条件を満たす周波数の範囲は各点において、せいぜい1…

そういや書くの忘れてた 初1ページ目に乗った 既出を知ってたからというのが一番大きいけれども、嬉しいね(これでkotamanegiに勝てないのか…) 次は暖色チャレンジですが、次でなれないとAGC挟むと遠くなっちゃうね

問題リンク 最小費用流に帰着される 提出コード codeforces.com まとめ 最小費用流初めて勉強した。 概念知ってたら、そのままだった。

問題リンク またかという気分 解法 座圧してimos法なり遅延セグ木などでに1を区間加算をしよう 各区間における最小値が1ならnon-redundantである 提出コード codeforces.com まとめ さすがに見すぎて飽きたな

問題リンク 解法 まず1本直径をとってこよう！ 直径以外の点は直径の両端のどちらかが最長となるので、まずそこから処理をする(これは直径を求めるアルゴリズムが最長→最長とやることからも分かるだろう) あとは直径を端から消していく。 提出コード codefor…

問題リンク 計算量解析が本質の問題だね 解法 まずがどこまでの範囲で最大値になるかを求めよう！ これはstackを使うことででできることは有名である。 そうするとより左のパートとより右のパートから1つずつとってきて和がになるような数を調べたらいい。 …

問題リンク ギャグなのに時間かかった… 解法 まず元の配列の転倒数のパリティを愚直に求めよう(BITを使ってでもとける) 転倒数のパリティはswapの偶奇に依存する(sawpの順番や、回数は直接関係ない) よって長さがの配列の反転は回swapすることで必ず達成でき…

問題リンク 解法 人投票した状況を順に考えていく。 人投票したとしたとする。 まだ無料で当選させていない人のうちで、以下の人の中でが最大の人を無料で投票させよう！ もし無料で当選させていない人たちがいなければ、いったん誰かを購入したと仮定して次…

問題リンク 解法 であるので、 となり最大値と最小値を独立に考えられるので、あとは個別に数え上げよう 提出コード codeforces.com まとめ こういう分離して考えるのは典型だね

問題リンク TLが厳しすぎる… 解法 を座圧しちゃいましょう！ そうすると遅延セグ木に乗ります(乗せ方はちょっと難しいけど、区間更新区間加算のときの個数を区間幅にすると解決です) そうすることで、休む時間がわかるので全体から引けば求まります。 計算量…

問題リンク 実装に手間取ってしまった… 解法 まず、グラフにそもそも閉路がないならYESである。以下閉路があるとしよう。 なんでもいいので1つ閉路をとってくる。この閉路の辺のどれかを削除することが、DAGになるための必要条件である。 この閉路の長さはせ…

問題リンク 解説 の番目の数をとすると、ということである。 ここで、とすると、このは明らかに単調性がある。 よって、となるの境界を二部探索で求めよう！！ さて、あとはの計算方法だが、これは素因数分解をして包除原理を使うと求めることができる。 こ…

問題リンク 易しい問題だが意外と解かれてない 解法 愚直に探索する。辺がないのがせいぜい本なので、各頂点からぜんぶみたときに飛ばされるのもせいぜい個であるので、ほぼhitする。 一度見た点を見ないようにstd::setでみた点を管理しよう。 提出コード co…

問題リンク 解法 約数の個数はかなり速いスピードで減っていって最終的に 1 or 2になる(1は最初から1の場合) ということで各において、何百回約数の個数に変更しても2のままで無駄なことをしてるだけなのである。 よってstd::setなどを使って、2より大きいの…

問題リンク こういうのは典型の1つでそれぞれの数字が何回足されるかということを考えるといいです。 まず最大値の数字は0回です。それ以外を考えていきましょう。 愚直に考えて、数える回数が分からないときは、確率で考えるといいです。 同じ数字もすべて…

解法 全てのタスクの和をとすると、最終的に になるので、あとはそれとの差分をみよう。 1度の操作で差分が2ずつ減っていくことに注意 提出コード codeforces.com まとめ 1回嘘書いちゃって反省

問題文の理解に戸惑ったね 解法 日で購入できるなら、日でも当然購入できるので単調性あるため二分探索をしよう！ 以下日で購入できるかの判定方法 1日で複数種類買うことができるので、日のうちドルとポンドのそれぞれがもっとも安い日に購入したらよい。 …

駒が3種類あるので、各girdを拡張させてとして考えましょう。頂点数はせいぜい300です。 距離の定義をとすると、これを辞書順最小にしろという問題になります。 となるとワーシャルフロイドが十分に間に合うので、ワーシャルフロイドをしましょう。(各始点に…

リクエストがあれば実装つきで、解説動画撮るので気軽にどうぞ 全体の感想としては、前回以上に典型色感が強い。 難易度感は前回より難しい気もする？ かなり知識で殴った感があって、想定はひょっとしたらもっと天才なのかもしれないけど。 ちなみに後で記…

電圧の総和を，抵抗の総和をとすると、 となるので、を固定したときの の範囲は区間になっている！！！ ということで予め前処理として、各とがそれぞれ何通りあるかをナップサックDPで求めて、については累積和まで求めておくことで、を固定したときに、条件…

問題リンク という制約からいかにもbitDPをしたくなる。 直方体はよくみると3面しかないので、次のようにDPを定義しよう！ あとは愚直にメモ化などで実装するといい 構造体を定義すると楽な気がする？ 提出コード yukicoder.me まとめ 慣れているとやるだけ…

問題リンク 解説動画です。 動画リンク 実装例