diverta 2019 Programming Contest

Eを解き始めたころに測ったら36.8だった。開始が15分遅れたのでドキドキしながら待つのは体力的に不利だなあとか思ってた。心拍数は上がってくれたが、ちょっと空回り気味だったか。正直昼間は頭悪かったけど、まあコンテストが始まれば大丈夫やろみたいな感じでいた。実際どうだったんだろ。残念ながらEが解けなかったので、早解き回だった。解けてる問題の細かいところを詰めるの苦手だし、一つ上の見通しを得るほどの実力はないしで、このセットを早解きできないのは仕方ない。Eは解けなかったけど、解ける可能性が十分にあると思って取り組めていたので、それはよかった(難しい問題がたまには解けているという経験に支えられている感覚)(まあ自分に解けるような難易度じゃなかったかもだけど)。unratedはどんなときでも残念だけど、微妙な気持ち。人が多いとは思っていたが。人数的には最近のABCほどではないのか?まあ上位陣が多かった(解く問題数が多い)と思うしテストケースも多そうだった。

A - Consecutive Integers

まさかnCkか?と一瞬思うが連続してるのであれだ。適当に書いて、サンプルが合ってればそれで正しいやつなはずだ。すぐ提出してなんとか1分切り。ratedコンテスト内の100点問題をどうするかが悩ましいと思っていたが、普通にいつものABCのときみたいに提出してしまった。

B - RGB Boxes

これねー、RGBとrgbの意味するものがわかりづらい。数だけが重要で、ちょうどN個にしたいのね。3000は2乗が通る。変数が3個だから、まあ行けそう。rとgを決めると、そういう組が存在すればbは一意に定まる。思ったよりきれいに書けた。

C - AB Substrings

ここからは、瞬殺できなかったら次の問題を少し見るという方針。結果的には、順番に解いていくことになった。

それぞれの文字列は短い。全体でも10^5文字以内。これはデータ構造に悩む。これは問題を解いてから入力部を書いたほうがいいだろう。組み合わせは無限大って感じだが、新たに生まれる"AB"は末尾の'A'と先頭の'B'がつながったものだけだ。また、元からある"AB"は独立にカウントできる。文字列の長さは2以上なので変なケースもなさそう(別に長さ1でも大丈夫だろって少し悩んだ)。さて、全部がBAならN-1個追加される。それが最大だが。一瞬フローが浮かぶくらい、あちらを立てればこちらがという感覚だった。これ全く見通しがなくてウンウン言ってたが、場合分けすれば普通に行けそうなのでもうそれするしかなくなった。こういうのが苦手なのは自覚している。1か所足し忘れでWAを出してしまった。そして、次の提出まで8分もかかっている。細かく場合分けしてるから、サンプルで通らないパスがどこかを確認するのも時間がたっぷりかかる。

んー、BAの塊の端に蓋をするということか。コンテスト中に見抜くのなあ。AもBも余ってしまうケースというのは、BAしかないときだけ?

D - DivRem Number

面白そうだけど全然わからん。とりあえずN=100のケースでN/mとN%mを100個出力してみる。あー、これか。できそう。O(sqrt(N))を2回やる。mがsqrt(N)以下のときは普通に試すだけでいい。次に、商がsqrt(N)未満のときを全部試す。ここがややこしかった。N/m=N%m=aとして、N=a*m+aとなっているから、条件を満たして商がaになることがあるならm=(N-a)/aである。このmをチェックすればいい。具体的な式の導出は苦手だが、必要条件とかの考え方は得意。企業コンの500は難しいと思って身構えてたらわりと行けたな?

E - XOR Partitioning

コンテスト時間の半分以上を使ったのかあ。まず思いついたのは累積xor。何が求まるのかややこしいが、ソートして同じ数をカウントすると美しさが0になる区間の数がわかる。とりあえずそれを実装。そもそも区間はO(N^2)通りしかない。美しさを固定すると、ある解の奇数個の区間を合体させても解になる。aが2未満のときを考えると、含まれる1の個数が偶数の分け方と奇数の分け方がある。これはなんかDPで解けそう。すると、2^20 + NくらいのサイズでDPできるんじゃ?しかしなかなか。計算量が落ちないし、そもそもaが小さいときのDPもわかってなかった。xorで結果を出したいね。