AtCoder

お久しぶりです。れたすです。

fairy_lettuceさんのパナコン2021（AtCoder Beginner Contest 195）での成績：81位
パフォーマンス：2400相当
レーティング：1948→2002 (+54) :)
Highestを更新し、初段になりました！#AtCoder #パナソニックプログラミングコンテスト（ABC195） https://t.co/HUIasXMrTB
AtCoder 黄色！！！！！！ pic.twitter.com/zp28cVuxT3

— れたす (@lettuce_cs) March 13, 2021

解説記事を書くのはかなりお久しぶりになってしまいました。

問題リンク

https://atcoder.jp/contests/arc114/tasks/arc114_c

問題概要

$1$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A$ に対して、$f(A)$ を以下のように定義します。

• 長さ $N$ の数列 $X$ があり、初め全ての要素は $0$ である。$f(A)$ を、次の操作を繰り返して $X$ を $A$ に等しくするために必要な最小の操作回数とする。

  • $1\le l\le r\le N$ と $1\le v\le M$ を指定する。$1\le i\le r$ に対して $X_i$ を $\max(X_i,\ v)$ で置き換える。

全ての $A$ に対する $f(A)$ の和を $\bmod 998244353$ で求めてください。

制約

• $1\le N,\ M\le 5000$

ABC 反省文シリーズ。

問題リンク

https://atcoder.jp/contests/abc190/tasks/abc190_d

問題概要

整数からなる公差 $1$ の等差数列のうち、総和が $N$ であるものはいくつあるでしょうか？

制約

• $1\le N \le 10^{12}$

ABC 反省文シリーズです。

問題リンク

https://atcoder.jp/contests/abc189/tasks/abc189_f

問題概要

マス $0$ から始めてマス $N$ を目指す双六があります。高橋くんは $1$ から $M$ までの目が出るルーレットを回して進みます。また、この双六のマス $A_i\ (i=1,\ 2,\ ,\dots,\ K)$ は振り出しに戻るマスで、そこに止まるとマス $0$ に戻されます。

高橋くんがマス $N$ より先に着きゴールするまでにルーレットを回す回数の期待値を求めてください。到達不可能ならその旨を報告してください。

制約

• $1\le N,\ M\le 10^5$
• $0\le K\le 10$
• $0\lt A_1\lt \dots\lt A_K\lt N$

解きました。公式解説や有志の解説ブログを見ても自分と同じような考え方の人がいなかったので解説ブログを書きます。

問題リンク

https://atcoder.jp/contests/arc071/tasks/arc071_d

問題概要

$1,\ 2,\ 3,\ \dots,\ n$ からなる無限長の数列 $a_1,\ a_2,\ \dots$ のうち、次の条件を満たすものの個数を答えてください。

• $a_n=a_{n+1}=\dots$
• すべての $a_i$ について、$a_{i+1}=a_{i+2}=\dots=a_{i+a_i}$

制約

• $1\le n\le 10^6$

過去にやった問題が役に立ったので嬉しかったです。

問題リンク

https://atcoder.jp/contests/arc111/tasks/arc111_b

問題概要

$N$ 枚のカードがあり、各カードの両面には $a_i,\ b_i$ の色がついています。どちらかを表にするとき、表側の色の種類数の最大値はいくつになるでしょうか。

制約

• $1\le N\le 2\times 10^5$
• $1\le a_i,\ b_i\le 4\times 10^5$

最近の 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 含め統一しました。

今回はバチャでやった問題の反省文です。過去の 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)$ は相異なる