Growth Record of Lettuce Farm

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

AtCoder Beginner Contest 184 D - increment of coins 解説

競プロ解説 AtCoder

この問題だけどうして問題名の最初が英小文字なのか気になってしまい夜も眠れません。

問題リンク

https://atcoder.jp/contests/abc184/tasks/abc184_d

問題概要

袋の中に金貨が A 枚、銀貨が B 枚、銅貨が C 枚入っています。
袋の中から硬貨をランダムに選び、それと同じ種類の硬貨をもう 1 枚入れるのをいずれかの種類の硬貨が 100 枚になるまで繰り返します。
操作回数の期待値を求めてください。

制約

0\le A,\ B,\ C\le 99
A+B+C\ge 1

続きを読む

AtCoder Beginner Contest 184 C - Super Ryuma 解説

競プロ解説 AtCoder

この問題がこのセットで最難……。

問題リンク

https://atcoder.jp/contests/abc184/tasks/abc184_c

問題概要

斜めにどこまででも進め、また マンハッタン距離 が 3 以下である場所に進める駒「超竜馬」があります。
(r_{1},\ c_{1}) から (r_{2},\ c_{2}) へ動くのに必要な最小手数を求めてください。

制約

1\le r_{1},\ c_{1},\ r_{2},\ c_{2}\le 10^{9}

続きを読む

Codeforces Round #685 Div.2-E1/E2 - Bitwise Queries 解説

競プロ解説 Codeforces

数列を当てる系のインタラクティブとても好きだし得意。この前の JOI の数当てもそうだったけど、こういう問題を考えるのがとても楽しいと思えます。

問題リンク

E1 (Easy Version): https://codeforces.com/contest/1451/problem/E1
E2 (Hard Version): https://codeforces.com/contest/1451/problem/E2

問題概要

n 要素からなる数列 a を当てるインタラクティブ問題。解答者はプログラムの中で以下の質問をすることができます。

  • AND i j: a_{i} と a_{j} の AND を質問する。
  • OR i j: a_{i} と a_{j} の OR を質問する。
  • XOR i j: a_{i} と a_{j} の XOR を質問する。

規定の回数以内の質問で元の数列を当ててください。

制約

4\le n\le 2^{16}
n は 2 の冪である
Easy: 質問の回数は n+2 回以内
Hard: 質問の回数は n+1 回以内

続きを読む

Codeforces Round #685 Div.2-D - Circle Game 解説

競プロ解説 Codeforces

同じ日の ARC で -55 もレート溶かしたのに同じ日のこどふぉでレート超盛りました。Codeforces は調子いいのに、AtCoder の下振れが酷いです。助けて。

問題リンク

https://codeforces.com/contest/1451/problem/D

問題概要

x-y 座標上の円 x^{2}+y^{2}=d^{2} があります。この円の中でマスを動かすゲームをします。
マスは最初 (0,\ 0) にあり、ふたりはお互いのターンで x,\ y 座標どちらかの正の向きにちょうど k だけ進めます。円の外に出たら負けです。勝者は先手か後手か求めてください。

制約

1\le d \le 10^{5}
1\le k \le 10^{5}

続きを読む

yukicoder No. 1293 - 2種類の道路 解説

競プロ解説 yukicoder

yukicoder contest 275 より。
個人差が強い問題。発想出来るかが分かれ目？yukicoder problems では黄 diff とのことですが[^1]、人によっては黄相応だと思う人も青程度と思う人もいると思います。

問題リンク

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

問題概要

N 個の都市には D 本の自動車専用道路と W 本の歩行者専用があります。
0 本以上の自動車専用道路を通った後に 0 本以上の歩行者専用道路を通ることで移動できる都市のペアの個数(自身どうしのペアを含まない)を求めてください。

制約

2\le N\le 10^{5}
1\le D,\ W\le \min\left(10^{5},\ \frac{N(N-1)}{2}\right)

続きを読む

yukicoder No. 1292 - パタパタ三角形 解説

競プロ解説 yukicoder

yukicoder contest 275 より。
実装ゲーでした。

問題リンク

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

問題概要

辺 a, b, c からなる面積 1 の三角形があります。どの辺について対称移動させるかの順序が文字列 S で与えられるので、通過する面積を求めてください。

制約

1\le |S| \le 2\times 10^{5}

続きを読む

AtCoder Problems の diff 推定アルゴリズムの変更に伴い色が変わった問題まとめ

競プロその他 AtCoder

AtCoder Problems に本日(11月17日)アップデートが入り、各問題の difficulty (以下、diff)の推定アルゴリズムが変わりました。これに伴いいくつかの問題で diff の色が変更になったため、色が変更になった問題をまとめます。

続きを読む