私の記録ブログ

趣味の記録

Atcoder ABC 143 を解いてみた(python3)

AtCoder python3 今度やります 競技プログラミング

解説動画【YouTube】

-A. Curtain

問題ページ【A - Curtain】

問題文

窓の横方向の長さはAであり、横方向の長さがBのカーテンが２枚取り付けられています。
（カーテンは縦方向には窓を覆うのに十分な長さがあります。）

窓のうちカーテンで隠されていない部分の横方向の長さが最小になるようにカーテンを閉めます。このとき、カーテンで隠されていない部分の合計の横方向の長さを求めてください。


制約

  • 1 ≦ A ≦ 100
  • 1 ≦ B ≦ 100
  • A, B は整数である。


考え

与えられたカーテンの長さを二倍にして窓の長さと比較する。
カーテンが長い場合は 0 を出力し、それ以外の場合は余った窓の長さを出力する。


解法

私のコンテスト中の解法

# -*- coding: utf-8 -*-
a, b = map(int, input().split())

if a <= b*2:
    print('0')
else:
    print(a-b*2)

実行時間：17 ms メモリ：2940 KB

-B. TAKOYAKI FESTIVAL 2019

問題ページ【B - TAKOYAKI FESTIVAL 2019】

問題文

N個のたこ焼きがふるまわれる予定です。このうち i 個目のたこ焼きのおいしさは di です。
ところで、おいしさが x と y であるたこ焼きを一緒に食べると、体力が x × y 回復することが一般に知られています。
N個のたこ焼きから、２個を選ぶ方法は\frac{N×(N-1)}{2}通り考えられます。それぞれについて、一緒に食べたときの体力の回復量を求めて、その総和を出力してください。

制約

  • 入力は全て整数である。
  • 2≦ N ≦ 50
  • 1≦ di ≦ 100


考え

愚直に全組み合わせを計算して、合計値に足していく。


解法

私のコンテスト中の解法

# -*- coding: utf-8 -*-
n = int(input())
d = list(map(int, input().split(' ')))

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans = ans + d[i]*d[j]

print(ans)

実行時間：17 ms メモリ：2940 KB

-C. Slimes

問題ページ【C - Slimes】

問題文

N匹のスライムが横一列に並んでいます。これらの色に関する情報が、長さNの英小文字からなる文字列Sで与えられています。左から i 番目のスライムは、Sの i 文字目に対応する色を持っています。

同じ色を持ち隣接するスライムは融合し、色は変わらずに１匹のスライムとなります。このとき、融合した後のスライムは、融合する前の各スライムが隣接していた他のスライムと隣接した状態になります。

最終的に存在するスライムは何匹となるでしょうか。


制約

  • 1 ≦ N ≦ 10^{5}
  • |S| ＝ N
  • Sは小文字からなる。


考え

文字列のすべての隣接関係を調べて、それが異なったときカウントを増やす。


解法

私のコンテスト中の解法

# -*- coding: utf-8 -*-
n = int(input())
s = list(input())

# 1種類は確実にいる
ans = 1

s1 = s[0]
for i in range(1, n):
    s2 = s[i]
    if s1 != s2:
        ans += 1
    s1 = s[i]

print(ans)

実行時間：182 ms メモリ：13476 KB

-D. Triangles

問題ページ【D - Triangles】

問題文

N 本の棒があり、 i 本目の棒の長さは L_{i} です。

これらのうち３本の棒を使って三角形を作ります。このとき、棒の長さを a, b, c として、以下の条件がすべて成り立たなければなりません。

  • a\ ＜\ b\ ＋\ c
  • b\ ＜\ c\ ＋\ a
  • c\ ＜\ a\ ＋\ b

作れる三角形は何種類あるでしょうか。ただし、２つの三角形は、そのうちー方のみに使われている棒が存在するときに異なるとします。

制約

  • 入力は全て整数。
  • 3\ ≦\ N\ ≦\ 2\ ×\ 10^3
  • 1\ ≦\ L_i\ ≦\ 10^3


考え

※３重ループで愚直に解いたらTLEになりました。（じつはC++だと通るらしい。）

AtCoder の解説動画を参考にしました。

ここでの条件を以下とする
a < b < c
a + b > c

棒が7本あるとする
L = 2, 3, 4, 6, 6, 7, 10

a = 3, b = 6
と置くと a+b = 9 となり、条件より c = 6, 7となる。つまり

b < c < a+b

a+b の境目を探すのに時間がかかっちゃうので、にぶたん（二分探索）を使う。

にぶたんとは
【YouTube】
python標準ライブラリで簡単にぶたん
【Python標準ライブラリ：順序維持のbisect - Qiita】


解法

解説をpythonで書き直してみました。

# -*- coding: utf-8 -*-
# にぶたん用
from bisect import bisect_left

n = int(input())
l = sorted(list(map(int, input().split(' '))))

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        a = l[i]
        b = l[j]
        ab = a+b
        idx = bisect_left(l, ab)

        # b < c < idx
        ans += max(0, idx-j-1)

print(ans)

実行時間：1918 ms メモリ：3188 KB

-E. Travel by Car

問題ページ【E - Travel by Car】

-F. Distinct Numbers

問題ページ【F - Distinct Numbers】