ユニークビジョンプログラミングコンテスト2023 クリスマス(AtCoder Beginner Contest 334)参加記

2023/12/23に開催された、ユニークビジョンプログラミングコンテスト2023 クリスマス(AtCoder Beginner Contest 334)に参加しました。

先週は、所用のためコンテスト不参加だったので、２週間ぶりの参加。年内にRatedで出られるコンテストは、これきりということで、年内再入水は絶望的ですが、来年に向けて良い成績が残せるように頑張るのみです。

２週間ぶりの参加。年内の再入水は厳しそうだが、とにかくレートを上げられるように頑張るのみです。

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334) - AtCoder https://t.co/gAMakBWFY2
— devgenjin77 (@devgenjin77) 2023年12月23日

今回の結果

ACDEの４完で終了。超久しぶりにB問題を落としてしまいました。

それでも、なんとか水パフォ確保という結果で、レートは上昇。なんとか今年最後のコンテストを勝ちで終えることができましたとさ。

B問題を落としたが、なんとか水パフォ確保で勝ち😅

devgenjin77さんのユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)での成績：1620位
パフォーマンス：1262相当
レーティング：1151→1162 (+11) :)#AtCoder #ABC334 https://t.co/qhgZYBGMfx
— devgenjin77 (@devgenjin77) 2023年12月23日

振り返り

B問題でやらかしてしまいましたが、なんとかリカバリできたという印象です。

A問題

A - Christmas Present

$B \gt G$ の場合Bat、それ以外は、Gloveを出力するだけ。

実装後、テストもそこそこに提出してAC。51秒で1完です。

提出コード

https://atcoder.jp/contests/abc334/submissions/48733223

B問題

B - Christmas Trees

見るからに、ややこしそうな問題という印象。

とりあえず、基点を $0$ にしておいたらシンプルになるかということで、 $L$ と $R$ ぞれぞれから $A$ を引いて補正してみる。

あとは、 $L$ 、 $R$ を、それぞれ $M$ で割った整数部を足した後、原点を跨ぐ場合は $1$ 足してみるという感じでOKか思い、提出してみたら、これがWA。。

どっかのコーナーケースに引っかかっているのかという感じだが、すぐには原因が分からない感じ。

IF文でゴリ押せばなんとか通りそうだが、もう時間が30分経過していることと、順位表を見てると通常B問題よりは躓いている人が多い印象ということから、これ以上B問題にとりかかるのはリスクが高いのではという判断で、一旦スキップすることにしました。

C問題

C - Socks 2

これもC問題にしては、やたら難しそうな問題という印象だが、B問題をスキップしている手前、なんとか解かないといけない。

以下考察。

残っている靴下で計算した「奇妙さ」の総和と、なくした靴下で計算した「奇妙さ」の総和は、おそらく一緒になるので、なくした靴下で「奇妙さ」を計算すればよい。
$K$ が偶数の場合、なくした靴下の色でソートしてから、隣接するペアで「奇妙さ」を計算していくのが最善かと。
$K$ が奇数の場合どうするか。 $K=1$ の場合は、「奇妙さ」を $0$ にできるが、そうでない場合、どの靴下を捨てるかを全探索しないといけない感じ。
結局、靴下の色でソートしてから、先頭から隣接するペアを見た時の「奇妙さ」の累積和、および、末尾から隣接するペアを見た時の「奇妙さ」の累積和を前計算し、作成するペアの数を $\lfloor \frac{K}{2} \rfloor$ で固定した時に、「奇妙さ」の合計が最小になる組を選べばOKかと。