週記(23/04/23)：ABC300!

今週のまとめ

• ABC299バチャ
• ABC293バチャ、出てたらちょっと暖まる
• ABC300、青に復帰！

です。

(本文中にABC 293 C-F, 299 C-E, 300 D-Fの解法を含む話題が出てくるのでご注意ください。)

4/24(Mon)

ABC299のバーチャル参加

69分(2ペナ)5完で865位相当でした。2ペナがともにケアミスでもったいない…。

「C – Dango」は団子にならないケース(-のみ or oのみ)を先に処理して後は連続するoの最長の長さを出せば良いです…が、最後がoで終わるケースを漏らしてて1WA。

「E – Nearest Black Vertex」は考察は比較的すんなり。[math]p_i[/math]ごとにBFSで見て

• 距離[math]d[/math]未満は黒を置けない領域
• 距離[math]d[/math]はそのどこかで[math]p_i[/math]に対応する黒を置けばよい領域

を出して、これがすべて成立するような置き方があればよいかをチェックすればOK。

ただ、制約の「1 個以上の頂点が黒で塗られている」を忘れていて1WA。サンプルにも入っていたのに「白でもええか」と思ってしまいました…。

残り時間＆終わってからしばらく「G – Minimum Permutation」を考えてましたがサンプルすら合わず…。

4/25(Tue)

会社の行き帰りで「G – Minimum Permutation」を考えましたが、詰めが甘くてまだ合わない…。

4/27(Thr)

ABC293のバーチャル参加

55分5完でパフォーマンス1606相当。ようやく調子が戻って青パフォ前後を出せるようになってきました。

「C – Make Takahashi Happy」は出現した数字を持ちながらDFSすればOK。ただ、端の判定でバグってしまってサンプル合わずかなり時間を使ってしまいました。

「D – Tying Rope」はロープの端をノードと思ってUnion Findで連結成分を管理して閉路をカウントすればOK。これも初期状態でロープ分をUnionするのを忘れてしまって少し時間を使いました。

「E – Geometric Progression」は最初、等比級数の和で考えるも必ずしも[math]A-1[/math]と[math]M[/math]が互いに素にはならないので難しそう。

考え直して[math]S_n = \sum_{i=0}^{n-1} A^i[/math]とおくと[math]S_{n+1} = A S_n + 1[/math]なので

[math]
\begin{bmatrix} S_{n+1} \\ 1 \end{bmatrix} = \begin{bmatrix} A &1 \\ 0 &1 \end{bmatrix}\begin{bmatrix} S_{n} \\ 1 \end{bmatrix}
[/math]

と書けて行列累乗で出せる！行列累乗を本番、バチャで通せたのは初めて！

「F – Zero or One」は計算量の見積もりが甘くてTLEを出したところで終了。

4/28(Fri)

ABC299「G – Minimum Permutation」, ABC293「F – Zero or One」「G – Triple Index」を行ったり来たり。

「F – Zero or One」は手元の環境だと最大ケースでも間に合うのに提出するとTLEで悩ましい。結局、解説を見ましたが、これを自力で思いつけそうな感じがしません…。

Twitterで検索するtomerunさんのツイート(画像は一部抜粋)の

が自然なアプローチだと思いました。

2つの解法をうまく使い分ける方針で1つ目は[math]N[/math]を[math]b[/math]進数表記して0-1かを確認します。これは1回あたり[math]O(\log_b N)[/math]かかるので[math]T\leq 10^3[/math]を考えると[math]10^4[/math]くらいは回せます。

もう1つは[math]b[/math]が大きくなると[math]b[/math]進数表記の長さが短くなるので0-1表記のパターンを列挙してそのパターンで[math]N[/math]で表現可能かをチェックします。パターンを決め打つと[math]b[/math]進数から10進数に戻した値は[math]b[/math]について単調増加なので[math]N[/math]以下になる最大の[math]b[/math]を二分探索して[math]N[/math]に一致するかで判定できますね。

使い分ける基準としては[math]b<10^3[/math]なら前者、[math]b\geq 10^3[/math]なら後者とすると計算量的に間に合います。賢いやり方ですねー。

4/29(Sat)

ABC300の参加

記念すべき300回目のABC。

2週連続でunratedでどうなることか…と思いつつスタート。問題を開こうにも開けない…またDDoSかと思ったら参加登録を忘れていただけでした…アホ過ぎる。

登録忘れで時間ロスしましたが48分5完のパフォーマンス1763で青に復帰できました！

DDoS攻撃は今回もあったみたいですがその影響を感じることなく参加できました^[1]1週間もないなかでの対策、運営には頭が下がります。ありがとうございます。。

「B – Same Map in the RPG World」はサンプル4がすごくて

ABCっぽいアスキーアートを

下に1列シフトして

左に14列シフトさせると…

300!になるという趣向なんですね！よくこんなの作りましたね(笑)

「D – AABCC」も[math]300 = 2^2\times 3 \times 5^2[/math]にちなんだ問題ですね。[math]a < b < c < 10^6[/math]なので[math]10^6[/math]以下の素数を列挙して[math]a,b[/math]を全探索しつつ[math]b < c < \sqrt{\dfrac{N}{ab}}[/math]となる[math]c[/math]の個数をカウントしました。

「F – More Holidays」は最長の連続部分列は先頭のSから始まるとしてよくその開始位置を全探索。×を貪欲にoに変えてoをカウントで良いはずがバグらせまくった挙句、1WAが取れず…

Fは惜しかったですが青にも戻れて気持ちよくGWを過ごせそうです。

関連記事

• 前週の週記: 「Euler Tour」
• 翌週の週記: 「ゴールデンウイーク」