Competitive Programming Editorial & Misc Articles

灘中入試コンテストday2-E でした。実装が重かったです。無限に実装をバグらせてしまい、自らの実装力の無さを嘆きました。

問題リンク

https://yukicoder.me/problems/no/1354

問題概要

$x,\ y$ 座標ともに $0,\ 1,\ \dots,\ N$ からなる竹藪があります。サンボ君はこの竹藪の $M$ 個のチェックポイントを全て通りつつ $(0,\ 0)$ から $(N,\ N)$ へと移動したいです。移動は右または下にのみ可能です。

ただし、竹藪には $L$ 体のトラが棲んでいます。トラのいるマスには最大でも $K$ 回までしか通れません。

条件を満たすような移動のしかたは何通りあるでしょうか。$998244353$ で割った余りを求めてください。

制約

• $1\le N\le 2\times 10^{5}$
• $0\le M\le \min(10^5,\ N-1)$
• $0\le L\le \min(100,\ (N+1)^2-2)$
• $0\le K\le 10^5$
• チェックポイントの座標について、$0\lt xc_i,\ yc_i\lt N$
• $xc_i\lt xc_{i+1},\ yc_i\lt yc_{i+1}$
• トラの座標について、$0\le xt_i,\ yt_i\le N,\ (xt_i,\ yt_i)\ne (0,\ 0),\ (N,\ N)$
• トラの座標は Distinct

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

問題リンク

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$

Educational Codeforces 初めての Unrated 参加でした。見事に出来ないといけない問題が解けずに Educate されました。

問題リンク

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

問題概要

$n$ 頂点 $m$ 辺の重み付き有向連結グラフが与えられます。ここで、二頂点間のパスの距離を、通る辺の重みの総和に、重みの最小値を足して、最大値を引いたものと定義します。頂点 $1$ から各頂点への距離の最小値を求めてください。

制約

• $2\le n\le 2\times 10^5$
• $1\le m\le 2\times 10^5$
• $1\le w_i\le 10^9$

最近の 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}$