毎日格上の問題を倒すやつの92日目です。 問題リンク atcoder.jp 問題概要 長さが で要素が 以上 以下である数列すべてについて、以下の値の和を で割ったあまりを求めてね。 長さが で要素がすべて である数列から、「ある区間の数をその数と決めた数の大き…

毎日格上の問題を倒すやつの91日目です。 問題リンク atcoder.jp 問題概要 以上 以下のすべての整数の部分集合であって、どの二つも互いに素であるようなものの個数を求めてね。 解法 幅が狭いのが意味深すぎます。 それぞれの整数について、共通の素数で割…

毎日格上の問題を倒すやつの89日目です。 問題リンク atcoder.jp 問題概要 数列 のいくつかの要素をxorしてできる数のうち、小さい方から 番目から 番目までのものを列挙してね。 解法 xorの基底の練習問題です。 noshiさんが広めたよくわからないすごい方法…

毎日格上の問題を倒すやつの86日目です。 問題リンク atcoder.jp 問題概要 の積を で割ったあまりを求めてね。 解法 か の時は先に処理します。これはどちらも容易です。 の場合は非常に簡単です。階乗を前計算して、 倍すればよいです。 一般の場合でも、逆…

毎日格上の問題を倒すやつの84日目です。 問題リンク atcoder.jp 問題概要 を二進数で書いたものを辞書順に並べたとき、 番目に来るものを答えてね。 解法 上から決めていくと、空文字列か0になるか1になるかを判断する必要がありますが、これは引き算さえで…

毎日格上の問題を倒すやつの83日目です。 問題リンク atcoder.jp 問題概要 から連続とは限らない部分列を取り出す方法であって、取り出し方が一意に定まるものの個数を求めてね。 解法 番目の要素を必ず選ぶ通り数 とします。そこで、遷移を考えましょう。 …

毎日格上の問題を倒すやつの82日目です。 問題リンク atcoder.jp 問題概要 があるよ。 を満たす の組のうち、辞書順で 番目のものをこの順に見ていって、以下のようにするよ。 の 番目を入れ替える 最終的な を求めてね。 解法 番目からキリのいいところまで…

毎日格上の問題を倒すやつの79日目です。 問題リンク atcoder.jp 問題概要 以下の整数であって、すべての を含むものの総和を求めてね。 解法 いわゆる桁DPです。 個の情報を持ち、それぞれに総和と個数を持っておきます。*1 時間が厳しそうな気持ちになりま…

毎日格上の問題を倒すやつの77日目です。 問題リンク atcoder.jp 問題概要 グラフが与えられるよ。 いくつかの頂点は奇数回、それ以外は偶数回通るような長さ 以下のパスをひとつ出力してね。 解法 存在が保証されている構築問題は、極端な場合を考えると良…

毎日格上の問題を倒すやつの76日目です。 問題リンク atcoder.jp 問題概要 整数列 が与えられるよ。 広義単調増加列 と広義単調減少列 で、 が成り立つようなものを考えるよ。 の要素の絶対値の和の最小値を求めてね。 解法 例の如く愚直なDPを考えると、要…

毎日格上の問題を倒すやつの75日目です。 問題リンク atcoder.jp 問題概要 文字列の美しさを決めるよ。 審査項目は 個あって、 個目は、「部分文字列に が含まれていたらその数と の積だけ得点が与えられる」というものだよ。 得点の最大値を求めるか、そん…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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