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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

毎日格上の問題を倒すやつの15日目です。 問題リンク atcoder.jp 問題概要 一辺が の正 角形に白黒の石を置くとき、すべての辺の黒い石の数が同じ置き方の数を で割ったあまりを求めてね。 解法 一辺に置く黒石の数を決め打つ余裕はありますが、愚直なDPで計…

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

毎日格上の問題を倒すやつの13日目です。1 問題リンク atcoder.jp 問題概要 木が与えられるよ。 木から頂点を2つ以上いくつか選んだ時、選んだ頂点の組すべてについて距離が木の直径と等しい選び方の個数を で割ったあまりを求めてね。 解法 木の直径は、DFS…

毎日格上の問題を倒すやつの7日目です。 無事一週間続いたことに驚いております。 問題リンク atcoder.jp 問題概要 K,E,Yのみからなる文字列が与えられるよ。 「隣り合う文字を入れ替える」ことを 回まですることで作れる文字列の個数を答えてね。 解法 まあ…

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

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