毎日格上の問題を倒すやつの64日目です。 問題リンク atcoder.jp 問題概要 項の、初項が で公差が である等差数列をつなげたものを数として解釈し、 で割ったあまりを求めてね。 解法 各桁数ごとに考えます。 そうすると、 倍して何かを足すことを繰り返すと…

毎日格上の問題を倒すやつの63日目です。 問題リンク atcoder.jp 問題概要 すぬけくんのお気に入りの整数 が隠されてるよ。 以下のような受け答えをするすぬけくんに最大 回質問して、 を特定してね。 「 はお気に入りの整数か?」と聞かれたとき と の辞書順…

毎日格上の問題を倒すやつの62日目です。 問題リンク atcoder.jp 問題概要 という漸化式があるよ。 となるような最小の を求めるか、そんなものはないと宣言してね。 解法 の場合は後がめんどいので先に処理しましょう。これは適切に場合分けするだけです。 …

毎日格上の問題を倒すやつの61日目です。 問題リンク atcoder.jp 問題概要 四隅に色がついたタイルが 枚あるよ。 これを組み合わせて隅に集まる色が同じ立方体を作りたいよ。 どのタイルにも向きがあるとき、作れる立方体が何通りか答えてね。 解法 上のタイ…

毎日格上の問題を倒すやつの58日目です。 問題リンク atcoder.jp 問題概要 すべての数が 回ずつ出る長さ の数列のうち、以下のようなものを見つけるか、そんなものはないと宣言してね。 番目の は全体で の位置にある 解法 非常に単純明快です。 の小さい順…

毎日格上の問題を倒すやつの57日目です。 問題リンク atcoder.jp 問題概要 を満たすすべての に対して、 となるような に対する の総和の最大値を求めてね。 解法 とりあえず、 のビットが立っている場所と同じ場所にしかビットが立っていないものを考えたく…

毎日格上の問題を倒すやつの56日目です。 問題リンク atcoder.jp 問題概要 ゲームのやりすぎで腰を痛めた*1 人の高橋くんたちを、数直線上の の位置にある 個の椅子に座らせようとしてるよ。 ただ、 人目の高橋くんには座標 より左か、座標 より右の椅子に座…

毎日格上の問題を倒すやつの55日目です。 問題リンク atcoder.jp 問題概要 グラフが与えられるよ。 すべての辺を1回ずつ使って三つのサーキットを作れるか判定してね。 解法 明らかにオイラーグラフであることが必要条件です。これはすべての頂点の次数が偶…

毎日格上の問題を倒すやつの54日目です。 問題リンク atcoder.jp 問題概要 頂点のグラフがあるよ。 いくつか辺を取り除いて2つ以下の完全グラフを作るとき、残す辺の本数の最小値を求めてね。 解法 補グラフについて考えると見通しが良くなります。 こうする…

毎日格上の問題を倒すやつの53日目です。*1 コンテストリンク https://kenkoooo.com/atcoder/#/contest/show/172ff02f-aef7-48c8-8f65-0de9b8643797?activeTab=Standings 結果 道案内...45/100(ooo-) ドラゴン2...100/100(ooo) 防犯ゲート...12/100(oo--) 合…

毎日格上の問題を倒すやつの50日目です。*1 問題リンク*2 atcoder.jp 問題概要 人の子供がいるよ。 人目のはしゃぎ度を 、 人目に配るキャンディーの量を として、幼稚園の活発度を とするよ。 人目のはしゃぎ度が から を動き、 個のキャンディーを配るとき…

毎日格上の問題を倒すやつの49日目です。*1 問題リンク*2 atcoder.jp 問題概要 頂点の木のうち、すべての頂点の次数が に含まれているようなものの個数を で割った余りを求めてね。 解法 2日前にやった次数制限付きケイリーの公式を利用します。 同じように…

毎日格上の問題を倒すやつの48日目です。*1 問題リンク atcoder.jp 問題概要 長さ の数列 が与えられるよ。 和が 以下のすべての数列 に対して、 を求めて、その総和を で割った余りを求めてね。 解法 負の二項定理を使って解くのが簡潔です。 これは、 とい…

毎日格上の問題を倒すやつの47日目です。 もとい、FPSウィークの2日目です。飽きたら終わります。*1 問題リンク atcoder.jp 問題概要 個の部品があって、 番目の部品には 個の穴があるよ。これらの穴は区別できるよ。 また、 個の接続用部品があるよ。 これ…

毎日格上の問題を倒すやつの44日目です。 問題リンク atcoder.jp 問題概要 以下の条件をすべて満たす整数の組を考えるよ。 あり得るすべての組に対して、 の総和を求めてね。 解法 以下の記事にFPSの基礎が詳しく載っています。 私もこれを参考に解いたので…

毎日格上の問題を倒すやつの43日目です。 問題リンク atcoder.jp 問題概要 数列が与えられるよ。 選んだ2数の積が立方数にならないように最大限選んだときの個数を求めてね。 解説 明らかに筋が悪いですがG - Cubic?みたいな感じで解きます。 数を素因数ごと…

毎日格上の問題を倒すやつの42日目です。 問題リンク atcoder.jp 問題概要 本の木があるよ。 ある木を伐採するコストは、その木と両端の木の高さの合計だよ。 コストの最小値を達成する伐採方法の数を で割った余りを求めてね。 解法 となりあわせになってい…

毎日格上の問題を倒すやつの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 問題概要 無向グラフが与えられるよ。 頂点 から行ける頂点数が になるように辺に向きをつけてね。 解法 から に辺を張るとき、明らかに から行ける頂点は から行ける頂点数以上です。 その…