今日の精進
毎日格上の問題を倒すやつの100日目です。*1 コンテストリンク https://kenkoooo.com/atcoder/#/contest/show/d7702885-8ae7-43b8-b7c9-16ea14a53752 結果 ジョイッターで友だちをつくろう(難易度11…0/100(---) 刑務所(難易度11)…0/100(--------) チーム戦(…
毎日格上の問題を倒すやつの99日目です。 コンテストリンク https://kenkoooo.com/atcoder/#/contest/show/d7702885-8ae7-43b8-b7c9-16ea14a53752 結果 ビ太郎の旅(難易度9)…15/100(oo--) イノシシ(難易度12)…62/100(ooo-) 旅行(難易度11)...7/100(--o---) …
毎日格上の問題を倒すやつの98日目です。 コンテストリンク https://kenkoooo.com/atcoder/#/contest/show/d7702885-8ae7-43b8-b7c9-16ea14a53752 結果 図書館(難易度9)…19/100(o-) 美味しい美味しいハンバーグ(難易度12)…2/100(o---o---) 掃除(難易度12)...…
毎日格上の問題を倒すやつの97日目です。 コンテストリンク https://kenkoooo.com/atcoder/#/contest/show/d7702885-8ae7-43b8-b7c9-16ea14a53752 結果 治療計画(難易度11)…0/100(----) 航空路線図(難易度10)…37/100(oo-) ふたつの交通機関(難易度11)...6/10…
毎日格上の問題を倒す*1やつの96日目です。 暫くこれです。ちゃんとAtCの格上も解いてはいますが。 コンテストリンク https://kenkoooo.com/atcoder/#/contest/show/d7702885-8ae7-43b8-b7c9-16ea14a53752 結果 道路の建設案(難易度10)…65/100(ooooo-) 鉱物(…
毎日格上の問題を倒すやつの93日目です。 問題リンク atcoder.jp 問題概要 頂点に色がついた木があるよ。 各色について、その色を一回以上通るパスの個数を求めてね。 解法 頂点0を根とした根つき木とします。 トポロジカルソートをして、オイラーツアー順を…
毎日格上の問題を倒すやつの92日目です。 問題リンク atcoder.jp 問題概要 長さが で要素が 以上 以下である数列すべてについて、以下の値の和を で割ったあまりを求めてね。 長さが で要素がすべて である数列から、「ある区間の数をその数と決めた数の大き…
毎日格上の問題を倒すやつの91日目です。 問題リンク atcoder.jp 問題概要 以上 以下のすべての整数の部分集合であって、どの二つも互いに素であるようなものの個数を求めてね。 解法 幅が狭いのが意味深すぎます。 それぞれの整数について、共通の素数で割…
毎日格上の問題を倒すやつの90日目です。 問題リンク 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 時間が厳しそうな気持ちになりま…
毎日格上の問題を倒すやつの78日目です。 問題リンク atcoder.jp 問題概要 枚の紙があって、 個ずつ数字を書くよ。 このとき、 が 個ずつ出現したうえで、各紙に共通する数字はただ一つにする必要があるよ。 は自由に、 は1000から2000の範囲で自由に決めら…
毎日格上の問題を倒すやつの77日目です。 問題リンク atcoder.jp 問題概要 グラフが与えられるよ。 いくつかの頂点は奇数回、それ以外は偶数回通るような長さ 以下のパスをひとつ出力してね。 解法 存在が保証されている構築問題は、極端な場合を考えると良…
毎日格上の問題を倒すやつの76日目です。 問題リンク atcoder.jp 問題概要 整数列 が与えられるよ。 広義単調増加列 と広義単調減少列 で、 が成り立つようなものを考えるよ。 の要素の絶対値の和の最小値を求めてね。 解法 例の如く愚直なDPを考えると、要…
毎日格上の問題を倒すやつの75日目です。 問題リンク atcoder.jp 問題概要 文字列の美しさを決めるよ。 審査項目は 個あって、 個目は、「部分文字列に が含まれていたらその数と の積だけ得点が与えられる」というものだよ。 得点の最大値を求めるか、そん…
毎日格上の問題を倒すやつの74日目です。 いや、こどふぉバチャです。格上は倒してません。 コンテストリンク codeforces.com 結果 A1完・Score376・Perf1454相当 A...00:12 競プロやめちまえ[バーチャル参加]hirayuu_cfさんのCodeforces Round 666 (Div. 1)…
毎日格上の問題を倒すやつの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が見つ…
毎日格上の問題を倒すやつの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 問題概要 という漸化式があるよ。 となるような最小の を求めるか、そんなものはないと宣言してね。 解法 の場合は後がめんどいので先に処理しましょう。これは適切に場合分けするだけです。 …