bobuhiro11's diary

ABC139-141

20 Sep 2019

ABC #139 D - ModSum

$p_1=N, p_2=1, p_3=2, … , p_N=N-1$ とすると、$m_1=0, m_2=1, m_3=2, … , m_N=N-1$ となる。 なので、答えは$1, 2, 3, …, N-1$の総和。

ABC #139 E - League

$i$と$j$の試合を頂点$(i,j)$と表す。ただし、$i$と$j$をひっくり返したものは同一視する。 各頂点は、直前にすべき試合数$prev_{(i,j)}$と、その次に実行可能な試合の一覧$next_{(i,j)}$をもつ。 そして、$prev_{(i,j)} = 0$である試合を見つけるたびに、貪欲にその試合をしていくよう、シミュレーションする。 ここで、ある試合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントすることに注意する。

ABC #139 F - Engines

あらかじめ各ベクトルを偏角ソートしておき、 720度分になるようにそのベクトルをつなげておく(後々、楽になる)。 そうすると、この問題の答えは、連続したベクトルの和であることが分かる。 すべてのベクトルについて、以下の操作を行う。

ABC #140 D - Fce Produces Unhappiness

まず、幸福でない人に注目して、それをどれだけ減らせるかに注目する。 たとえば、$RLLLLRRRRRLLRRLLRRR$から幸福でない人を抜きだすと、$RL…….RL..RL…R$となる。 連続する人は同時に操作できるので、$RLRLRLR$と考えてよい。 そして、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> (空)のように操作を繰り返せば良い。

ABC #140 E - Second Sum

Nから1まで、順番に見ていく。 ある要素$i$について見た時、左右には$i+1, i+2, … , N$の要素が置かれていることになる。 右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、 合算すればよい。最大値の位置については、setlower_boundで見つけた。

ABC #140 F - Many Slimes

貪欲な感じで、できるだけ体力が大きなスライムから作っていけばよい。 うーん、今回はE・F問題よりもD問題が難しく感じた。。

ABC #141 D - Powerful Discount Tickets

すべてのアイテムを優先度付きキューqに入れておく。 割引券の枚数だけ順番に取り出して、以下の操作を行う。

ABC #141 E - Who Says a Pun?

長さlenについて、二分探索する。 ある長さについて、ローリングハッシュですべての部分文字列のハッシュ値を入れておき、mapなどで入れておく。 ハッシュ値が一致して、なおかつ重複がなければ、その長さでは条件を満たすことが分かる。

ABC #141 F - Xor Sum 3

各ビットごとに考える。 まず、$A_1 \oplus A_2 \oplus … \oplus A_N$ を計算しておき、 1が立っているビットについて、どのように色分けしても答えに影響しないので、 取り出しておく。取り出した結果、$A_1 \oplus A_2 \oplus … \oplus A_N = 0$の状態になる。 ここで、青色のXORを$X$、赤色のXORを$Y$とする。 $X \oplus Y = 0$なので、XORの性質から、$X = Y$となる。 なので、$A_i$から幾つか選んで、そのXORを最大化するような、選び方を見つけたい。 吐き出し法(連立1次方程式をといていくような感じ)で、上位のビットから見ていき、 1が立っている要素を pivot 行とみなして、他の要素とXORを取っていく。 結果、$X = Y = A_1 \oplus A_2 \oplus … A_N$となる。


comments powered by Disqus < ABC136-138 TCP技術入門 読書メモ >