Competitive
最近の ABC は調子良かったんですが、今回はありとあらゆる失敗を詰め込んだ破滅回でした。もう反省だらけです。
【追記】嘘解法であることが発覚したので、その部分を訂正して正当な解法にしました。
問題リンク
https://atcoder.jp/contests/abc188/tasks/abc188_f
問題概要
整数 $X$ を整数 $Y$ にしたいです。以下の操作を何回でもできます。
- 整数を $1$ 増やす。
- 整数を $1$ 減らす。
- 整数を $2$ 倍する。
最小で何回操作する必要があるでしょうか。
制約
$1\le X,\ Y\le 10^{18}$
…あけましておめでとうございます！
本年の抱負は何事もなく無事進級すること、及び AtCoder 橙達成 (中間目標として 3 月までに黄色) です。今年もよろしくお願いいたします。
ID変更のご報告
Codeforces では毎年恒例のユーザー名変更が可能な時期となりましたので、AtCoder 及び Codeforces の ID を fancy_lettuce から fairy_lettuce に変更し、Topcoder 含め統一しました。
…C 問題は問題文が読みにくくて少しつらかったけど、D 問題も E 問題も面白くて楽しいセットでした。本番ギリギリ E が間に合わなくてつらかった……。
問題リンク
https://codeforces.com/contest/1469/problem/E
問題概要
ふたつの文字列 $a,\ b$ について、同じ位置に同じ文字が存在するような位置がひとつでもある場合、a bit similar といいます。
0 および 1 からなる文字列 $s$ について、その長さ $k$ の部分文字列全てと a bit similar である長さ $k$ の文字列のうち、辞書順最小のものを求めてください。そのような文字列が存在しない場合はその旨を報告してください。
制約
$1\le k\le n\le 10^6$
…今回はバチャでやった問題の反省文です。過去の ABC の問題の解説になります。
問題リンク
https://atcoder.jp/contests/abc161/tasks/abc161_e
問題概要
高橋さんは $N$ 日間のうち $K$ 日を選んで働くことにしました。
- 働く日どうしの間には $C$ 日以上空ける
- $S_i$ が
xであるときは働かない。
これらの条件を満たすように働くとき、必ず働く日を全て求めてください。
制約
- $1\le N\le 2\times 10^5$
- $1\le K\le N$
- $0\le C\le N$
- 問題文の条件を満たすように働くことができる
全完黄パフォ～～～！！！
ペナはもう少し縮まったはずなので反省も多いですが、最近の ABC は失敗ばかりだったのでとにかく嬉しいです！
問題リンク
https://atcoder.jp/contests/abc186/tasks/abc186_f
問題概要
縦 $H$ マス、横 $W$ マスのグリッドがあります。また、グリッド上には $M$ 個の障害物があり、$i$ 番目は $(X_i,\ Y_i)$ に置かれています。
障害物にぶつかるまで右または下にずっと移動できる飛車のコマがマス $(1,\ 1)$ にあります。飛車が $2$ 手で到達できるマスの数を求めてください。
制約
- $1\le H,\ W\le 2\times 10^5$
- $0\le M\le 2\times 10^5$
- $(X_i,\ Y_i)\neq (1,\ 1)$
- $(X_i,\ Y_i)$ は相異なる
JOI 2021 二次予選をバチャしました。難しかったし、納得いく結果が出せませんでしたが、面白い問題でした！
問題リンク
https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_c
問題概要
$2$ つの街があり、合計 $N$ 個のイベントが行われます。イベント $i$ は街 $P_i$ で開催され、時間は $(S_i,\ S_i+1)$ の間行われます。
JOI 君はこれらのイベントに参加します。どちらの街から始めることができ、それまでに参加したイベント数を $j$ 個とすると、$D+K\times j$ だけ街の間の移動に時間がかかります。
参加できるイベント数の最大値を求めてください。
制約 (満点)
$1\le N\le 200\ 000$
$1\le D\le 10^{12}$
$0\le K\le 10^{12}$
$1\le P_{i} \le 2$
$1\le S_{i} \le 10^{12}$
$S_{i}$ は全て異なる。
やらかし反省録が増えました！！！！！！！！！！！！！！！！！！！
問題リンク
https://atcoder.jp/contests/abc185/tasks/abc185_e
問題概要
$N,\ M$ 要素からなる整数列 $A,\ B$ があります。$A,\ B$ からいくつかの要素をコスト $1$ で取り除くことができます。取り除いたあと、$A,\ B$ の要素数が同じでなくてはなりません。
取り除いたあとの $A,\ B$ について $A_i\neq B_i$ である要素があれば、その個数だけコストが $1$ ずつ上乗せされます。
コストの最小値を求めてください。
制約
$1\le N,\ M\le 1000$
$1\le A_i,\ B_i\le 10^{9}$
ネタ被りが前日に発覚して (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}$
…問題リンク
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 において Writer/Tester をした問題やコンテストの講評は開催されるたびに上げようと思います。当然ですが、問題のネタバレを含みます。
私の Writer をした問題では初出題です。yukicoder 毎年恒例のアドカレコンのうち 1 問を担当させて頂きました。色々不慣れな点もありましたが無事出題でき、良かったです。Tester のりあんさんには感謝です！
yukicoder No.1312 Snake Eyes
yukicoder Advent Calendar Contest 2020 の 12 月 9 日公開問題です。
…