JOI

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

今回の問題解説では、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}$

お久しぶりの記事です。暇なので競プロの問題の解説をしてみることにしました。のんびり解説記事を書きたいので自分が解けた中で難しい問題や自分の解法が他の解説と違ったものに絞り解説しようと思います。

初めての解説記事はJOI春合宿より「数当て」(難易度 9) です。

問題ページ

https://atcoder.jp/contests/joisc2011/tasks/joisc2011_guess

問題概要

インタラクティブ問題です。$1$ から $N$ を並び替えた順列を予想して、合致する箇所の個数が知らされるのでその順列を当てようという問題です。予想できるのは合計$L$回までです。

制約(満点)

• $1\le N\le100$
• $L=700$