ganmo::cout

競技プログラミング始めました

diverta 2019 Programming Contest

久々のUnrated回でした
今回は青下位以下にとっては1-2-4-5の４問早解きセットだったみたいです

A - Consecutive Integers (100点)

問題: A - Consecutive Integers
連続する区間で選ぶので、左端を選ぶと一意に定まる。したがってN-K+1を出力してAC。O(1)。

拙解 (C++14): Submission #5342030 - diverta 2019 Programming Contest

B - RGB Boxes (200点)

問題: B - RGB Boxes
(r,g)が定まると、bをいくつにすればいいか、あるいはこの組み合わせでは不可能かが決まる。N\le 3\times 10^3なので(r,g)を全探索しても間に合ってAC。O(N^2)。
ちなみにPythonだとギリギリTLEになるとかPyPyなら大丈夫とかいう話があるみたいです（C++だと50msで余裕で間に合いました）

拙解 (C++14): Submission #5344648 - diverta 2019 Programming Contest

C - AB Substrings (400点)

問題: C - AB Substrings
まず各文字列に含まれる部分文字列 'AB' はどのようにつなげてもそのままなので確定。次に気になるのは先端の'B'と末尾の'A'；これらをうまくつなげると'AB'ができる。すなわち、先端の'B'と末尾の'A'がつながる箇所が多ければ多いほど'AB'が増える。なので、B???A、???A、B???のような文字列を探していって???A+B???A+B???A+...+B???A+B???とつなげて、残った???AとB???でペアを作ると最大になるのでこれを出力してAC。O(N+\sum |s_i|)。
雑に実装してコーナーケースに引っかかりまくってWAを5連打した…

拙解 (C++14): Submission #5357163 - diverta 2019 Programming Contest

D - DivRem Number (500点)

問題: D - DivRem Number
実験すると、Nの約数-1 がお気に入りの数の候補とわかる。これは、条件
\displaystyle \lfloor N/m\rfloor \equiv N \% m \mod m
から、
\displaystyle \begin{align*} N&=m\lfloor N/m\rfloor + N \% m \\ &\equiv m(N \% m) + N \% m &\mod m\\ &\equiv (N \% m)(m + 1) &\mod m \end{align*}
が成り立ってNがm+1の倍数でなくてはならないことからわかる。残りのN \% mから考えてもこれは必要条件なので、\sqrt{N}より大きい約数-1（つまり、Nを\sqrt{N}未満の正の整数で割って得られる整数-1）をmとして全探索して、それが\lfloor N/m \rfloor=N\% mを満たす整数であれば足していって総和を出力してAC。O(\sqrt{N})。
個人的にはC問題よりとても簡単に感じました（考察に比べて実装がめちゃくちゃ軽いので）

拙解 (C++14): Submission #5359781 - diverta 2019 Programming Contest

E - XOR Partitioning (800点)

問題: E - XOR Partitioning
（未完成：まだ考察しきれていません）
仕切った結果、偶数個の区間に分けられれば全体の総XORは0になり、奇数個に分けられれば全体の総XORは各区画の総XOR（すべて等しい）になることが考えられる。
なので、累積XORの配列を取って、0の位置に駒を置いて(0→)a→0→a→…→0(→a)というふうに駒を動かす方法が何通りあるか数えれば解ける。これは累積XOR配列の末尾（つまり全体の総XOR）が0か0でないかによって大きく解き方が変わる。これはランレングス圧縮をしたのちDPを使えば解ける。O(N)。

拙解 (C++14): まだ

F - Edge Ordering (1200点)

見てません

まとめ

4問早解きセットでDが10分かからないで解けてんのにCに1時間近くかけたのは痛すぎる
早解きはやっぱカフェインじゃなくてアルコールだ（バルマーピーク）