Lukeの競プロ日記

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

ABC256後記(A~E)

A - 2N

問題概要

2Nを答えてください

解法

2Nを出力すればいい。これはpow(2,n)や(1<<n)でできる

提出 atcoder.jp

B - Batters

問題概要

長さNの数列Aがあって、以下の操作をN回繰り返すとき、4マス以上進む駒の数を答えてください

  1. マス0にコマを置く
  2. すべての駒を A_{i}だけ進める

解法

N個の駒は、

  • 1個目: A_{1}+A_{2}+A_{3}+...+A_{N}
  • 2個目: A_{2}+A_{3}+A_{4}+...+A_{N}
  • 3個目: A_{3}+A_{4}+A_{5}+...+A_{N}
    ...

のように動く。このとき、i番目の駒は必ずi+1番目の駒より前にいるから、「4マス以上進むものの中で一番後ろのもの」が分かれば良さそう(その駒よりも先に置かれた駒はすべて4マス以上進む)。

では、どうやってそれを見つけるか。
これは単純に、一番最後の状態を考えて、4以上になるまで A_Nから逆順に足していけばいい。

提出 atcoder.jp

C - Filling 3x3 array

問題概要

縦横それぞれの合計が与えられるので、それを満たす3x3のグリッドの個数を求めてください。

解法

一見、すべてのマスを全探索しないといけなさそうに見える。
ところが、縦、横それぞれについて、2 つわかってしまえば残りの一つはわかる(合計から引けばいい)ので、4つだけを全探索すればいいことになる。 あとは、出る値について、

  • 入力の条件を満たす
  • 最小値が1以上

ことを判定すればいい。
実装は重めだけど頑張る

提出 atcoder.jp

D - Union of Interval

問題概要

与えられる区間の和をとってください

解法

ここで、問題をちょっと読み替えてみると、こうなる。

N個の半開区間 [l_i, r_i]に対してブロックを一つずつ置く。このとき、最終的にブロックが1個以上置かれる区間を列挙してください

これができれば、あとはimos法で各場所のブロック数を求めてあげて、ブロック数が1以上の区間を列挙すればいいということがすぐにわかる。

imos法:区間[l,r)に対して、imos[l]に1加算、imos[r]に1減算して、最後に全体で累積和をとる手法

提出

atcoder.jp

E - Takahashi's Anguish

問題概要

i君は A_i君が嫌いで、i君よりも先に A_i君にキャンディが渡されると C_iだけ不満になる。
このとき、不満の合計の最小値はいくらか。

解法

一見複雑そうだが、人間関係は結局(有向)グラフなので、グラフにしてみる。こんな感じで有効辺を張ってみる

AはBが嫌い=AからBにコストCの辺

こうみると、グラフになるべく沿って進めば良さそう。
とすると、考えるのは「0本以上の辺を消してトポロジカルソート可能にする時、削除する辺のコストの合計の最小値」となる(削除した辺=逆走してコストCを受け取る辺)。
つまり、そうしてできたできたトポロジ列の順に辿ってキャンディをあげればいい。

ではどの辺を消せばいいかというと、そもそもトポロジカルソート可能にするということは、ループを無くすことなので、強連結成分ごとに(ループごとに)分けて、その中で一番コストが低い1辺だけを切ってあげればいい。
ここで切った辺のコストの総計が答え

トポロジカルソート:有向グラフで、辺の向きがすべて同じになるように直線状に並び替える方法。ループがあるとできない
強連結成分分解の実装: ここを参照

提出

atcoder.jp