Lukeの競プロ日記

主にAtCoderの問題の解説を書いています

ABC276後記 (A~F)

A - Rightmost

問題概要

与えられる文字列 $S$ で一番最後のaは何番目か

解法

まずは答えansを初期値-1として持っておき、 $S$ を先頭から見ていく。
aが登場するたびにansを更新していけば良い。

提出

B - Adjacency List

問題概要

$N$ 頂点 $M$ 辺の無向グラフが与えられる。
それぞれの頂点について、その頂点と直接つながっている頂点を昇順に出力せよ

解法

グラフの基礎的な問題。グラフを隣接リスト表現(≠隣接行列表現)で表してあげる。

提出

C - Previous Permutation

問題概要

順列 $P$ の辞書順で一つ前の順列を出力せよ

解法

C++だとSTLで一発。std::prev_permutation()を使う。
僕の解法はそれぞれを $N$ から引いて、std::next_permutation()を使っている

提出

D - Divide by 2 or 3

問題概要

与えられた数列 $a_1, a_2, a_3, ..., a_N$ に対して、

2の倍数であるような数 $a_i(1\leq i \leq N)$ を2で割る
3の倍数であるような数 $a_i(1\leq i \leq N)$ を3で割る

を任意の回数行なって全ての数を同じにする時、最低で何回必要か(不可能なら-1)

解法

全て同じにできる場合、その数は数列の最大公約数となる(すべてがその数を因数として持つから)。したがってまずは数列を最大公約数で割ってあげる。
次にそれぞれが2,3でそれぞれ何回割れるかを考える。これはwhile文を回してあげればいい。もし2と3で割れるだけ割った後、1になっていなければ、数列をすべて同じ値にすることは不可能。

提出

E - Round Trip

問題概要

スタート地点、道、障害物からなる $H \times W$ のグリッドが与えられる。この時、スタートから出発してスタートへ戻ってくる道順であって、同じ道を2回以上通らないものは存在するか

解法

DFSを行う。
スタート地点から初めて、来た道を戻る以外の方法(深さの差が2以上)でスタート地点へ戻ることができた場合、それまで探索した経路が目的の経路となる

提出

F - Double Chance

問題概要

$N$ 枚のカードがあり、 $i$ 番目のカードには $A_i$ と書かれている。このとき、

$K(1 \leq K \leq N)$ 枚目までのカードから、一枚カードを引いて元に戻す操作を2回行うときの、その2枚のうち大きい方の数値の期待値

を全ての $K$ について求めよ

解法

カードを引く順番まで区別すると、ありうる引き方は全て等確率で起こる。したがって、とりうる最大値の総和を求め、最後に $K^{2}$ で割ってあげれば良い。ここで、 $K=i$ の時にとりうる最大値の総和 $S_i$ は、

$S_i = S_{i-1} + i$ 番目のカードを使う時に取りうる最大値の総和

となる。そして、 $i$ 番目のカードを使う時に取りうる最大値は、

他方のカードの数字 $a_j$ が $A_i$ 以下の場合、 $A_i$
他方のカードの数字 $a_j$ が $A_i$ より大きい場合、 $A_j$
同じカードを引いた場合、 $A_i$

となって、それぞれの場合の総和が求まれば良い。 1、2の場合は、BITやセグ木を使ってあげることで、

1の場合： $A_i$ 以下のカードの枚数 $\times A_i$
2の場合： $A_i$ より大きいカードの総和

を高速に求めることができる。また、1,2の場合は $i$ 番目のカードを先に引くか後に引くかの2通りあるため、2倍する。

提出