毎日格上の問題を倒すやつの93日目です。 問題リンク atcoder.jp 問題概要 頂点に色がついた木があるよ。 各色について、その色を一回以上通るパスの個数を求めてね。 解法 頂点0を根とした根つき木とします。 トポロジカルソートをして、オイラーツアー順を…

毎日格上の問題を倒すやつの78日目です。 問題リンク atcoder.jp 問題概要 枚の紙があって、 個ずつ数字を書くよ。 このとき、 が 個ずつ出現したうえで、各紙に共通する数字はただ一つにする必要があるよ。 は自由に、 は1000から2000の範囲で自由に決めら…

毎日格上の問題を倒すやつの72日目です。 問題リンク atcoder.jp 問題概要 山の数が 以下でそれぞれの山の石の個数が に含まれるようなNimのうち、先手が勝てるようなものの個数を求めてね。 解法 要するに、要素のXORが非零であるものの個数を数え上げると…

毎日格上の問題を倒すやつの71日目です。 問題リンク atcoder.jp 問題概要 個の文字列があり、 個目の文字列 はコスト かかるよ。 回文を作るための最小コストを求めてね。 解法 両端から作っていきます。 すると、「回文ができる」か、「片方が対消滅し、部…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

毎日格上の問題を倒すやつの6日目です。 問題リンク atcoder.jp 問題概要 種類の品物がそれぞれ無限個あるよ。 を、体積と重さが 以下になるように品物を選んだ時の価値の最大値と定義するよ。 は有限の値になるから、それを求めてね。 解法 求めたいものは…

毎日格上の問題を倒すやつの5日目です。 無事5日続きました。 問題リンク atcoder.jp 問題概要 グリッドに×を書いて×が書かれた場所のスコアを最大化してね。 ただ、線分を書くのにコスト がかかるよ。 ×が繋がってるところの線分は端折って一本にしてもいい…

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