torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Beginner Contest 172, D : Sum of Divisors

問題概要

 正整数 $X$ について,関数 $f$ を

  • $f( X ) = $ $X$ の約数の個数

とする.
 正整数 $N$ が与えられるので,$$\sum_{ K = 1 }^{ N } K \times f( K )$$ を求めよ

制約

 $1 \leq N \leq 10^7$

続きを読む

AtCoder Beginner Contest 172, C : Tsundoku

問題概要

 本のスタックが 2 つあって,片方には $N$ 冊の本が,他方には $M $ 冊の本が積まれている.$N$ 札の本の内,上から $i$ 番目は読むのに $A_i$ 分かかり,$M $ 冊の本の内上から $j$ 番目は $B_j$ 分かかる.
 いずれかのスタックの一番上の本を読んでからそれを取り除く操作を繰り返すことを考える.$K$ 分以内に読み切れる本の最大値はいくらか?

制約

  • $1 \leq N, M \leq 2 \times 10^5$
  • $1 \leq K \leq 10^9$
  • $1 \leq A_i, B_i \leq 10^9$
続きを読む

AtCoder Beginner Contest 172, B : Minor Change

問題概要

 英小文字からなる 2 つの文字列 $S, T$ が与えられる.$S$ の 1 文字を異なる文字に変更する操作を繰り返して $S$ を $T$ に一致させるとき,必要な操作回数の最小値はいくらか?

制約

  • $1 \leq |S|, |T| \leq 2 \times 10^5$
  • $|S| = |T|$
続きを読む

AtCoder Beginner Contest 171, D : Replacing

問題概要

 $N$ 項からなる正整数列 $\{ A_i \}$ がある.ここから,次の操作を $Q$ 回行う.

  • $i$ 回目の操作では,値が $B_i$ である要素をすべて $C_i$ に置き換える

 それぞれの $i$ について,操作後の $\sum A$ を求めよ.

制約

  • $1 \leq N, Q, A_i, B_i, C_i \leq 10^5$
  • $B_i \neq C_i$
続きを読む

AtCoder Beginner Contest 171, B : Mix Juice

問題概要

 相異なる $N$ 個の正整数からなる列 $\{ p_i \}$ が与えられる.ここから $K$ 項を選んで和を取るとき,和として有り得る値の最小値を求めよ.

制約

  • $1 \leq K \leq N \leq 1{,}000$
  • $1 \leq p_i \leq 1{,}000$
続きを読む