AtCoder Beginner Contest 214 [ C - Distribution ]をPythonで解く(300点、⬜️灰色diff)
問題
問題概要
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で割った余りに。
実装
参考
少なくとも 2N 回ループを回さないといけないことに注意してください。
AtCoder Beginner Contest 217 [ E - Sorting Queries ]をPythonで解く(500点、🟩緑diff)
問題
解法
問題を読んだ段階で、ソートを行うクエリをどう扱うか(普通にソートすると計算量くってTLEっぽい)がポイントと思われる。
そこで、次のように処理する。
キュー Q1と最小値を優先的に取り出す優先度付きキューQ2を用意して、クエリを以下のように処理します。
- クエリ1 : Q1に x を push する。
- クエリ2 : Q2が空かどうかによって 2 つの操作のいずれかを行う。
- Q2が空の場合、 Q1の先頭の要素を出力して pop する。
- Q2が空でない場合、 Q2の最小の要素を出力して pop する。
- クエリ3 : Q1内の要素をすべてQ2に移す。
実装
参考
AtCoder Beginner Contest 217 [ D - Cutting Woods ]をPythonで解く(400点、🟩緑diff)
問題
問題概要
長さ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より要素追加が軽いことが書いてある。
問題概要を引用させてもらいました。
ありがとうございます。
AtCoder Beginner Contest 213 [ D - Takahashi Tour ]をPythonで解く(400点、🟫茶diff)
Pythonでlistの内容を横一列に表示する
AtCoderの問題の答え表示で、横一列表示が出て、
「あれ?どうすんの?」
と思い、調べたのでメモ
>>> A = [1, 2, 3, 4, 5] >>> print(*A) 1 2 3 4 5