Growth Record of Lettuce Farm

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

Educational Codeforces Round 102 E - Minimum Path 解説

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 解説

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

問題リンク

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

問題概要

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

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

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

制約

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

続きを読む

Educational Codeforces Round 101 E - A Bit Similar 解説

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 解説

今回はバチャでやった問題の反省文です。過去の ABC の問題の解説になります。

問題リンク

https://atcoder.jp/contests/abc161/tasks/abc161_e

問題概要

高橋さんは N 日間のうち K 日を選んで働くことにしました。

  • 働く日どうしの間には C 日以上空ける
  • S_ix であるときは働かない。

これらの条件を満たすように働くとき、必ず働く日を全て求めてください。

制約

  •  1\le N\le 2\times 10^5
  •  1\le K\le N
  •  0\le C\le N
  • 問題文の条件を満たすように働くことができる
続きを読む

パナソニックプログラミングコンテスト (ABC186) F - Rook on Grid 解説

全完黄パフォ~~~!!!
ペナはもう少し縮まったはずなので反省も多いですが、最近の 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 二次予選 C イベント巡り (Event Hopping)

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} は全て異なる。

続きを読む