Xmas Contest 2019

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 小さいので,手で遊んで解けます.しかし,解くだけなら簡単ですが最小手数は非自明だった…