yukicoder

yukicoder No. 1354 - Sambo's Treasure 解説

2021-01-17

灘中入試コンテストday2-E でした。実装が重かったです。無限に実装をバグらせてしまい、自らの実装力の無さを嘆きました。

問題リンク

問題概要

$x,\ y$ 座標ともに $0,\ 1,\ \dots,\ N$ からなる竹藪があります。サンボ君はこの竹藪の $M$ 個のチェックポイントを全て通りつつ $(0,\ 0)$ から $(N,\ N)$ へと移動したいです。移動は右または下にのみ可能です。

ただし、竹藪には $L$ 体のトラが棲んでいます。トラのいるマスには最大でも $K$ 回までしか通れません。

条件を満たすような移動のしかたは何通りあるでしょうか。$998244353$ で割った余りを求めてください。

制約

$1\le N\le 2\times 10^{5}$
$0\le M\le \min(10^5,\ N-1)$
$0\le L\le \min(100,\ (N+1)^2-2)$
$0\le K\le 10^5$
チェックポイントの座標について、$0\lt xc_i,\ yc_i\lt N$
$xc_i\lt xc_{i+1},\ yc_i\lt yc_{i+1}$
トラの座標について、$0\le xt_i,\ yt_i\le N,\ (xt_i,\ yt_i)\ne (0,\ 0),\ (N,\ N)$
トラの座標は Distinct

…

yukicoder No. 1314 - N言っちゃダメゲーム (5)

競プロ解説 yukicoder Competitive

2020-12-11

ネタ被りが前日に発覚して (4) が (5) になるってどんな偶然なんですか？？

問題リンク

https://yukicoder.me/problems/no/1314#

問題概要

N言っちゃダメゲームをします。つまり、先手であるあなたは $0$ から始め、お互いに $[1,\ K]$ の整数を加算したものを言っていき、$N$ 以上の整数を言った人の負けです。
$N$ は今回 $2$ 以上 $M$ の各整数を用います。先手の人は残っているものの中から好きなものを選び、その回の $N$ とします。一度使った数は以降使えなくなります。$2$ 回目以降のゲームは前回負けたプレイヤーが先手をします。

お互いに各ゲームではわざと負けたりしない条件のもと勝つ回数を最大化します。あなたが勝つか負けるか、引き分けになるかを求めてください。

制約

$2\le M,\ K\le 10^{9}$

…

yukicoder No. 1313 - N言っちゃダメゲーム (4)

競プロ解説 yukicoder Competitive

2020-12-10

問題リンク

https://yukicoder.me/problems/no/1313

問題概要

先攻のプレイヤーであるあなたは $0$ から始めます。交互に $[1,\ K]$ のうちのどれかの整数を加算していきます。$N$ 以上の数字、または予め指定された危険な数字を言ってしまうと負けです。

あなたが勝つ場合は最初に宣言して勝てる数字を全て出力してください。あなたが負ける場合は $0$ を出力してください。

制約

$N,\ K$ は整数
$1\le K\lt N\le 2\times 10^{5}$
$|S|=N-1$
$S_{i}$ が x のときは $i$ は「危険な数字」で、o のときはそうではない

…

yukicoder No. 1312 - Snake Eyes (Advent Calendar Contest 2020 - I) 講評

Writer記録 yukicoder Competitive

2020-12-09

これから私が yukicoder において Writer/Tester をした問題やコンテストの講評は開催されるたびに上げようと思います。当然ですが、問題のネタバレを含みます。

私の Writer をした問題では初出題です。yukicoder 毎年恒例のアドカレコンのうち 1 問を担当させて頂きました。色々不慣れな点もありましたが無事出題でき、良かったです。Tester のりあんさんには感謝です！

yukicoder No.1312 Snake Eyes

yukicoder Advent Calendar Contest 2020 の 12 月 9 日公開問題です。

問題ページ
https://yukicoder.me/problems/no/1312

…

yukicoder No.1311 - Reverse Permutation Index 解説

競プロ解説 yukicoder Competitive

2020-12-08

yukicoder Advent Calendar Contest 2020 の 12/08 出題問題です。

一見すると $N,\ S$ の間に簡単な法則が成り立ちそうですが、どうなんでしょう。面白いですね。

問題リンク

https://yukicoder.me/problems/no/1311

問題概要

ある順列が辞書順で出てくる順番をインデックスと呼びます。また、$S$ 要素で $1$-indexed な順列 $a$ に対して $b$ が $a_{b_{i}}=i (i=1,\ 2,\ \dots,\ s)$ を満たすとき、$b$ を $a$ の逆置換と呼びます。
$S$ 要素の順列の中で、$N$ 番目の順列の逆置換のインデックスを求めてください。

制約

$0\le N\lt S! \lt 2^{64}$
$1\le S\le 20$

…

yukicoder No. 1310 - 量子アニーリング解説

競プロ解説 yukicoder Competitive

2020-12-07

yukicoder Advent Calendar Contest 2020 の 12/07 出題問題です。

みんながぐろふぉに出ている中の出題だったため¹、FA を狙えないかと思っていましたが残念ながら 3 番目の AC でした。

問題リンク

https://yukicoder.me/problems/no/1310

問題概要

$N$ 要素の $+1,\ -1$ のどちらかからなる数列 $s$ に対して、

$\displaystyle E=-\sum_{i=1}^{N}s_i s_{i+1}$

とします。ただし $s_{N+1}=s_{1}$ です。$2^{|E|}$ の総和を $998244353$ で割った余りを求めてください。

制約

$3\le N\le 2\times 10^{5}$

…

yukicoder No. 1306 - Exactly 2 Digits 解説

競プロ解説 yukicoder Competitive

2020-12-03

yukicoder Advent Calendar Contest 2020 の 12/03 出題問題です。

教育的問題除く ★4 初 AC！(★3.5 の AC が無いのは内緒) ちなみに 16 番目の AC でした。時間はかかったけれど、高難易度の問題をじっくり攻略するのは楽しいです。

おことわりですが、問題を解いた後ぼーっとしながら思考をそのまま書き連ねているので、解説の体を成していないかもしれません(ごめんなさい)。「考察」の内容は解説というよりは私の思考手順をなるべく細かく文章にしたものです。解説記事については、「私と同じ知識を有する人が同じ問題が全く分からなかった際に見て思考を追える文章」をモットーにしているので、いささか回りくどいかもしれません。その代わり、「解法」パートは簡潔に解き方をまとめようと思うので、どうかご容赦ください。
解説をどれくらいの細かさで書くかは本当に人々の思想だと思うんですけれど(ABC の解説を見ているとよく分かります……)、どうしたらいいんでしょうか……。

問題リンク

https://yukicoder.me/problems/no/1306

問題概要

インタラクティブ数当てゲーム。

$\{N,\ N+1,\ \dots ,\ N^2 -1\}$ をちょうど $1$ つずつ含む順列 $A$ があります。この順列を以下のクエリを高々 $1.5\times(N^2-N)$ 回行うことで特定してください。

? i j
1. $p=\lfloor A_i/N\rfloor-\lfloor A_j/N\rfloor$ とする。つまり、$A_i,\ A_j$ の $N$ の位の差。
2. $q=\lfloor A_i%N\rfloor-\lfloor A_j%N\rfloor$ とする。つまり、$A_i,\ A_j$ の $1$ の位の差。
3. もし $p\lt q$ なら $p,\ q$ を swap する。
4. $p,\ q$ が返される。

数列を特定したら、! に続けて数列を出力してください。

ただし、出力したクエリによって完全に数列を特定できることができない状態で数列を答えても AC とはなりません(adaptive なジャッジ)。