AtCoder Beginner Contest 217をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 217を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 217 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Lexicographic Order

Pythonにおいて辞書順は, 通常の大小関係<と>で表されます.

B - AtCoder Quiz

方法はさまざまあるかと思いますが, 以下では「コンテスト一覧となる集合から差し引いた残りを出力する」という方法で記述しています.

C - Inverse of Permutation

例えば, $[p[i], i]$を$i = 1, 2, \ldots, N$まで並べたリストを用意して昇順にソートすると, 各要素の2番目の要素を取り出したものは順列$Q$に相当します(図1参照).

時間計算量は$O(N \log N)$に(たぶん)なりますが, これでもACすることができます.

あるいは, $q[p[i]] = i$であることに気づいてしまえば, より高速に処理することが可能です(「$Q$の$p[i]$番目の要素が$i$である」そのままです). 時間計算量は$O(N)$に(たぶん)なります.

D - Cutting Woods

UnionFindを利用した解法は, おそらく以下のようになるかと思います. UnionFindは, 「AtCoder Beginner Contest 214をPythonで解く」でも取り扱っています.

AtCoder Beginner Contest 214をPythonで解く

こんにちは, Shinoryoです. 今回は AtCoder Beginner Contest 214 を, Pythonで解いてみた結果を書き連ねていこうと思います. AtCoder Beginner Contest 214 - AtCoder AtCoder is...

1. クエリが全部なされた後でも切断されていない部分を切断するような, 新たなクエリを加える. これにより, 全てのクエリが実行された後には全ての部分が切断されている状態になる.
2. $L$で初期化されたUnionFindを用意する.
3. クエリを逆に実行していく. $c = 1$なら切断の逆の結合を行い, $c = 2$なら出力するべき値を何らかのリスト等に格納しておく.
4. 出力するべき値が格納されたリストから, 定められた順番で出力を行う.

Pythonでは, これだとTLEになってしまいます.

そこで, 発想を変えてみます. 「切断位置リスト」として, 今までに切断された位置が格納されたリストを用意します. 便宜上, $0$と$L$も初期値として格納しておきます. あるクエリ$c = 2, x = x_1$が与えられたときに,

• 「切断位置リスト」に含まれる要素のうち$x_1$より大きい要素のうち最小の要素($= x_2$)
• 「切断位置リスト」に含まれる要素のうち$x_1$より小さい要素のうち最大の要素($= x_3$)

を高速に取得できれば, 出力すべき値は$x_2 - x_3$となります.

そのような$x_2$, $x_3$を高速に取得できる方法の1つに, bisectモジュールがあります. リストの順序関係(基本的には, 数値の大小関係)を保ったまま, リストへの挿入を行うことができます. 挿入だけでなく, 「挿入可能な位置」を調査することができ, これによって$c = 2$のクエリに関する操作を行うことができます.

これだけでも残念ながらPythonだとTLEになってしまうのですが, arrayモジュールを利用することによって, 挿入をやや高速に行うことができて^*1 ACすることができます.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 217」
  Editorial - AtCoder Beginner Contest 217

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• nkmk様による「Pythonで文字列を比較（完全一致, 部分一致, 大小関係など）」
  Pythonで文字列を比較（完全一致, 部分一致, 大小関係など） | note.nkmk.me

  Pythonで文字列同士を比較して判定する方法について説明する. 完全一致（等価）: ==, != 部分一致: in, not in 前方一致・後方一致（先頭・末尾）: startswith(), endswith() 文字列の大小関係（順番）: <, <=, >, >= 大文字小文字を区別せずに比較 正規表現パターンにマッチ: re.search(), re.fullmatch() 文字列を検索し...

• bisect — Array bisection algorithm — Python 3.9.7 documentation
  bisect — Array bisection algorithm — Python 3.9.7 documentation

• ta7uw様による「Python標準ライブラリ：順序維持のbisect」
  Python標準ライブラリ：順序維持のbisect - Qiita

  はじめに ソートされたリストに対してソート順序を保ったまま値を挿入したいと思う場面は少なくないはずです. そういった場面に 出くわしたときにappendしてsortしているとパフォーマンスはよくないです. Pythonのlistのソ...

• array — Efficient arrays of numeric values — Python 3.9.7 documentation
  array — Efficient arrays of numeric values — Python 3.9.7 documentation

脚注

*1 : 気になったので, リストに対してinsertをしたときの処理時間を計測してみました.

通常のリストの場合：3.3825604915618896秒
arrayモジュールの場合：0.6667544841766357秒

こうしてみると, (少なくとも$N$が十分に大きい場合には)確かにarrayモジュールの方がinsertに関しては高速に処理が出来そうですね.