ABC235 参加記録

コンテスト中AC:A〜E

C - The Kth Time Query

二次元配列を用意し、には、が出現したインデックスを順に記録します。

クエリが与えられた時、まず、のサイズがより小さい場合(出現数が)は、-1を出力します。
そうでなければ、を答えとすれば良いです(0-indexedであれば、となることに気をつける)。

しかし、今回が大きく、配列に収まりません。そこで、を座標圧縮します。
同様にも圧縮後の値を得ますが、がそもそもに一回も出現していないパターンがあります。
この場合は、座標圧縮後の値が見つからず、正しく動作しません。このパターンで必ず-1を出力するために、に出現した整数かどうかを記録する連想配列を用意して対処しました。
提出コード

D - Multiply and Rotate

可能な操作を整理します。整数からは以下の条件を満たす整数が作れます。

• 
• の10進表記をとすると、 (但し、の場合)

ある整数にしたいような問題では、から出発して値を小さくしていく、メモ化再帰が使われる場合があります。
しかし、今回の場合、操作によって必ず小さい数になるとは限らないので、この方法は使えません。

そこで、メモ化再帰、つまりDFS木の発想から、操作を重み1の有向辺とみなしてみます。

すると、整数を始点とし、始点から最短経路問題と同様に最小の操作回数を確定できます。
すなわち、現在作ることが可能な整数の中で操作回数が最小な整数は、その後どのように整数を作っていってもその操作回数未満にすることはできません。
以上より、ダイクストラ法でこの問題を解くことができます。

なお、2個目操作で自分より小さい整数にできるため、を超えた整数も考慮する必要があります。
桁数の増減は無いので、が桁なら桁までの全ての整数を考慮しておけば良いです。
提出コード

E - MST + 1

クラスカル法で最小全域木をつくる時のアルゴリズムは、

• 辺のコストを昇順に並べて、辺のコストが小さい順から調べていき、辺[e=(u,v)]について、が非連結ならその辺を採用する

というものです。よって、クエリの辺が採用されるか否かはの辺のうち、コストがより小さい辺のみによって決定します。そこで、

• の最小全域木を求める過程で、よりコストが小さい辺を追加した後に、辺が採用されるかを判定する

という方法ではどうでしょうか。
今回の制約上、

• [texG]の辺のコストは相異なり、かつの辺のコストと、クエリの辺のコストは全て異なる

となっています。従って、

• の辺をコストの昇順に並べたとき、並び方は一意(クラスカル法による全域木及び辺の走査順が一意)
• の辺をコストの昇順に並べたとき、クエリの辺の挿入位置は一意

が成立します。これによって、前述した判定方法で達成可能ということが言えます(多分)。
逆に、コストが同じ辺が存在する場合、同一コストの辺の走査順を変えることによって、異なる全域木(又はその部分集合)が構成されてしまい、構成されたものよって辺の採用の要否が異なる可能性が出てきます。

実際の判定方法のアルゴリズムですが、の辺とクエリの辺をごちゃ混ぜにして昇順ソートし、クラスカル法で最小全域木を構成していきます。その過程で、クエリの辺が出てきた場合は、辺の採用の要否のみを判定し、全域木には追加しないようにします。

提出コード