Growth Record of Lettuce Farm

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

AtCoder Beginner Contest 189 F - Sugoroku2

競プロ解説 AtCoder

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$

続きを読む

AtCoder Regular Contest 071 F - Infinite Sequence 解説

競プロ解説 AtCoder

解きました。公式解説や有志の解説ブログを見ても自分と同じような考え方の人がいなかったので解説ブログを書きます。

問題リンク

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$

続きを読む

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 含め統一しました。

続きを読む