【AtCoder】ACL Beginner Contest 178 (A~D) 参戦記

ALC (AtCoder library contest) Begginer Contestに出場した

AtCoderが用意したC++のライブラリを使って問題を解こうというものだけど、筆者はC系の言語は二度と使いたくないので自作のPythonのライブラリ(スニペットだけど)で挑んだ

結果

順位:4249人中1050位

得点:1000点 (3)

ペナルティ付き最終解答時間:107:38

パフォーマンス:1245

※()内の数字はWAの回数

各問題の結果
得点 WA回数 解答時点での経過時間
A 100点 0 0:56
B 200点 0 2:37
C 300点 0 6:34
D 400点 3 92:38
E 500点 - -
F 600点 - -

レート変化

919→960 (+41)

Highest更新!

もうすぐ1000だ

f:id:monhime:20200927074741j:plain:w400

f:id:monhime:20200927074340j:plain:w400

解答

A Repeat ACL

A - Repeat ACL

問題要約

整数$ K $が与えられる。文字列"ACL"を$ K $回繰り返してつなげることで得られる文字列を出力せよ。

解答

Shortest狙ってる訳でもないので普通に書いた

コードを見る(クリックして下さい)

ALCBC A問題 解答

 

Submission #17021415 - ACL Beginner Contest

B Integer Preference

問題要約

$ A $以上$ B $以下の整数と$ C $以上$ D $以下の整数で共通する整数はあるか

解答

Bにしては少しもひねりがない

ライブラリコンテストだからかな

コードを見る(クリックして下さい)

ALCBC B問題解答

 

Submission #17023750 - ACL Beginner Contest

C Connect Cities

C - Connect Cities

問題要約

$ N $個の都市と$ M $本の双方向道路があり、道路$ i $は都市$ A_i $と$ B_i $を結ぶ。道路を辿って全ての都市の間を行き来できるようにするには、最低何本の道路を作る必要があるか。

解法

道路を辿って行き来できる都市をグループにして扱う

例えば2つのグループがあったとき、その間に1本だけ道路を加えれば、それぞれのグループに属する都市は全て道路を辿って行き来できる

すると、2つのグループは1つのグループとして扱える

これをグループの個数が1になるまで続けると、結局、求めるのは(最初の状態で道路を辿って行き来できるグループの個数)-1になる

道路を辿って行き来できる都市のグループの個数は、Union-Findで道$ i $に対し$ A_i $と$ B_i $をuniteし、最後にグループの個数を求めればよい


Cになって急に難易度(必要な知識)が上がった

とはいえ気づけばすぐなので、ライブラリ知ってる前提のライブラリコンテストなら妥当かな

解答

Union-Findのコードは下記サイトを参考にした

PythonでのUnion-Find(素集合データ構造)の実装と使い方 | note.nkmk.me

コードを見る(クリックして下さい)

ALCBC_C.gyp

 

Submission #17027498 - ACL Beginner Contest

D Flat Subsequence

D - Flat Subsequence

問題要約

$ N $個の要素の整数の数列$ A $と整数$ K $が与えられる。以下の条件を満たす数列$ B $の長さとして考えられる最大値を求めよ

・$ B $は$ A $の(連続とは限らない)部分列である。

・どのBの隣り合う要素の差の絶対値も$ K $以下である。

制約

$ 1 \leq N \leq 300000 $

$ 0 \leq A_i \leq 300000 $

$ 0 \leq K \leq 300000 $

解法

数列$ A $の$ i $番目までの各要素について、その要素の値が$ B $の最後尾であったときの$ B $の最大長さが分かっているとする(dp[i]=($ B $の最後尾が$ i \,(0\leq i \leq \max\{A\})$のときの$ B $の最大長さ)とする)

$ A_{i+1} $を$ B $に追加するときに$ B $が最大長さになるためには、「$ B $の最後尾が$A_{i+1}-K $以上$ A_{i+1} + K $以下である場合のうち、$ B $の最大長さが最大のもの」に$ A_{i+1} $を追加すれば良い

これを漸化式で表すと、$ \displaystyle dp[i+1]=\max_{i_s \leq i \leq i_t}\{dp[i]\}+1 $

ただし、$ i_s = \max\{A_{i+1}-K,\,0\},\,i_t = \min\{A_{i+1}+K,\,\max\{A\}\} $

これをこのままプログラムにすると、数列$ A $の各要素についてdpテーブルの最大$ 2K $の範囲から最大値を取り出すため、時間計算量はO(NK) となる

$ N,\,K$の制約の最大値より計算量のオーダは最悪$ 10^{10} $ になるため、これではTLEになる

そこで、区間最大値を高速に求めるセグ木を使う

セグ木ならある数列の区間最大値がO(log K)で求まるので、全体の時間計算量はO(Nlog K)でなんとか間に合いそう(C系言語なら余裕だけど)


セグ木については競プロかつっぱさんの動画が分かりやすいので参考に

解答

はじめ何も考えずPythonで提出してTLE

セグ木にしたところで制約が $ 3\times 10^5 $なので各$ i $での処理が多いとPythonじゃだめらしい

PyPyにしてTLEは消えたけどWAが残った

原因は数列の要素が全て正の整数と勘違いしていたことだった

終了直前でなんとかAC

もったいない


セグ木のコードは下の記事を参考にした

最大・最小セグ木 コピペ用 Python - じゅっぴーダイアリー

セグ木のクラスでは区間の決め方は左閉半開区間なので区間の右側の指定で+1している

コードを見る(クリックして下さい)

ALCDC D問題 解答

 

Submission #17045619 - ACL Beginner Contest

感想

ライブラリコンテスト?は初めて参加するけど、意外と自分の既に持っているライブラリで戦えた

今回も水パフォとれた

AtCoder Rating Simulatorによると、このままパフォーマンス1400を維持すればあと6回で水色になる

今の感覚的に水パフォ程度なら安定して取れそう

f:id:monhime:20200927074359j:plain


先々週まではとにかくABCの過去問を解き進めていたけど、この辺りからはdiff順に過去問解くだけでは伸びにくいと感じてきた

テーマを絞って、その関連問題を集中して特訓するのが効率が良さそう

そのために、ABC系のRatedコンテストは全て出て、出題された問題をF問題まで全て復習しよう

今回のEはTwitterを見ると遅延セグ木を使う問題らしいので、今週は遅延セグ木の特訓でもしようかな