競プロ解説

文字列 $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 予選 F - 財宝 (Treasures) 解説 (おまけ: C#での定数倍高速化に関する知見)

競プロ解説 JOI Competitive

2020-11-11

今回の問題解説では、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 2010-2011 春合宿数当て (Guess Them All) 解説

競プロ解説 JOI Competitive

2020-11-03

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

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

問題ページ

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

問題概要

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

制約(満点)

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

…