Competitive
この問題だけどうして問題名の最初が英小文字なのか気になってしまい夜も眠れません。
問題リンク
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$
この問題がこのセットで最難……。
問題リンク
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}$
…数列を当てる系のインタラクティブとても好きだし得意。この前の 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$ 回以内
同じ日の 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 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 contest 275 より。
実装ゲーでした。
問題リンク
https://yukicoder.me/problems/no/1292
問題概要
辺 a, b, c からなる面積 $1$ の三角形があります。どの辺について対称移動させるかの順序が文字列 $S$ で与えられるので、通過する面積を求めてください。
制約
$1\le |S| \le 2\times 10^{5}$
…AtCoder Problems に本日(11月17日)アップデートが入り、各問題の difficulty (以下、diff)の推定アルゴリズムが変わりました。これに伴いいくつかの問題で diff の色が変更になったため、色が変更になった問題をまとめます。
…
Rated コンテストにたくさん出たいのでこどふぉに出ました。冷えました。つらいです……。
今回はその冷えたこどふぉで解けなかった問題の解説です。解けて然るべき問題を解けなかった時の辛さは全競プロer共通だと勝手に思っています。
問題リンク
https://codeforces.com/contest/1447/problem/D
問題概要
文字列 $A,\ B$ の部分文字列を $C,\ D$ とします。$C,\ D$ のスコアを $4\times LCS(C,\ D)-|C|-|D|$ とします。ただし、$LCS(C,\ D)$ は $C,\ D$ の最長部分列の長さとします。スコアの最大値を求めて下さい。
部分文字列は連続していなければならず、部分列は連続していなくてもいいことに注意して下さい。
制約
$1\le |A|,\ |B|\le 5000$
…今回の問題解説では、JOI 2015 年の予選より、財宝 (難易度 8) を解説します。
思ったより苦戦させられ、周りの C# 使いの競プロerを巻き込んで一緒に TLE と格闘したので、その経緯も含めて解説します。
C# での定数倍高速化に関する知見を纏めた記事は多くないため、これが C# 競プロerの皆さんに役立つ知見となると嬉しいです。
問題リンク
https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_f
問題概要
$N$ 個の財宝があり、それぞれには市場価値 $X_i$ と貴重度 $Y_i$ が定められています。これらの財宝を Anna と Bruno の2人で分配します。2 人とも取らない財宝があってもですし、2 人とも取る財宝が 0 個でもいいです。
Anna は、Anna が取った財宝の市場価値の合計と Bruno が取った市場価値の合計の差の絶対値が $D$ 以下であれば満足します。
一方 Bruno は財宝の貴重度の合計を大きくしたいです。Anna が満足する取り方をした上で、Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を求めてください。
制約(満点)
- $1\le N\le 30$
- $0\le D,\ X_i,\ Y_i\le 10^{15}$
ICPC国内予選、eSeFとぽたてと一緒にチームchihominで出ました！
…