bobuhiro11's diary

ABC EF問題を埋めた

16 Jun 2019

Atcoder Beginner Contest #116 ~ #129のCD問題をすべて解いた。 また、#126 ~ #129についてはEF問題が追加されているので、すべて解いた。 F問題は、解説PDF、解説Youtube、解説ブログを参考にした。

ABC #126 F - XOR Matching

https://atcoder.jp/contests/abc126/submissions/5909511

M=3とすると、長さ2^(M+1)の数列は、{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}のような要素をもつ。 このとき、{<0,1,...,7からKを除いた昇順の数列> K <7,6,...,0>からKを除いた降順の数列 K}とすれば良い。

ABC #127 F - Absolute Minima

https://atcoder.jp/contests/abc127/submissions/5930963

中央値が最小値となる性質を利用する。中央値が2つあるときには、左側を採用する。 中央値は、小さいほうと大きいほうをそれぞれ優先度付きキューで管理すると便利。 解説動画では、同一のaを二度入れてキュー間で交換するテクニックを使っていたが、 ナイーブに一度だけ入れる方法でも問題ない。 キューが片方に偏らないように、整理する必要がある。 更新クエリのとき、aが最小値を取る区間のなかに含まれていれば、最小値の更新はない。 一方、含まれていなければ、最小値を取る区間のなかで、最も近い点との差分を、最小値に追加する。

ABC #128 F - Frog Jump

https://atcoder.jp/contests/abc128/submissions/5921198

A、Bをそのまま扱うのではなく、C=A-Bk=何度戻りが発生するか という変数に置き換えて考える。 Cを固定すると、kが増えるにつれて、蓮を多く踏めるようになる。 同一の蓮を二度以上通るかどうかは、単純にsetで管理した。

ABC #129 F - Takahashi’s Basics in Education and Learning

https://atcoder.jp/contests/abc129/submissions/5945816

難しかった。まず、等差数列の各要素が何桁なのかによって、分割する。たとえば、A=3、B=4であれば、3,711,15,19に分けて考える。分割後は、sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1)を求めることになる。 A sum_i=0^(l-1) 10^k^iB sum_i=0^(l-1) i*10^k^(l-i-1)にわけて、計算する。 どちらも漸化式に変換して解く(コード中のf,gに対応)。 解説動画を見るのがおすすめ。

Atcoder ProblemsのUser Page


comments powered by Disqus < Go言語による並行処理 読書メモ ABC EF問題を埋めた(続き) >