Xmas Contest 2019

Xmas Contest 2019 にご参加いただいた皆様,どうもありがとうございました! 大変遅くなりましたが解説記事が準備できました.今年も相変わらずのばたばた準備をしていましたが,いつの間にか問題がいくつも分裂してすごいことに.皆様何かしら楽しめる問題…

Xmas Contest 2019 K: Set of Trees

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_k 問題概要 根付き木の順序を,子を降順に並べたものの辞書順として再帰的に定める.根付き木がいくつかあって, つ選んで「小さく」するという行動ができる 人ゲームを考える.初期状態が与えられる…

Xmas Contest 2019 J: Sub-Post Correspondence Problem

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_j 問題概要 文字列 が与えられるので,ある () に対して が の連続とは限らない部分列となるようにできるか判定せよ (一応,同じ添え字は 回まで). 解法 カード 枚での解 () があれば YES でなけれ…

Xmas Contest 2019 E: Sum of f(n) 解説

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_e 問題概要 の素因数の個数 (重複込み) を とする. が与えられるので を求めよ. 解法 1 (?) 答えを手元で全部計算して,適当な間隔で区切って埋め込みます.狭い区間については区間篩のアルゴリズ…

Xmas Contest 2019 D: Sum of (-1)^f(n) 解説

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_d 問題概要 の素因数の個数 (重複込み) を とする. が与えられるので を求めよ. 解法 1 (?) 答えを手元で全部計算して,適当な間隔で区切って埋め込みます.狭い区間については区間篩のアルゴリズ…

Xmas Contest 2019 C: Sokoban 解説

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_c 問題概要 倉庫番の盤面が与えられるので (入力公開),解くのに必要な最小手数を求めよ. sample, 01, 02 小さいので,手で遊んで解けます.しかし,解くだけなら簡単ですが最小手数は非自明だった…

無限直積の双対加群こわい

概要・参考文献 を示します. https://mathoverflow.net/q/10239 ←これを読み解いたよというような話です. 何がすごいの? は簡単です.直和の普遍性と,同一視 ですね.こっちは を任意の単位的可換環にしても成り立ちます.一方,直積からの準同型という…

Codeforces 1119H: Triple

https://codeforces.com/problemset/problem/1119/H 問題概要 が固定されている. に対して が与えられるので, たちを の指数は XOR で畳み込む,というのを速くやる. 考察 Hadamard 変換すれば畳み込みが掛け算になる (常識) けど,そのままやると長さ の…

Xmas Contest 2018

Xmas Contest 2018 にご参加いただいた皆様,どうもありがとうございました! 2015, 2016, 2017 年は元気にしていなくて開催できなかったのですが,その間引き継いでくれていた japlj さんと snuke さんと共に今年は運営しました.とっつきやすい良問を作っ…

Xmas Contest 2018 J: Japanese Exponentation 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_j 問題概要 四の三の二乗乗 みたいなのを で計算せよ. 解法 UTF-8 の文字列を処理する方法は,皆さんお使いのプログラミング言語ごとに調べてください. 冪乗を で計算する方法を考えます.「 のと…

Xmas Contest 2018 I: Interesting Equation 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_i 問題概要 実数 が与えられるので, がだいたい になるような整数 を求めよ. 解法 ? なる解の存在が保証されているので,その範囲の をすべて調べられれば答えが見つかります. もちろんそれでは遅…

Xmas Contest 2018 H: Hello, Xmas Contest 2018 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_h 問題概要 文字列 が与えられる.グリッドの一部に A-Z または * を書いて, 各行の最初の非空白文字を順に繋げて * を除いた文字列が 各列の最初の非空白文字を順に繋げて * を除いた文字列が とな…

Xmas Contest 2018 E: Exclusive☆OR 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_e 問題概要 個のブール変数から 個とった XOR たちを,AND と OR と NOT を使って作る.NOT の使用回数を最小化せよ. N = 1 のとき 何もしなければ正解です. N = 2 のとき なので, に NOT を使う…

Xmas Contest 2018 D: Devilish Dice 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_d 問題概要 個の 面さいころの目を上手く決めて,「どのさいころについても,他のあるさいころを選ぶと確率 以上でそれより大きい目が出せる」となる を最大化せよ. 考察 くろうさ「先にさいころ選…

Xmas Contest 2018 C: CombinatioN 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_c 問題概要 Pascal の三角形を書こうとしたが,ある場所で足し算を大きい値に間違えてしまった (→間違いがそこから伝搬).そして一部消えてしまった.というものが与えられるので,間違えた場所を特…

Xmas Contest 2018 B: Bit Smaller 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_b 問題概要 とか, とか,そういうののうち 以下のものをすべて求めよ. 解法 1 全探索しましょう.数の切り方は高々 通りしかないのでなんとかなると思います. 先頭のほうから切っていく感じで再帰…