AtCoder Beginner Contest 143（参加）

最近はAOJの問題とかQiitaの記事を見ながらスタックとキューの応用を勉強したりグラフ理論のためのnetworkxを使ってみたりしていてAtCoder全然解いてなかったので既に懐かしい感じになってしまった。

待ちに待ったはじめてのABCなので直前めっちゃドキドキした。

結果

がんばります（3完/6問）。
まだまだ知らない基礎知識がたくさんあると思うけどABCならA〜Cは基本落としてはいけないと思えるようになったのでA〜Dの4完を次の目標にしたい。

A問題

解説略 atcoder.jp

コード

#!/usr/bin/env python3
import sys

input = sys.stdin.readline
A, B = map(int, input().split())

if A <= 2*B:
  print(0)
else:
  print(A - 2*B)

B問題

与えられた数列の任意の2値の積の総和を求める問題 atcoder.jp

所感

計算量的に間に合うので愚直にやる

コード

#!/usr/bin/env python3
import sys

input = sys.stdin.readline
N = int(input())
Ds = list(map(int, input().split()))

sum = 0
for i in range(len(Ds)):
  for j in range(i + 1, len(Ds)):
    sum += Ds[i] * Ds[j]
print(sum)

C問題

与えられた文字列に対し、すべての連続する文字を1連続に短縮した際の文字列の長さを求める問題 atcoder.jp

所感

1文字目から見ていって直前の文字と異なっていたらリストにpushしていけばいい。

コード

#!/usr/bin/env python3
import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
Ss = list(input())

ans = []
for S in Ss:
  if ans == []:
    ans.append(S)
  elif ans[-1] == S or S == '\n':
    continue
  else:
    ans.append(S)
print(len(ans))

D問題

長さの異なるN本の棒があるとき、三角形のできる組み合わせ数を求める問題（長さが同じ棒同士は区別される） atcoder.jp

所感

三角形の成立条件は大小関係で定義できるので、ソートを真っ先に考えた。

棒の本数が\( 3 \leq N \leq 2*10^3 \)なのでO(NlogN)のsort()を用いてもいけそうだが、棒の長さが1〜1000までしかないようなので、ソートの勉強をしてた時に見つけたO(N)のソートが使えそうと判断。

1〜1000に対応する配列を確保し、N個の値を先頭から見ていって対応するインデックスに格納していくことで実質ソート完了。
インデックスが数値の大小関係に対応しているので、三角形の成立条件を元にスライスし、場合の数を足し合わせることで計算。
ただし、同じ長さの棒を使う場合が存在するので別途Combinationで処理。
ここまででO(N²)で実装し終わった気になっていたが、気になってk個の要素のSliceの計算量をみたらO(k)だったので計算量はO(N³)かもしれない…（Twitterを見ているとO³の単純な3重ループ実装でも通ったとの声。Pythonでも？）

以下のコードを提出したけどWAが出てしまったので何が間違っていたのか後日考えて反省会の予定。A〜Cまでは15分かからなかった（とはいえまだまだ遅い）のにDで残りの85分を使ってしまったので非常にもったいない。
A〜Cに時間かかりすぎ問題はペナルティを恐れて「こんなに簡単でいいのか？見落としはないか？」となって時間を消費しがちなのが効いている気がするのでここは慣れなのかもしれない。

コード（失敗）

#!/usr/bin/env python3
import sys
import copy

input = sys.stdin.readline
N  = int(input())
Ls = list(map(int, input().split()))

L_map = [0 for _ in range(1000 + 1)]
for L in Ls:
  L_map[L] += 1
L_map_orig = copy.deepcopy(L_map)
ans = 0
for i in range(1, 1000):
  if L_map[i] == 0: continue
  a = L_map[i]
  L_map[i] -= 1
  for j in range(i, 1000 + 1):
    if L_map[j] == 0: continue
    b = L_map[j]
    L_map[j] -= 1
    if i == j:
      ans += int(a*(a-1)/2) * sum(L_map[max(j-i+1, j+1):i+j])
      if a >= 3:
        ans += int(a*(a-1)*(a-2)/6)
    else:
      ans += sum(L_map[max(j-i+1, j+1):i+j])
      if b >= 2:
        ans += int(b*(b-1)/2)
    L_map[j] = L_map_orig[j]
  L_map[i] = L_map_orig[i]
print(ans)