Xmas Contest 2020

Xmas Contest 2020 にご参加いただいた皆様,どうもありがとうございました! 大変遅くなりましたが解説記事が準備できました.略解を AtCoder 上に載せて一息ついたのもあって 2019 よりもさらに遅くなってしまいました…….その分濃い情報を提供できている…

Xmas Contest 2020 I: Implement Me 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_i 問題概要 は, のうち が 個以上なら で, 個未満なら である.この だけを使って与えられた関数 が作れるか判定し,作れる場合は実装せよ. 簡単な場合 部分点が についています.この部分点自体…

Xmas Contest 2020 H: Hierarchical Phylogeny 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_h 問題概要 頂点に の空でない部分集合のラベルがついた根付き木であって,各頂点が 子が 個で,ラベルが指定された部分集合 () のいずれか 子が 個で,ラベルが子のラベルの非交和 のいずれかである…

Xmas Contest 2020 G: Graph Products 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_g 問題概要 無向単純グラフ に対し,"Cartesian product" と "tensor product" が同型か判定せよ. 考察 サンプルは全然あてになりません.クリスマスだから許されている (許されていますか?) 無み…

Xmas Contest 2020 D: Determinant 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_d 問題概要 行列 の 成分は のとき のとき かつ のとき である. を求めよ. 行列式の処理 対角だけ変なことになっているので,対角をどう使うかで場合分けします. だと思って,行列式の定義の各項 …

Xmas Contest 2020 C: Candies Candidates 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_c 問題概要 数列中の正の整数 を または に変えられるゲームがある.与えられた数列が先手必勝か後手必勝か判定せよ. とりあえず 値が減っていく不偏ゲームなので (short impartial game なので),…

Xmas Contest 2020 B: Beterminant 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_b 問題概要 円払うと % で 円もらえる賭けを 回やって最終的に所持金が増えている確率が を超えるような最大の を求めよ.存在しない場合や無限個存在する場合はそれを指摘せよ. 考察 として,所持…

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 全探索しましょう.数の切り方は高々 通りしかないのでなんとかなると思います. 先頭のほうから切っていく感じで再帰…