Growth Record of Lettuce Farm

競プロの記録・解説をします

yukicoder No. 1354 - Sambo's Treasure 解説

競プロ解説 yukicoder

灘中入試コンテスト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

続きを読む

AtCoder Regular Contest 111 B - Reversible Cards 解説

競プロ解説 AtCoder

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

問題リンク

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 Round 102 E - Minimum Path 解説

競プロ解説 Codeforces

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$

続きを読む

AtCoder Beginner Contest 188 F - +1-1x2 解説

競プロ解説 AtCoder

最近の ABC は調子良かったんですが、今回はありとあらゆる失敗を詰め込んだ破滅回でした。もう反省だらけです。

【追記】嘘解法であることが発覚したので、その部分を訂正して正当な解法にしました。

問題リンク

https://atcoder.jp/contests/abc188/tasks/abc188_f

問題概要

整数 $X$ を整数 $Y$ にしたいです。以下の操作を何回でもできます。

整数を $1$ 増やす。
整数を $1$ 減らす。
整数を $2$ 倍する。

最小で何回操作する必要があるでしょうか。

制約

$1\le X,\ Y\le 10^{18}$

続きを読む

【謹賀新年】ID変更のご報告

競プロその他 AtCoder Codeforces

あけましておめでとうございます！

本年の抱負は何事もなく無事進級すること、及び AtCoder 橙達成 (中間目標として 3 月までに黄色) です。今年もよろしくお願いいたします。

ID変更のご報告

Codeforces では毎年恒例のユーザー名変更が可能な時期となりましたので、AtCoder 及び Codeforces の ID を fancy_lettuce から fairy_lettuce に変更し、Topcoder 含め統一しました。

続きを読む

Educational Codeforces Round 101 E - A Bit Similar 解説

競プロ解説 Codeforces

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$

続きを読む

AtCoder Beginner Contest 161 E - Yutori 解説

競プロ解説 AtCoder

今回はバチャでやった問題の反省文です。過去の 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$
問題文の条件を満たすように働くことができる

続きを読む