人工知能と競プロやってくブログ

深層学習・機械学習・AI・atcoder・競技プログラミングについて調べてやってみたことをまとめるブログです

AtCoder Beginner Contest 214 [ C - Distribution ]をPythonで解く(300点、⬜️灰色diff)

問題

atcoder.jp

問題概要

N人が円周上に並んでいる.
i番目の人は時刻tに宝石をもらうとSi時間後にその宝石を(i+1)番目の人に渡す.
ただし,(N+1)=1とする.
また,高橋君は時刻Tiにi番目の人に宝石を渡す.
すべてのiについて,i番目の人が初めて宝石をもらう時刻を求めよ.

1≤N≤2×105
1≤Si, Ti≤109
(問題概要かんプリンさんサイトより引用)

解法

1 <= iのi番目すぬけ君について考える。
宝石を渡されるパターンは2つ考えられる。

  • 隣のすぬけ君から宝石を渡される。
  • 自分担当の高橋くんから宝石を渡される。

なので、このどちらかの小さい方が答え。

しかし円周上に、すぬけ君が並んでいるのがポイントで、1周だけループさせただけでは答えが出ない。
最低2周させる必要がある。

2周対応にするために、配列の添字はNで割った余りに。

実装

参考

atcoder.jp

少なくとも 2N 回ループを回さないといけないことに注意してください。

AtCoder Beginner Contest 217 [ E - Sorting Queries ]をPythonで解く(500点、🟩緑diff)

問題

atcoder.jp

解法

問題を読んだ段階で、ソートを行うクエリをどう扱うか(普通にソートすると計算量くってTLEっぽい)がポイントと思われる。

そこで、次のように処理する。

キュー Q1と最小値を優先的に取り出す優先度付きキューQ2を用意して、クエリを以下のように処理します。

  • クエリ1 : Q1に x を push する。
  • クエリ2 : Q2が空かどうかによって 2 つの操作のいずれかを行う。
    • Q2が空の場合、 Q1の先頭の要素を出力して pop する。
    • Q2が空でない場合、 Q2の最小の要素を出力して pop する。
  • クエリ3 : Q1内の要素をすべてQ2に移す。

実装

参考

atcoder.jp

AtCoder Beginner Contest 217 [ D - Cutting Woods ]をPythonで解く(400点、🟩緑diff)

問題

atcoder.jp

問題概要

長さLの木材がある.以下のQ個のクエリを処理せよ.
i番目のクエリは(ci,xi)で与えられる.

  • ci=1のとき:木材の左端からxiの地点で木材を切る.
  • ci=2のとき:木材の左端からxiの地点を含む木材の長さを出力する.

1≤L≤109
1≤Q≤2×105
ci=1,2
1≤xi≤L−1
(問題概要かんプリンさんサイトより引用)

解法

木の右端と左端の配列を作成(0, L)。
これに二分探索で要素を追加、二分探索で要素を検索を行う。

二分探索はpythonでお馴染みの、bisectを使うのだが、検索対象をlistではなくarrayにしているところがポイント。
listにした場合、PyPy7.3.0でTLEが1個出てしまって通らない。

これはlistへの要素追加が処理が重く、足を引っ張っている。
検索したところarrayへの要素追加は、listと比較して1/3の計算量で済むので、データ管理をarrayに変更することでACできた。

実装

参考

x1.inkenkun.com arrayにしたほうがlistより要素追加が軽いことが書いてある。

kanpurin.hatenablog.com

問題概要を引用させてもらいました。
ありがとうございます。

AtCoder Beginner Contest 163 [ D - Sum of Large Numbers ]をPythonで解く(400点、🟫茶diff)

問題

atcoder.jp

解説

生成できる最小値と最大値を計算すれば、間の組み合わせ数は、おのずと割り出せる。

実装

参考

youtu.be

Educational DP Contest / DP まとめコンテスト [ K - Stones ]をPythonで解く

問題

atcoder.jp

解法

区間DPで解く。
区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。
𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、最適な状況下での何かしらの値

dp[0][0]から、幅0でdp[0][0], dp[1][1], dp[2][2] ....と計算していく。
先攻後攻を考慮して
先攻ではX-Yが最大になるように
後攻ではX-Yが最小になるように
数字を入れていく。

最終的にdp[0][N-1]が計算され、答えが出る。

実装

参考

atcoder.jp

algo-logic.info

AtCoder Beginner Contest 213 [ D - Takahashi Tour ]をPythonで解く(400点、🟫茶diff)

問題

atcoder.jp

解法

コンテスト参加中
「DFS(深さ優先検索)だろ!こりゃACもらった!」
と思ったら、TLEで解けなくてガッカリだったー。
ので復習。

この問題、DFSで木を上方向に戻る処理まで再帰関数で実装してしまったんだが、1に戻って終わるのが前提の問題。
なので、戻るに決まってるので、木構造の一番深いところまで行くところまで計算したら、あとの戻りは自明で決まる。

ゆえに下に行った直後に、元の都市への戻りを追加してしまえば、一番深いところまでの片道の計算で済む。

実装

実行結果

PyPy3(7.3.0) AC 1169ms
Python(3.8.2) AC 1151ms

再帰関数よびまくりだが、PyPyでもPythonでも、そこまで実行速度に差がないね。