2022-12-20

AtCoder Regular Contest 129 D - -1+2-1 解説 (エスパー→証明)

競プロ解説 AtCoder

エスパーです。正直こっちのほうが分かりやすいです。

厳密ではありませんが証明はちゃんとつけました。

問題リンク

https://atcoder.jp/contests/arc129/tasks/arc129_d

問題概要

長さ $N$ の整数列 $(A_1, \dots, A_N)$ があります。この整数列の両端は繋がっています。

$A_{i-1}, A_i, A_{i+1}$ にそれぞれ $-1,2,-1$ を何回か足すことによって $A_i$ を全て $0$ にできるか判定し、できるなら最小回数を求めて下さい。

制約

$3\le N\le 200000$
$-100\le A_i \le 100$
入力は全て整数

2022-04-30

Google Code Jam Round 1C 2022 B - Squary 解説

競プロ解説 GCJ

おもしろかった。気付いたときうわーーーーって言いました。

問題リンク

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877b42/0000000000afdf76

2023/07/16 追記 GCJ のサイトが閉じられたので、代替となるリンクを貼ります。

https://github.com/google/coding-competitions-archive/tree/main/codejam/2022/round_1c/squary

なお、GCJ の過去問のデータはこのリポジトリで参照できます。

問題概要

数列 ${E_i}$ に、 $K$ 個以下の整数 ( $-10^{18}$ 以上 $10^{18}$ 以下) を追加し、以下の等式が成り立つようにしてください。

$\displaystyle \sum E_i^2=\left(\sum E_i \right)^2$

制約

$1\le T\le 100$ (テストケース数)
$1\le N\le 1000$ (数列の長さ)
$-1000\le E_i\le 1000$

小課題

小課題 1 (9pts): $K=1$
小課題 2 (22pts): $2\le K \le 1000$

2021-11-09

AtCoder Beginner Contest 091 C / AtCoder Regular Contest 092 A - 2D Plane 2D Points 解説スライド

競プロ解説 AtCoder

計算機プログラミングの授業では解説しなかったため没となったスライドを供養します。

本番では使用してないですがほぼ完成しています。あくまでスライドなので、普段の解説記事よりは簡潔かと思います。

drive.google.com

2021-11-09

AtCoder Grand Contest 029 B - Powers of two 解説スライド

競プロ解説 AtCoder

お久しぶりです。

計算機プログラミングの授業でこの問題の解説をしたので、普段の解説記事とは違う形式ですがそのスライドを公開しようと思います (教員には許可を取っております)。

drive.google.com

最近競技プログラミングを休んでいたのでかなりお久しぶりになっていました。ABC どころか Rated も出ていない……。

ゆっくりのんびり、余裕のある程度にまたやろうかなと思います。

2021-06-01

AtCoder Regular Contest 046 D - うさぎとマス目解説

競プロ解説 AtCoder

なんか全然公式解説と違うことしてました……。

問題リンク

https://atcoder.jp/contests/arc046/tasks/arc046_d

問題概要

$H$ 行 $W$ 列からなるグリッドグラフがあります。

このグラフにおいて、 $(i,j)$ から $((i+1) \bmod H, j)$ または $(i,(j+1) \bmod W)$ に移動できます。

マス $(0,0)$ からスタートして全てのマスを通り、 $(0,0)$ に戻ってくるような経路の数を $\bmod 10^9+7$ で数え上げてください。

制約

$1\le H,W\le 10^6$

2021-05-20

Educational Codeforces Round 91 E - Merging Towers 解説

競プロ解説 Codeforces

解説記事や 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$ はどちらのタワーもそのクエリの時点で存在するようなものが与えられる。

2021-05-02

ZONeエナジープログラミングコンテスト “HELLO SPACE” F - 出会いと別れ / Encounter and Farewell 解説

競プロ解説 AtCoder

問題リンク

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)$ は張れません。