Competitive Programming Editorial & Misc Articles

今回の問題解説では、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で出ました！

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

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

問題ページ

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

問題概要

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

制約(満点)

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

先日の エイシング プログラミング コンテスト 2020 で、AtCoder水色になりました！！！！！！！！！！！！！！！！！！！！！！

fancy_lettuceさんのエイシング プログラミング コンテスト 2020での成績：837位
パフォーマンス：1599相当
レーティング：1166→1218 (+52) :)
Highestを更新し、4 級になりました！#AtCoder #エイシングプログラミングコンテスト2020 https://t.co/72e591XRhS
青パフォ逃しましたが入水です！！！ pic.twitter.com/q1qJf43FQj

— れたす (@lettuce_cs) July 11, 2020

自分にとって水色は通過点だと思っていたのでぱぱっと水色になって上に行こうと思っていたら思いの外レートが伸び悩んでしまい、一時期非常に苦しかったのですが、無事水色になれました。マイルストーンとして今までに競プロでやったことをまとめようと思います。

ところで、先日って7月11日？もう1か月経ったらしいですよ？ぼーっとしてたらこの記事を下書きに保存したまま1か月経ったらしいです。怠惰ですね。この記事をお蔵入りさせるわけにもいかないので、1か月遅刻してしまいましたが公開します。

初めまして。最近競プロ頑張ってるれたすです。
日本語文献が一切無さそうな、Codeforcesに最近適用された新しいレーティング算出方法についてまとめようと思います。Codeforcesって色んな情報をまとめるのが不便なので大変ですよね……。

出典: Codeforces: Soon We Will Change the Rating Calculation for New Accounts

概要

新しくCodeforcesに参加するアカウントには初回$6$回のコンテストに限り表示レートにマイナス補正が掛かるようになります(AtCoderのレートに掛かるいわゆるリセマラ補正みたいなもの)。マイナス補正は回数を重ねる毎に少しずつ小さくなっていって$6$回目の参加でゼロになります。