ABC465 参加記

私です。

ABC465 に参加しました。早め4完で入緑しました。入緑記事はまた書こうと思います。

何気に初水色パフォーマンスだったりします。これを安定できるようにしたいですね。

A問題 Supermajority

ABC463 - A と同じですね。

浮動小数点数を使う必要はありません。$A > B \times \frac{2}{3}$ の両辺を3倍して、A * 3 > B * 2 を判定すればOKです。

B問題 Parking 2

ある偉い人は言いました。『$\mathcal{O}(1)$ で賢く解くよりも、$\mathcal{O}(N)$ で確実に解いたほうが良い』と。

各時刻 $i \; (A \le i < B)$ について、$i$ 時から $i+1$ 時までの料金を考えます。

• $L \le i < R$ なら $X$ を加算する
• そうでないなら $Y$ を加算する

この問題では時刻が $23$ 以下なので、1時間ずつ料金を加算するシミュレーションで十分です。

C問題 Reverse Permutation

こういうアルゴリズムでもデータ構造でもない問題が一番面白いですよね。そうです、サンプルエスパーしましょう。

$k$ の操作を行う直前、$k$ は操作対象の末尾にあります。そのため、操作後の $k$ は次の位置に移動します。

• $S_k$ が o なら、先頭へ移動する
• $S_k$ が x なら、末尾に残る

そこで、操作を $k=N,N-1,\ldots,1$ の順に読み、答えを外側から埋めていきます。未確定部分の左右端と、向きが反転しているかを持っておけば、$k$ をどちらの端へ置くかが決まります。

• 反転していなければ、o なら左端、x なら右端へ置く
• 反転していれば、置く側を左右逆にする
• o の場合は、置いた後に向きも反転させる

長さ $N$ の配列を先に用意し、左右の書き込み位置を管理しながら埋めれば、Dequeを使わずに $\mathcal{O}(N)$ で実装できます。

D問題 X to Y

似ているかは置いておいて、類題として Codeforces 1103 (Div.3) - C: Omsk Programmers を上げておきます。

この問題の操作は、次の2種類に分けて考えられます。

• 操作1: $x$ を $\left\lfloor \frac{x}{K} \right\rfloor$ に更新する
• 操作2: $x$ を $[x \times K, (x+1) \times K)$ の区間内の整数に更新する

操作1の更新先は一意に決まりますが、操作2には複数の更新先があります。そのため、操作2でどの値を選ぶかを $X$ 側から考えるのは大変です。

ここで、$X$ に操作2を行う代わりに、$Y$ に操作1を行うことを考えます。$X$ から見れば操作2の行き先は複数ありますが、行き先の $Y$ から逆にたどれば $\left\lfloor \frac{Y}{K} \right\rfloor$ の1通りに決まります。

したがって、$X \ne Y$ の間は $X,Y$ の大きい方を $K$ で割ればよいです。

$X = 7, \; Y = 43, \; K = 6$ で考えると $Y$ の方が大きいので、

とすれば、1回で $X=Y$ になります。あとは $X=Y$ になるまで、大きい方を $K$ で割り、その回数を数えれば答えです。

私は最初、切り捨てを表現しようとして浮動小数点数を使い、WAを出しました。しかし、$X,Y,K$ は最大 $10^{18}$ なので、浮動小数点数では正確に保持できません。整数除算を使えば、そのまま切り捨てられます。

E問題 Digit Circus

解けませんでした。

世界のナベアツだなぁと思いつつ、巨大数の問題を解いたことがないので良くわかりません。

コンテスト後にTwitterとかを見ていると、桁DP というものを使うらしいです。これを機に勉強しようかなと思います。

最後に

ついに緑です。

満足せずに頑張ろうと思います。

Twil3akineでした。

あ、みなさんもヒューリスティックしましょうね。