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

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

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

毎日格上の問題を倒すやつの68日目です。 問題リンク atcoder.jp 問題概要 互いに区別できるキャベツがあるよ。 正確には、品種 のキャベツが 個あるよ。 また、店 はいくつかの品種のキャベツを、合計 個欲しがってるよ。 高橋君は、持っているキャベツをす…

毎日格上の問題を倒すやつの67日目です。 嘘です、はるくさんのやらかし回です。本番のコンテストだと許されないことをしてるので、懺悔としてまとめておきます。 コンテストリンク codeforces.com 結果 0完（笑） 解法と反省 A 二次元累積和まではパッと思…

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

毎日格上の問題を倒すやつの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--) 合…

毎日格上の問題を倒すやつの51日目です。*1 問題リンク atcoder.jp 問題概要 マス横に並んだものを、「隣り合う マスにはたかだか2色しか表れない」という条件を満たして マスで塗る方法を数え上げてね。 解法 番目と 番目の色が異なる塗り方 ってだけでDPは…

毎日格上の問題を倒すやつの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 問題概要 本の木があるよ。 ある木を伐採するコストは、その木と両端の木の高さの合計だよ。 コストの最小値を達成する伐採方法の数を で割った余りを求めてね。 解法 となりあわせになってい…