AtCoder Beginner Contest 103

A - Task Scheduling Problem

問題

  • 3個のタスクがあり、それぞれに値 $A_1,A_2,A_3$ が決められている
  • 最初のタスクはコスト0で完了できる
  • 2番目以降の完了には、直前のタスクとの $A_i$ の差の絶対値のコストがかかる
  • 全てのタスクを完了させるためのコストの最小値は?

解法

選ぶタスクの $A_i$ を増やしたり減らしたり行ったり来たりすると、往復する分が無駄なコストとしてかかってしまうので、小さい方から徐々に増やす(または大きい方から減らす)のがよい。

間を省略すると、$A_1,A_2,A_3$ の最大値ー最小値が答えとなる。

a, b, c = map(int, input().split())
print(max(a, b, c) - min(a, b, c))

B - String Rotation

問題

  • 文字列 $S,T$ がある
  • 文字列 $S$ を「回転させる」とは、$S$ の末尾の文字を先頭に持ってくる操作を指す
    • ABCDE → EABCD
  • 文字列 $S$ を回転させて、$T$ に一致させられるか調べよ

解法

全部試す。

s = input()
t = input()
for _ in range(len(s)):
    if s == t:
        print('Yes')
        break
    s = s[-1] + s[:-1]
else:
    print('No')

C - Modulo Summation

問題

  • 正整数列 $\{a_1,a_2,...,a_N\}$ がある
  • 1つの正整数 $m$ に対して、$f(m)=(m \mod{a_1})+(m \mod{a_2})+...+(m\mod{a_N})$ とする
    • $X\mod{Y}$ は、$X$を$Y$で割った余り
  • 上手く $m$ を選んで $f$ が取れる最大値を求めよ

解法

ある $a_i$ で正整数を割った余りは $0$~$a_i-1$ の間である。つまり最大は $a_i-1$ である。

全ての $a_i$ について最大値 $a_i-1$ を取れるような $m$ が存在すれば、$f$ の最大値は $(a_1-1)+(a_2-1)+...+(a_N-1)$ となる。

じゃあ、そんな $m$ は存在するのか。

最大値 $a_i-1$ を得られるのは、$a_i$ の倍数から1少ない数 $m=ka_i-1$ の時である。

$m'=a_1\times a_2 \times ... \times a_N$ のように全ての $a_i$ をかけてしまえば、$m'$ は $a_1$~$a_N$ 全ての数の倍数である。

よって、$m=m' - 1$ とすることで、全ての $a_i$ に対して、最大値の $a_i-1$ が得られる。

$m$ を実際に計算する必要は無い。

n = int(input())
aaa = list(map(int, input().split()))
ans = 0
for a in aaa:
    ans += a - 1
print(ans)

D - Islands War

問題

  • 東西1列に並んだ $N$ 個の島がある
  • $N-1$ 本の橋によって、隣同士の島が結ばれている
  • いくつかの島で戦争が起こり、以下のような要望が $M$ 個寄せられた
    • 島 $a$ と $b$ を、その間にあるいずれかの橋を壊して、移動できないようにしてほしい
  • 全ての要望を叶えるために、壊す橋の最小数はいくつか?

1      2      3      4
○===○===○===○

> 1と3を移動できないように
> 2と4を移動できないように

→2と3の間にある橋を壊せば、2つの要望を叶えられる
答えは1本

解法

必要が生じるまで橋は壊さないことにして、西から順に見ていく。

ある要望 $a_i,b_i$ について、$b_i$ まで見た時に、$a_i$ 以降のどの橋も壊されてなければ、$b_i-1$ と $b_i$ の間の橋を壊す必要がある。

        ai      bi
○=○=○=○=○=○=○=○
                ↑ココマデミタ

        ai      bi
○=○=○=○  ○=○=○=○
              ↑壊す必要がある

他の要望のために既に $a_i$ 以降のいずれかの橋が壊されていれば、何もしなくてよい。

        ai      bi
○=○=○  ○=○=○=○=○

壊す時、$a_i$~$b_i$ の間ならどの橋でもいいのだが、出来るだけ右の橋を壊した方が、他の要望の区間を多く含めるようになる。

         a       b
○=○=○=○=○=○=○=○
         ~~~~~~~~
     ~~~~~~~~~~~~~~~~
             ~~~~~~~~~~~~
          ↑  ↑
          ①  ②

$b_i$ の小さい方から見ていくので、①を含み、右端がbより右にある区間は、必ず②も含んでいる。

実装

まず各要望について「$a_m$ と要望番号 $m$」「$b_m$ と要望番号 $m$」の計 $2M$ 個の情報をリスト化し、ソートする。

ソート時、同じ島なら $b$ の方が $a$ より前に来るようにする。($b_1$ と $a_2$ が同じ島である2つの区間は、共有する橋を持たないため)

    a1      b1
○=○=○=○=○=○=○=○
            a2      b2

「保留中リスト」と「確定済みリスト」を用意し、上記のソート済みリストを順に見ていく。

$a_i$ が出てきたら、要望番号 $i$ を保留中リストに蓄積する。

$b_i$ が出てきたら、

  • 要望番号 $i$ がまだ叶えられてなければ、(確定済みリストに無ければ)
    • 橋を1つ壊す
    • 保留中リストの要望を全て確定済みリストに移す
    • 保留中リストを空にする
  • 要望番号 $i$ が既に叶えられていれば
    • 何もしない

以上で、壊した橋の数が答えとなる。

n, m = map(int, input().split())
ab_list = []
for i in range(m):
    a, b = map(int, input().split())
    ab_list.append((a - 1, 2, i))
    ab_list.append((b - 1, 1, i))

ab_list.sort()
ans = 0
separated = [False] * m
buf = set()
for island, ab, i in ab_list:
    if ab == 1:
        if separated[i]:
            continue
        else:
            ans += 1
            for j in buf:
                separated[j] = True
            buf.clear()
    else:
        buf.add(i)
print(ans)

実装2

もっとよい実装が解説されていた。

$(b,a)$ ペアについてソートして、「最後に壊した最も東の橋 $r$」を記録しながら西から見ていく。

$a$ が $r$ より小さければ、既に要望は叶えられている。

$a$ が $r$ より大きければ要望はまだなので、橋を壊して$r=b$ に更新する。

要望番号を管理しなくても、これで十分カウントできる。

また、$b$ が同じ要望が複数ある場合、必要なのは $a$ が最も東にある1つだけなので、その辺の重複を最初のソートリスト作る時に削除すると、後半のループが減ってなお高速になる。

n, m = map(int, input().split())
disputes = []
for i in range(m):
    a, b = map(int, input().split())
    disputes.append((b, a))
disputes.sort()
ans = 0
most_right_bridge = 0
for b, a in disputes:
    if most_right_bridge <= a:
        ans += 1
        most_right_bridge = b
print(ans)

programming_algorithm/contest_history/atcoder/2018/0721_abc103.txt · 最終更新: 2018/07/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0