参加しました yukicoder contest 368

記録

yukicoder contest 368 - yukicoder

4完, 86人中20位でした

解法・反省

A

No.2124 Guess the Permutation - yukicoder
提出 14:23 (2)

解法

順列という情報から, がわかる.
これと, 個のクエリによって, 式からなる 変数の1次連立方程式が立てられる.
次正方行列 , 行列 , を用いて と表すと, この連立方程式は が正則（つまり逆行列が存在する）なら, として連立方程式の解は一意に定まる.
連立方程式を解くアルゴリズムはガウス・ジョルダン法で だが, この制約 だと少々厳しい. それよりも, いい感じにクエリを投げて簡単に解く方がいい.
たとえば初回に とすれば がわかる. そこから, ( ) とすれば がわかる. 最後に, をすれば勝ち.
最初は でもいいと勘違いし WA. 自明すぎる

提出

Pypy3 #817664 (PyPy3) No.2124 Guess the Permutation - yukicoder

B

No.2125 Inverse Sum - yukicoder
提出 26:24 (1)

解法

これはさくさく考察が進んでよかった. この形式の方程式はわりと典型な気がする.
の分母を払うと . 移項して .
ここで競技数学・受験数学の定石というかテクニックだが, こういう式は因数分解の式を作るのが良い.
両辺 をかけて とすると, となる.
ここで, は の約数だから, の約数すべてについて調べればいいことになる. (負の約数も数えたが, 解説によれば数える必要はないらしい)
さて, を の約数, とすると という1次方程式が出る. 計算が出来なさすぎて手で解けなかった（は？）ので WolframAlpha 君に投げたら出してくれた. ちなみにぼくはあのサイトのことを「神」と呼んでいます.
らしい. なので, を で割った余りが で, なおかつ のときに答えに加える.
あとは の昇順ソートすればok.

提出

Pypy3 #817729 (PyPy3) No.2125 Inverse Sum - yukicoder

C

No.2126 MEX Game - yukicoder
提出 45:39 (2)

解法

これはペナが頻発する問題だと思う. 個人的に今回一番好きかも. でもARCとかで出たらバグりまくって発狂する.
先手のターンが終わって後手のGote君の番とする. Gote君が1個整数を変えて, Sente君が1個整数を変えて, …というようなことをたくさん繰り返す. Gote君が最終的な mex を減らそうとして数列の1要素を選ぶが, Sente君が次のターンでその要素を元に戻せばよい. これは真似っこ戦略と呼ばれてる. でも最後のターンでGote君が一回だけmexを減らせるチャンスがある.

の要素の出現回数をカウントした数列を とする. たとえば なら である.
Gote君がどんなときにmexを減らせるか？ のとき, 1個変えても無駄. でも のとき, それを変えれば を最終的なmexに変えられるかもしれない.
たとえば, のとき, 何もしなければ mex = 5 なのに, なのでそれを変えれば となって mex = 2 に変わる.

つまり, でmexになりうるものはとても危険！ということである, 先手の最初のターンでそれを 以上にしたい気持ちが芽生える.
は, に対して で, とする. にしたいが, 何を変えればよいのか？
で が存在したら, その を変えればOK.
で が存在したら, その を変えればOK.
で, となるものがあったとき, それはもうmexの上限となるから, から自由にとっていい.

これでいいはず（たぶん）. かなり複雑だったけど面白い.

提出

Pypy3 #817827 (PyPy3) No.2126 MEX Game - yukicoder

D

No.2127 Mod, Sum, Sum, Mod - yukicoder
提出 72:50 (0)

解法

★2.5にしてはかなり難しかった. 最初は実験エスパーをしてOEISゲーに帰着しようとしたが, いい情報は得られなかったので自分で考察することにした.

を固定してその和を求めてみる. を動かせば は と続く.
これは周期性があるが, 1周期の総和は, 和の公式より である. を まで動かしたときこれが何周期あるかというと, 周期である. よって周期分の がまず得られる.
あと余ったやつだが, 項 あるので, である.
よってあわせて .
これで, の固定をはずせば となる. しかし, これでは甘い. もっと削減だ. 式を整理すると

となる. まずは
だが,
の値のとりうる値の種類数はだいたい である. よって, それを列挙して, まとめて計算すればよい. の方には , の方には の和の公式を使う.
連載 しょぼんコーダー 5 floor(N/i)を楽に列挙する方法 - しょぼんブログ に の簡単な列挙方法が書いてある. ぼくは覚えてないのでこれを見て写した.
だが, まず, という式は思いつく必要がある. そうすると, はさっきの場合に帰着できる.

も, ちょっと複雑になってるが同じくさっきの方法に帰着できる.
よって で解けた.

提出

Pypy3 #817959 (PyPy3) No.2127 Mod, Sum, Sum, Mod - yukicoder

E

No.2128 Round up!! - yukicoder
提出 コンテスト後

解法

でやっていって公倍数にあたったとき止まる. でも回数は不安になる. ちょっと実験してみると, から操作するとき なら は と順に出現していることがわかる. これが の最小公倍数まで続くということである.
から までの操作回数は, は をとり, は と との間, と との間を1回ずつ埋めるから 個である.
が与えられて, そこから に達するまでは愚直に計算する. (高々2回なので間に合う)
ここで注意すべきなのは, の場合. 貪欲で小さい方→大きい方と進むと となってしまい, 到達できるはずの をスキップしてしまう.（ぼくはテストケースを見るまで気付きませんでした）なのでここの愚直計算は地味にきつい.
までにとりうる回数 + が答えになる. オーバーフローに注意する必要があるが, Pythonは特権があるので（計算は遅れるが）ある程度なら気にしなくてもよい.

提出

Pypy3 #818166 (PyPy3) No.2128 Round up!! - yukicoder