2021-04-12

AtCoder Beginner Contest 198 E - Unique Color 解説

競プロ解説 AtCoder

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

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$
与えられるグラフは木

2021-04-12

AtCoder Beginner Contest 198 D - Send More Money 解説

競プロ解説 AtCoder

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

問題リンク

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

問題概要

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

制約

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

2021-04-03

AtCoder 黄色になりました

色変記事 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
— れたす (@fairly_lettuce) 2021年3月13日

今回はこの通り、AtCoder 黄色になったので、そのご報告とか色々をいたします。

前回 (AtCoder 青色・その他) の色変記事
色変報告
AtCoder 黄色になるまでにやったこと
- 精進記録
- 身につけたアルゴリズム・データ構造
  - 何の迷いもなく書ける・使えるようになった
  - 調べたら使える・ちょっと苦労するけど書ける程度
  - あまり理解していない
青のときから変わったこと
おわりに

2021-03-19

AtCoder Regular Contest 114 C - Sequence Scores 解説

競プロ解説 AtCoder

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

問題リンク

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)$ で置き換える。