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

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

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

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

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

毎日格上の問題を倒すやつの70日目です。 問題リンク atcoder.jp 問題概要 以下の整数の組 であって、 を満たす が存在するようなものの個数を で割ったあまりを求めてね。 解法 愚直を書いてOEISにぶちこむと、1,2,4,5,8,10,13,14,18,21,26,28 - OEISが見つ…

毎日格上の問題を倒すやつの69日目です。 問題リンク atcoder.jp 問題概要 個の長方形が縦一列に並んでいるよ。 それぞれの長方形をスライドして連結にするとき、スライドする距離の最小値を求めてね。 解法 普通のDPは当然間に合いません。 しかし、そのDP…

毎日格上の問題を倒すやつの65日目です。 問題リンク atcoder.jp 問題概要 町が電車でつながってるよ。 それぞれの電車は、同じ会社のものはいくら乗り換えても 円で済むけど、別の会社に乗り換えるともう 円かかるよ。 町 から町 まで移動する値段の最小値…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

毎日格上の問題を倒すやつの9日目です。 問題リンク atcoder.jp 問題概要 区別できない 面ダイスが 個あるよ。 「どの異なる2つのダイスの目の和も にならない場合の数を で割った余り」の答えをありえるすべての に対して求めてね。 解法 包除原理で解きま…

毎日格上の問題を倒すやつの8日目です。 問題リンク atcoder.jp 問題概要 2つの点が描かれた紙があるよ。 マスの境界にある線をランダムに選んで切ることを2つの点が分かれるまで行うとき、回数の期待値を答えてね。 解法 「操作が終わるまでにこの線を切る…

毎日格上の問題を倒すやつの2日目です。 問題リンク atcoder.jp 問題概要 長さ の順列 が隠されてるよ。 以下の質問を高々 回まですることで、全ての要素を特定してね。 か？ 解法 の位置を特定すると良いことがあります。1 なぜかというと、 を足しても大小…

Twitter(今もTwitter)*1でこんなことを言っていました。 私、丸紅コン終わったら毎日精進鯖みたいなことします(鬼畜)1日1問もDiffが自らのレート以上の問題が解けていなかった場合爆発することにします(え？)ちなみにレートが変わる日は変わる前のレートで考…