JOI23/24の参加記です。春合宿です。雑です。躊躇なくネタバレします。 また、記憶の捏造があるかもしれません*1 春合宿前 特段特殊な精進はしてなかったはずです。難易度10を少し埋めたり遅延セグ木の空書きとかはしました。 というので、本選前よりは精進…
JOI23/24の参加記です。本選までです。雑です。 一次予選たち 流石に楽勝でした。絶対需要ないので何も書きません。RTAしたり、3回目で1時間くらい存在を忘れていたりしました。 綺麗なフラグ回収ですよね、これ A:一行 00:17B:mod7 00:44C:oだけ分ける 01:1…
毎日格上の問題を倒すやつの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 問題概要 の積を で割ったあまりを求めてね。 解法 か の時は先に処理します。これはどちらも容易です。 の場合は非常に簡単です。階乗を前計算して、 倍すればよいです。 一般の場合でも、逆…
毎日格上の問題を倒すやつの85日目です。 問題リンク 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 問題概要 グラフが与えられるよ。 いくつかの頂点は奇数回、それ以外は偶数回通るような長さ 以下のパスをひとつ出力してね。 解法 存在が保証されている構築問題は、極端な場合を考えると良…
第2回 緑以下コンテスト - connpass に参加してきたので雑記です。しっかりしたものではありません。 AdCの記事こんなんじゃだめでは....? 前日 オンサイトがあったので参加登録しました。そこに理由なんていらない。 土曜学校あるのが参加しない理由にはな…
毎日格上の問題を倒すやつの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 問題概要 互いに区別できるキャベツがあるよ。 正確には、品種 のキャベツが 個あるよ。 また、店 はいくつかの品種のキャベツを、合計 個欲しがってるよ。 高橋君は、持っているキャベツをす…