Competitive Programming Editorial & Misc Articles

解説記事や Editorial などをざっくり見ても自分の解法の解説が無かったので。

問題リンク

https://codeforces.com/contest/1380/problem/E

問題概要

$n$ 個の皿が $m$ 個のタワーに置かれています。皿は直径がそれぞれ $1,2,\dots,n$ であり、直径が $i$ である皿はタワー $t_i$ に置かれています。また、各タワーには上から直径が小さい順に皿が置かれています。

あなたは $m$ 個のタワーのうち $1$ つに全ての皿が乗っているようにしたいです。タワーは以下の操作を何回か行うことでまとめます。

• 好きな $i,j\ (1\le i,j\le m,\ i\ne j)$ を選ぶ。タワー $i$ から上から何個か (全部でも良い) の皿を取り、同じ順番でタワー $j$ の上に置く。このとき、動かす皿は全て操作前のタワー $j$ の一番上の皿よりも小さくてはならない。

タワーを $1$ つにまとめるのに必要な操作回数の最小値を、タワーをまとめる難易度と呼ぶことにします。

さて、$m-1$ 個のクエリ $a_i,b_i$ が与えられます。$i$ 個目のクエリはタワー $b_i$ の皿を全てタワー $a_i$ の皿とまとめ、新たなタワー $a_i$ にすることを意味します。新たなタワーも皿は上から小さい順になるようにします。これは難易度には関係しません。

全ての $k=0,1,2,\dots,m-1$ について、$k$ 番目のクエリまでを処理した状態でのタワーをまとめる難易度を求めてください。

制約

• $2\le m\le n\le 2\times 10^5$
• $1\le t_i\le m$
• $1,2,\dots,m$ までの整数がそれぞれ少なくとも 1 回以上 $t_i$ に現れる。
• $1\le a_i,b_i\le m,\ a_i\ne b_i$
• クエリ $a_i,b_i$ はどちらのタワーもそのクエリの時点で存在するようなものが与えられる。

問題リンク

https://atcoder.jp/contests/zone2021/tasks/zone2021_f

問題概要

$N=2^n$ 個の頂点 $0,1,2,\dots,N-1$ について、$N-1$ 個の辺 $(i,j)$ を張って全域木を構成したいです。ただし、$(i,j)$ について、$i\oplus j$ が $A_1,A_2,\dots,A_M$ のいずれかと一致するような辺 $(i,j)$ は張れません。

全域木が構成できるか判定し、出来る場合は構成の仕方を $1$ つ示してください。

制約

• $N=2^n$ として、$1\le n\le 18$
• $0\le M\le N-1$
• $0\lt A_1\lt A_2\lt\dots\lt A_M\lt N$

謎制約。

問題リンク

https://codeforces.com/contest/1517/problem/D

問題概要

$n\times m$ のグリッドグラフが与えられます。$4$ 近傍で繋がっている各辺には道の長さが与えられています。

全ての $(i,j)$ について、$k$ 回移動を繰り返して最初の位置 $(i,j)$ に戻ってくるとき、移動経路の距離の最小値を答えてください。戻ってこれなければ -1 としてください。

制約

• $2\le n,m\le 500$
• $1\le k\le 20$
• $1\le (各辺の長さ)\le 10^6$

最近似た問題を見ていたのでその解説を見て難しい解法にハマりました。

Editorial と同じ解法と、自分の解法を両方紹介します。

問題リンク

https://atcoder.jp/contests/abc198/tasks/abc198_e

問題概要

$N$ 頂点の木が与えられます。頂点 $i$ は色 $C_i$ で塗られています。

頂点 $1$ から $x$ への最短パスに色 $C_x$ が頂点 $x$ 以外に現れないような頂点を良い頂点と呼びます。良い頂点を列挙してください。

制約

• $2\le N\le 10^5$
• $1\le C_i\le 10^5$
• 与えられるグラフは木

久々に ABC でやったらいけないミスした……。

問題リンク

https://atcoder.jp/contests/abc198/tasks/abc198_d

問題概要

覆面算 $S_1+S_2=S_3$ を解いてください。

制約

• $1\le |S_i|\le 10$
• $S_i$ は英小文字のみからなる。

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

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$