TL;DR n\k -4 -3 -2 -1 0 1 2 3 4 -4 1 0 0 0 1 -4 10 -20 35 -3 -3 1 0 0 1 -3 6 -10 15 -2 3 -2 1 0 1 -2 3 -4 5 -1 -1 1 -1 1 1 -1 1 -1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 2 0 0 0 0 1 2 1 0 0 3 0 0 0 0 1 3 3 1 0 4 0 0 0 0 1 4 6 4 1 主な対…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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