毎日格上の問題を倒すやつの41日目です。 問題リンク atcoder.jp 問題概要 グラフが与えられるよ。 指定された辺はちょうど1回、それ以外は何回でも通っていいような経路が存在するか判定してね。 解法 何回でも通っていい辺がごちゃごちゃしていると見通し…

毎日格上の問題を倒すやつの40日目です。 問題リンク atcoder.jp 問題概要 横 マスのグリッドがあり、それぞれ数字が書かれてるよ。はじめ、カエルが マス目にいるよ。 を決めて、「 歩進んで 歩下がる」ことを繰り返すよ。 同じマスに2度立ち入るか、範囲か…

毎日格上の問題を倒すやつの39日目です。 これはこどふぉバチャになるので、必ずしも「格上の問題を倒す」ではない気がしますが。 コンテストリンク codeforces.com 結果 AB2完・Score1236・Perf1890相当 A...00:13 B...01:14(+1) D...(-4) うーん[バーチャ…

毎日格上の問題を倒すやつの37日目です。 問題リンク atcoder.jp 問題概要 頂点 辺のグラフがあるよ。 はじめ、王様が頂点 にいるよ。長さ の数列 を決めて、 回以下の行動を繰り返すよ。 今いる頂点から頂点 の向きに辺を張り、 に移動する このとき、どの…

毎日格上の問題を倒すやつの36日目です。 問題リンク atcoder.jp 問題概要 木が与えられるよ。 すべてのパス について、 と のLCAの最大値を類似度として、これを最小にする順列 を構築してね。 解法 明らかに、類似度を0にすることは不可能です。*1 そのた…

毎日格上の問題を倒すやつの35日目です。 問題リンク atcoder.jp 問題概要 草が 本あって、 番目の草の高さは だよ。 高橋くんは、以下のようにして草を全部抜くよ。 を残っている草の中で最も高い草の高さとして、 より高い高さの草を一斉に抜く 青木くんは…

毎日格上の問題を倒すやつの34日目です。 問題リンク atcoder.jp 問題概要 長さ の数列 と が与えられるよ。 長さ の全ての順列 に対して、 の総和を求めてね。 解法 見た目が見た目ですが、DPできます。 大きい順に見て行った時、 番目で余りをとる場合、か…

毎日格上の問題を倒すやつの33日目です。 問題リンク atcoder.jp 問題概要 「数列 を 回シフトしてから一様に をxorしたら に一致する」ような の組をすべて求めてね。 解法 いつものbitごとに考えるあれです。 各bitごとにみると、シフトはローリングハッシ…

2023/10/17のABC323にて入黄したので、いろいろ書きます。 自己紹介とこれまで そういえばしっかりしてなかったので。 私は中学2年生です*1。私の学校は私しか競プロ勢がいないので、競プロ強豪校ではありません。筑駒でも開成でも灘でもないです。*2 数学が…

毎日格上の問題を倒すやつの23日目です。 問題リンク atcoder.jp 問題概要 「所属大学も得意分野も異なる 人の強さの合計の最大値」をありえるすべての に対して求めてね。1 解法 いわゆる重み付き二部マッチングです。 コストを負にして最小費用流をしたい…

毎日格上の問題を倒すやつの22日目です。 問題リンク atcoder.jp 問題概要 集合の列に対して、隣り合う要素で片方にしかないものがちょうど1つであるものを、「素晴らしい整数の列」とするよ。 また、「素晴らしい整数の列」のスコアを、 を含む集合の個数を…

毎日格上の問題を倒すやつの21日目1です。 初めての橙後半の難問です。 問題リンク atcoder.jp 問題概要 以下の条件をすべて満たす の組の数を で割ったあまりを求めてね。 解法 とします。 重要な事実として、以下が成り立ちます。2 このとき、累積和の考え…

毎日格上の問題を倒すやつの20日目です。1 問題リンク atcoder.jp 問題概要 無向グラフが与えられるよ。 頂点 から行ける頂点数が になるように辺に向きをつけてね。 解法 から に辺を張るとき、明らかに から行ける頂点は から行ける頂点数以上です。 その…

毎日格上の問題を倒すやつの19日目です。 問題リンク atcoder.jp 問題概要 スケート場があって、何マスかにとどまれるよ。 どのマスからでもすべてのマスに行けるように、とどまれるマスを増やしたいよ。 増やすマスの最小値を求めてね。 解法 からすべての…

毎日格上の問題を倒すやつの16日目です。 問題リンク atcoder.jp 問題概要 個の飴があるよ。 「この中から 個選んだ時の種類数の期待値」をすべての に対して求めてね。 解法 主客転倒テクです。 個ある飴を選ぶ確率を全部に関して足せば期待値になります。1…

毎日格上の問題を倒すやつの15日目です。 問題リンク atcoder.jp 問題概要 一辺が の正 角形に白黒の石を置くとき、すべての辺の黒い石の数が同じ置き方の数を で割ったあまりを求めてね。 解法 一辺に置く黒石の数を決め打つ余裕はありますが、愚直なDPで計…

毎日格上の問題を倒すやつの14日目です。1 問題リンク atcoder.jp 問題概要 人でリーグ戦をするよ。 すでに何戦かは終わらせてるから、このあと単独優勝する可能性がある人を列挙してね。 解法 が小さいため、多項式時間なら割と何でも間に合います。 なので…

毎日格上の問題を倒すやつの13日目です。1 問題リンク atcoder.jp 問題概要 木が与えられるよ。 木から頂点を2つ以上いくつか選んだ時、選んだ頂点の組すべてについて距離が木の直径と等しい選び方の個数を で割ったあまりを求めてね。 解法 木の直径は、DFS…

毎日格上の問題を倒すやつの12日目です。 問題リンク atcoder.jp 問題概要 全部の頂点が白い木があるよ。 「頂点 からのパスの中に白い頂点があるような頂点を つ黒く塗る」ことを繰り返してすべての頂点を黒くするときの回数の期待値を答えてね。 解法 期待…

まえおき なんか高順位になっちゃったので、解法を軽くまとめておきます。たぶん雑です。 ↓ところでこいつHeuristic強いのか弱いのかわからないんですが AHC022 - 懇親会&賞金圏内(?)1 AHC023 - 30台すらいけず(???) AHC024 - 自明なのすら書けずに緑パフォ(…

毎日格上の問題を解くやつの11日目です。1 問題リンク atcoder.jp 問題概要 頂点 辺の無向グラフに以下の操作を施して木にできるか判定してできるなら実際にやってみてね。 頂点 間と頂点 間に辺を追加する。 解法 頂点数が偶数なら明らかに不可能です。 逆…