AtCoder Beginner Contest 144（参加）

めちゃめちゃサボってしまった（反省）

はじめて４完できたので良かったけど凡ミスで順位すごい下がった気がする（反省）

A問題

与えられた２数が一桁の自然数なら積を、それ以外なら-1を返す atcoder.jp

コード

#!/usr/bin/env python3
import sys

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

if A < 10 and B < 10:
  print(A*B)
else:
  print("-1")

B問題

与えられた数が九九の答えならYes、違ったらNoを返す atcoder.jp

コード

#!/usr/bin/env python3
import sys

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

for i in range(1,10):
  # 1〜9の数字で割り切れて商が10未満
  if N // i < 10 and N % i == 0:
    print("Yes")
    exit()
  else:
    continue
print("No")

C問題

a,bを自然数として、ある座標(a,b)に積abを対応付ける。座標(1,1)にいる時、与えられた数Nが対応付けられた座標まで移動するために最小で縦横何マス移動しなければならないか。 atcoder.jp

所感

積がNとなる２自然数の組み合わせをすべて列挙した上で、各組のうち最小の和を考えれば良い
座標の出発点は(0,0)ではなく(1,1)なので注意

コード

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

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

facts = []   # 積のペアを格納するリスト
# 列挙にはNの平方根まで割れば十分
for i in range(1, math.ceil(math.sqrt(N))+1):
  if N % i == 0:
    facts.append([i, N//i])
sums = []
for fact in facts:
  sums.append(sum(fact))
print(min(sums)-2)   # 出発点を考慮して1+1 = 2を引く

D問題

底面が1辺aの正方形、高さbの直方体の中に体積x³の水が入っている。底面の1辺を床につけたまま直方体を傾けていく時、水をこぼさずに角度何度まで傾けられるか atcoder.jp

所感

どう見ても数学の問題なので、愚直に計算をした。 絵を書くのが面倒（iPad買ったので次から書きたい）なので割愛するけど、
１．（側面の長方形で切断した）断面は三角形or台形
２．断面の対角線が水平になるところが三角形と台形の境目
３．水面は地面と平行になる
の３つを用いればOK

１回目の提出では満杯（＝傾けられない）時の場合分けを忘れてミスし、更に分数の計算ミスでまたWAしてしまったことで無駄に１０分のペナルティを食らってしまった（反省）

コード

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

input = sys.stdin.readline
a, b, x = map(int, input().split())
if a**2*b == x:
  print(0)
  exit()

if 2*x <= a**2*b:
  t1 = a*b**2
  t2 = 2*x
  ans = math.degrees(math.atan(t1/t2))
else:
  t1 = a**3
  t2 = 2*a**2*b - 2*x
  ans = 90 - math.degrees(math.atan(t1/t2))
print(ans)

E問題

要点は下記
１．長さNの２つの数列AとFがある
２．Aの数列の任意の項の値を１減らす操作をK回できる
３．数列AとFの項を１つずつ取り出し、その積から長さNの数列を新しく作る
４．新しく作った数列の最大の項を最小化する取り出し方が存在し、その時の最大の項の値を求める

\( 1 \leq N \leq 2 \times 10^5, 0 \leq k \leq 10^{18} \)

atcoder.jp

所感

上記２の操作を考えないのであれば、直感的にはAを降順ソート、Fを昇順ソートして第k項同士の積から新しい数列を作り、この数列の最大の項（既に最小化されている）を求めればいい。
上記２の操作を考える場合、上記のソートを通じてできた数列の中で最大の項について、対応するAの値を１減らす操作をK回繰り返す。
ただし、このやり方だと計算量がO(NK)となり間に合わない、というとこまで来て何も思い浮かずギブアップ

解説を見て解法に納得したので気が向いたら書く。二分探索を使うらしいけど名前だけ知っててちゃんと使ったことなかった（反省）
解説を見るとこのE問題は解けてよかったなぁ〜と思ってしまった

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)

AtCoder Beginner Contest 138（A~D、過去問）

A問題

入力した文字列の大きさによって出力文字を変える問題 atcoder.jp

コード

#!/usr/bin/env python3

#### input
a = int(input())
s = input()

#### process
if a >= 3200:
  print(s)
else:
  print("red")

B問題

N個の入力に対して、

\( \dfrac{1}{\frac{1}{A_1} + \frac{1}{A_2} + ... + \frac{1}{A_N}}\)

を求める問題 atcoder.jp

所感

ABC139で丸め誤差に苦しめられたのでなるべく誤差がでない形（int）で計算を進める

コード

#!/usr/bin/env python3
from functools import reduce

#### input
N = int(input())
As = list(map(int, input().split()))

# N=1ならそのまま数字を返す
if N == 1:
  print(As[0])
  exit()

#### process
# 分母はA_1〜A_Nの積
numerator = reduce(lambda a, b: a * b, As)
denominator = 0
for i in range(0, N):
  tmp = As.pop(0)
  # 分子は「A_1以外の積」＋「A_2以外の積」＋・・・
  denominator = denominator + reduce(lambda a, b: a * b, As)
  As.append(tmp)

print(numerator / denominator)

C問題

\( N \) 個の数字\( v_i \) の中から2つを選んで平均値に置き換える作業を繰り返した時、最後に残る数字の最大値を求める問題

atcoder.jp

所感

先頭から順番に処理を繰り返していくと、最後に残る値は、

\( \dfrac{\dfrac{\dfrac{v_1 + v_2}{2} +v_3}{2} + v_4}{2} ... \)

であり、これを通分すると、

\( v_1 + v_2 + 2v_3 + 2^2v_4 + ... + 2^{N-2}v_N\)

となるのでこれを最大化するためには数列が小さい順に並んでいればいい。
ということで、ソートを行った後に上記を計算しに行く

コード

#!/usr/bin/env python3

#### input
N = int(input())
vs = list(map(int, input().split()))

#### process
vs_sorted = sorted(vs)
vs_sum = vs_sorted[0]

for i in range(1, len(vs_sorted)):
  # リストのインデックスは0から始まるので数値がずれることに注意
  vs_sum = vs_sum + 2**(i-1) * vs_sorted[i]

print(vs_sum / 2**(N-1))

D問題

（説明略） atcoder.jp

所感

木構造の問題。木構造全然詳しくないのでめちゃくちゃ焦った。
各ノードに対して毎回上からたどっていって計算していくと計算量がO(NQ)になって間に合わない。
あるノードの合計得点はその1つ上のノードの合計得点＋自分の獲得得点で計算できるので、 これをなんとかして計算量を減らせないか考えたが思いつかず。
下記は提出だけしたけどTLE連発したやつ。

DFSもBFSも全然わからないので勉強しないと。。。
グラフ理論も色々調べてみてるけど実装までわからん。。。

コード（失敗）

#!/usr/bin/env python3

import sys
input = sys.stdin.readline

#### input
N, Q = list(map(int, input().split()))
ABs = []
for i in range(0, N-1):
  ABs.append(list(map(int, input().split())))

ABs.sort(key=itemgetter(1))

PXs = []
for i in range(0, Q):
  PXs.append(list(map(int, input().split())))

#### process
scores = [0] * N
above_nodes  = [[x+1] for x in range(0, N)]

for i in range(0, len(ABs)):
  above_nodes[ABs[i][1]-1].extend(above_nodes[ABs[i][0]-1])

for i in range(0, len(PXs)):
  scores[PXs[i][0]-1] = scores[PXs[i][0]-1] + PXs[i][1]

for i in range(0, N):
  node_score = 0
  for above_node in above_nodes[i]:
    node_score = node_score + scores[above_node-1]
  print(node_score, end = ' ')
print("")

AtCoder Beginner Contest 139 A~D（過去問）

A問題

2つの等長文字列SとTが与えられた時、それぞれのn文字目が一致している回数を数える問題 atcoder.jp

コード

#!/usr/bin/env python3
#### input
S = input()
T = input()

#### process
score = 0
for i in range(0, len(S)):
  if S[i] == T[i]:
    score = score + 1

print(score)

B問題

• コンセント穴が1つだけある
• 差込口をA個持つ電源タップが複数ある
• B個のコンセント穴を使いたい

このとき、最小で何個電源タップを使えばよいか atcoder.jp

所感

電源タップを差し込む時に一個のコンセントを使うので、電源タップを差し込むごとにA-1だけコンセント穴が増える
ただし、最後に差し込んだ電源タップではすべてのコンセント穴が空いているのでAだけコンセント穴が増える

ある電源タップにあらかじめコンセントを1個差し込んでおき、この電源タップが最後に差し込む電源タップになるようにすると、 「電源タップを差し込むたびにA-1だけコンセント穴が増えるとき、B-1個のコンセント穴を作るために必要な最小の電源タップ数は何か」という問題になるので、割り算を使って解ける

コード

#!/usr/bin/env python3
import math

#### input
A, B = map(int, input().split())

#### process
print(math.ceil((B-1)/(A-1)))

C問題

長さ \( N \) の数列 \( H_1, H_2, ..., H_N \) が与えられた時、\( H_k \geq H_{k+1} \) は最大で何連続成立するかを求める問題

atcoder.jp

所感

\( 1 \leq N \leq 10^5 \)なので、先頭から全部見ていっても間に合う

コード

#!/usr/bin/env python3

#### input
N = input()
H = list(map(int, input().split()))

#### process
now_step = 0
max_step = 0
for i in range(0, len(H)-1):
  if H[i] >= H[i + 1]:
    now_step = now_step + 1
  else:
    max_step = max(max_step, now_step)
    now_step = 0

max_step = max(max_step, now_step)

print(max_step)

D問題

\(1〜N\)の整数が順番に並んだ整数列\(A\)と、\(1〜N\)の整数を並び替えてできる整数列\(B\)（長さ\(N\)）があるとき、\( \displaystyle \sum_{k=1}^N (A_k \ mod \ B_k) \) の最大値を求める。\( 1 \leq N \leq 10^9\)

atcoder.jp

所感

Nの大きさ的にN回のループ（＝数列の各要素を処理）すら許容されないので、整数問題として考えるのが良さそう。
整数問題の定番としてとりあえずN=1から試していく。 N=1からN=4まで、順列を全通り書いて試してみたところ、

N=1のとき：[1]に対して順列[1]を用意して答えは0
N=2のとき：[1,2]に対して順列[2,1]を用意して答えは1
N=3のとき：[1,2,3]に対して順列[2,3,1]を用意して答えは3
N=4のとき：[1,2,3,4]に対して順列[2,3,4,1]を用意して答えは6
　 となったので、[2,3,4, ..., N, 1]の順列を用意すれば良さそうで、その時の余りは下記で求められる。

\( \displaystyle \sum_{k=1}^{N-1} k = \dfrac{N(N-1)}{2} \)

改めて考えてみると、1〜Nの中で除数としたときに最も剰余を多くできるのはN（最大の剰余はN-1）であり、当然ながら1〜Nの中でこれを満たすためにはN-1を被除数に取るしかない。よってNとN-1、N-1とN-2を対応付けしていき、最後に余った1とNを組み合わせるのが最も剰余を最大化することがわかる。

なんだ今回チョロかったなと思いながら実装へ（フラグ）

コード（１回目）

#!/usr/bin/env python3

#### input
N = int(input())

#### process
print(int(N*(N-1)/2))

結果（１回目）

WAが２つ（絶句）

所感（２回目）

数学的にも合っているはずなのにどうして。。。

上記の証明が間違っている可能性も含め、色々検討した。

• N=1〜4を書き出した時、最大の剰余和を生成する順列は[2,3, ..., N, 1]以外にもパターンがあったことを思い出し、そこにヒントがあるかもしれない
• 整数問題のよくあるパターンとしてNが素数の時に何か起こるのかもしれない
• とりあえず全通り解かせて見るかと思いN=11（数分かかる）くらいまで全部計算させて法則が破れたりしないか確かめる

とか色々やってみたけど、まったくわからず。ここで、そういえばめちゃめちゃ大きい数字を扱うと丸め誤差とかで値がおかしくなることがあったなということを思い出し、改めて調べてみるとドンピシャ。 float型に変換されるときに丸め誤差が悪さをするので割り算の実行タイミングを考慮する必要があった。久々に意識したな、丸め誤差・・・。

（参考）

>>> int(999999999*999999998/2)
499999998500000000　　# 2で割った後の1の位は0だが、

>>> int(999999999*999999998)
999999997000000002　　# 2で割る前の1の位は2・・・？

>>> a=999999999
>>> b=int(a/2)　　　# 先に割っておく
499999999
>>> a*b
499999998500000001     # めでたしめでたし

コード

#!/usr/bin/env python3

#### input
N = int(input())

#### process
if N % 2 == 0:
  tmp = int(N/2)
  print(int(tmp*(N-1)))
else:
  tmp = int((N-1)/2)
  print(int(tmp*N))

AtCoder Grand Contest 039（教訓編）

現状

前回のコードでの漏らし（WA）は以下のようなケース
主にT末尾の変更を適宜合計回数から差し引く処理が上手く行ってなかったぽい（他にも色々あるが）

❯ python main.py debug
abaaba
1
1  # 出力。K=1はほぼ全探索なのでこっちは正しい

❯ python main.py debug
aba
2
2 # abaを2回繰り返すので上と同じ1になるはずだが・・・

反省点と改善点

今回のコンテスト（今までの過去問）を通じて以下の３つを意識していこうと思った

• １．計算量の考慮
• ２．パターンの幅出し
• ３．リカバリ

１．計算量の考慮

「全部試すか否か」と、「全部試さないならどうするか」をまず考える。今回のケース では、

• i . 全探索で間に合うか？　→　Tそのものを扱うと間に合わなさそう（間に合いそうなら愚直にやる）
• ii. どういう方針に変更するか？　→　Sを考えてTに拡張する（＝TをSで分解する）

となるが、ii. はもう少し掘り下げる必要が多分あって、

• A . やりたい処理をもっと効率的に行う実装が実はある（例：バブルソート→マージソート）
• B . 複数の要素に分解して何らかの計算をし、最後に合算する（今回の問題はこれ）
• C . 法則を数式に落とし込んで解の計算を行う（漸化式とか）
• D . 乱択アルゴリズムを使う（一昨日知ってめちゃめちゃ感動した。後述）

みたいに色んなパターンがありそう。上から順番に考えていくのが効率的かも。
ABC140 - Dの分類をどこにするかがちょっと悩ましいけど・・・。
これの引き出しをもう少し増やしていってうまい感じに整理し直したい。

ちなみに、乱択アルゴリズムは下記を読んで知った（特に25ページ目からの行列の問題の解法がすごい）

プログラミングコンテストでの乱択アルゴリズム from Takuya Akiba

www.slideshare.net

元の話に戻り、今回の問題で上記A〜Dを考えてみると、「隣り合わせないための最小置換回数」はソートみたいになんていう名前で呼ばれる処理なのかわからなくて全然ググれないし、ありふれた処理というよりは特殊な処理の気もしたので多分A. は考えなくてよさそう（諦めに近い）
B. の分解を考える場合は、
「元の要素を分解する（最小の）単位は存在するか？」を考えて、存在する場合は以下をどう扱うかを考えればいい

• それ単体での計算結果
• 他と組み合わせた際の計算結果への影響（単位のパターンが複数ある場合、組み合わせ別に考慮）

今回の場合は「隣り合う文字が同じなら置換しないといけない」ことを考えると、

• 「隣り合う2文字のペア」を単位とする（2つが同じ／異なるの2パターンが存在）
• 「同じ文字が1個以上連続する箇所」を単位とする

の2つの単位がぱっと浮かびそう。厳密には端っこに位置する／しないでもパターンを考慮する必要が出てきたりするのでそこは円順列とかじゃない場合は注意しておく。

「それ単体での計算結果」については、Sが100文字以下なので計算量的に上記のどっちの単位を採用しても全探索でOK
ただし、他と組み合わせた際の計算結果への影響については、「同じ文字の連続」については別の「同じ文字の連続」と組み合わせた時につなぎ目で置換処理が発生しない（＝余計な計算をしなくていい）のに対し、「隣り合う2文字のペア」では組み合わせた際にも置換処理するかの判定が必要になってくるので、実装が煩雑になる。
よって、「同じ文字が1個以上連続する箇所」を単位にTを分解し、最後に合算するのがよさそう。

踏まえると、「同じ文字が1個以上連続する箇所」を単位にTを分解し、「その単位自体での置換結果」と、「それを繋げてTに戻す時の処理」を考えればよい。

２．パターンの幅出し

自分でテストする時のテストパターンが貧弱だと考慮漏れに気づかずに火傷をする可能性があるので、どういう基準でパターンを考えていったら良いのかを少しずつ整理したい
計算手法や結果の変わり目がどこかに着目をして、現時点では以下のパターンがありそう。

数値

• 偶数／奇数で（計算手法や結果が）変わるか？
• 正／負で変わるか？
• 0／1／2以上で変わるか？

文字列

• すべて同じ文字／すべて異なる文字で変わるか？
• 対称性のあり／なしで変わるか？

３．リカバリ

２．にも関係するが、今回の問題では「abaaba」みたいな「適当にアルファベット生成して検算したら気づけたじゃん！」な落とし穴にハマったので、これの対策も考えた。
（更に言うと、提出し直してはWAが出てを繰り返してたくさん失敗したので、この非効率さへの反省もある）

そもそも今回の問題だと、「左右のペアを比較して置換をしていく」部分についてはTの長さが短ければ全探索でも解けて正しい答えが得られる。
となると、全探索に頼らない実装をした提出用のコードと計算結果を比較することで、提出用のコードが正しそうかは事前にある程度わかりそう。
そこで、具体的な手順として以下のリカバリも意識しておき、必要に応じて使っていきたい（最初から考える必要はないかも） 　 ① 正しい答えを得られる解き方があるか（全探索とか）
② どの程度まで入力を生成したら必要なパターンをカバーできそうか
主に以下を検討していけばよさそう

• 数値：与えられた数値を大きくしていくときに大きさに依存する非連続な変化があるか？
• 文字列：文字種は何パターン必要か？

例えばSやKが10の時と11の時とで偶奇以外の変化はなさそう
今回のケースでは両隣のアルファベットとの違いだけが問題になるので、アルファベットは3つあれば十分

③ 正しい答えを得られる解き方のコードを書く
④ 入力群を生成するコードを書く
⑤ 提出用のコードの計算部分を関数に書き換える
⑥ 正しい答えを得られるコードと提出用のコードに、生成された入力群を入れて答えを比較する

その他

解き直しは後日。はてブのスタイルだと編集画面だとそんなに読みにくくないのに投稿した記事を見ると読みにくかったりするので文章の見せ方もちょっと意識してみたい気がしてきた。文字が大きすぎるだけなのかな。

AtCoder用のローカル環境

形から入るタイプなのでAtCoderをはじめる前に下記のonline-judge-toolsとatcoder-cliをベースに環境を作りました。 online-judge-tools.readthedocs.io tatamo.81.la

ただ、online-judge-toolsで生成されるテスト問題用ディレクトリの名前と、atcoder-cliで読み込みに行くテスト問題用ディレクトリの名前が異なっているようなのでgithubのコードを元にフォルダ名が統一されるように書き直しました。

上記をより効率的に使うために.zshrcで下記のエイリアスを設定。main.pyが解答用コード、template.pyがテンプレ、sublはsublimeのエイリアスです。
（英語のコメントは文法が適当かも）

#### for atcoder
# check if current dir is atcoder problem dir
function atchk() {
  # dirname of parent of parent of current
  ATDIR=$(basename $(dirname $(dirname $PWD)))
  if [ $ATDIR != "atcoder" ]; then
    echo "invalid directory"
    # source中で単にexitするとシェルが終了してしまう
    return 1 2>&- || exit 1
  fi
}

# execute test
alias attest="atchk && oj t -c \"python main.py\""

# create template file
alias atmain="atchk && atmain_func"
function atmain_func() {
  if [ -e main.py]; then
    echo "main.py already exists."
  else
    cp ../../template.py main.py
    subl main.py
  fi
}

# open problem page
alias atopen="atchk && atopen_func"
function atopen_func() {
  CONTEST=${$(dirname $PWD)##*/}
  PROBLEM=$(basename $PWD)
  command open "https://atcoder.jp/contests/${CONTEST}/tasks/${CONTEST}_${PROBLEM}"}

alias atready="atchk && atopen && atmain"
alias atsubmit="atchk && acc submit main.py"

実際に問題を解くときは、下記の流れでやってます。

• １．> acc new abc140 （テスト用のディレクトリを作成してテストデータ等をダウンロード＋格納）
• ２．> cd abc140/a （問題のフォルダに移動）
• ３．> atready （テンプレから解答用コードを作成してSublimeで開き、合わせて問題のページをブラウザで開く）
• ４．（コードを書く）
• ５．> attest （各テストケースを試す）
• ６．> atsubmit （コードを提出する）

ちなみに現時点のテンプレのソースは先人のテンプレも参考にしつつ以下を使っています（他記事のソースコードでもたまにテンプレの消し忘れ有り）。
ABC141で学んだヒープソートなど、抜けていた知識をこれからどんどん放り込んでいきます（意気込み）。 適当な引数を加えて実行（python ***.py 1 とか）することでデバッグモードに切り替え、IPython.embed()で対話できるようにしています。

railsでもbinding.pryを多用していたのでpythonでもなんとかならないかと思いたどり着きました。
（if em: embed()を対話したい箇所に挿入）

#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

#### input
# a, b = map(int, input().split())
# a = list(map(int, input().split()))
# a = list(map(lambda x: int(x)*(-1), a))  # 各要素を-1倍

# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')

#### function
# @lru_cache(maxsize=10000)

#### process
# if em: embed()

## heapsort, O(NlogN)
# import heapq
# heapq.heapify(A)
# min = heapq.heappop(A)
# heapq.heappush(A, new_element)

AtCoder Grand Contest 039 A（参加＋失敗編）

はじめてのコンテスト参加。ABCだと思ってたけど今週はAGCだったのでこわかった。 結論は０完の爆死（つらい）だったので悔しい・・・

A問題

ある文字列SをK回繰り返してできる文字列Tがあるとき、Tの文字を1文字ずつ変えて（置換して）いって同じ文字同士が隣り合わないようにする最小手順を求める問題 atcoder.jp

所感

\( 1 \leq K \leq 10^9 \)

なので、Tを作るのは諦める。
文字列Sを繰り返したときのTに対する最小置換回数は、文字列Sに対する最小置換回数から計算できそう。
連続させた時に置換回数に影響するのは両端の接続部分のみなので、

• １．Sの各連続２文字の関係
• ２．Sの先頭文字と末尾文字の関係

で場合分けすればOK
１がK回、２がK-1回出現する（２はK回出現＋回数を１引くでもOK）

実際にSの各文字列を書き換える必要はないが、Sの長さが100以下なので書き換えをしても計算量的には問題なし
実際には、１．書き換え無しで解こうとしてWA→２．色々いじってみる→３．途中でわけわからなくなる→４．デバッグ用の出力がほしいので書き換えして出力することに。
書き換えは「ある文字に対して、その両側の文字と異なる文字で上書き」をしたいので、下記のコードで実装した（抜粋）

letters = string.ascii_lowercase　　# a~zの入ったリスト
score = 0　　# 置換回数の初期値

# Sの各連続2文字の関係
for i in range(0, len(S) - 2):　　# i + 2 まで考えるためのrange
  if S[i] == S[i + 1]:　　# 次の文字と同じだったら
    S[i + 1] = letters.strip(S[i]).strip(S[i + 2])[0]　　# 次の文字を前後と異なる文字に置き換え
    score = score + 1　　# 置き換えたので回数を増やす

# 最後の2文字は別個で処理（「次の次の文字」が存在しないため）
if S[-2] == S[-1]:
  S[-1] = letters.strip(S[-2]).strip(S[0])[0]
  score = score + 1
else:
  # Sの先頭文字と末尾文字の関係
  # 最後の2文字が同じ場合は先頭を考慮して置き換えるので、この処理は必要ない
  if S[-1] == S[0]:
    S[-1] = letters.strip(S[-2]).strip(S[0])[0]
    score = score + 1

上記に加え、Tの末尾は置換する必要がないので、Tの末尾が置換されていたら回数を１減らせば良い ところが提出したらRE／WAが出てしまい、下記が考慮から抜け落ちていたことに気づく。

• 1文字のみの入力（当然REになる）
• 連続させたときに置換回数が減るケース（後述）

前者は凡ミスすぎるけどとりあえずifで処理。
後者は以下の例が該当する。

例．aabaを2回繰り返す

各連続2文字では置換箇所は１箇所で、先頭と末尾を見ると置換箇所は１箇所
1箇所 × K + 1箇所 × K - 1 にK = 2を代入して、置換回数は3となるが、
aabaaaba
↓
acbacaba
とできるので実際は2回で良い。
これが例外的になるのは、2個くっつけた結果前半のaabaはacbaになり、後半のaabaはcabaになっていて置き換え方が異なっている点。
そこでSを2個くっつけたものに対して置換回数を数えて最後に合算することにした。
（思えばここで単純に2個くっつけて終わらせたのが誤算・・・？）

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

#### input
S_orig = list(input())
K = int(input())

# 1文字の時の処理
if len(S_orig) == 1:
  if K == 1:
    print(0)
    exit()
  else:
    # TをK文字のSにしてしまう
    S_orig = S_orig * K
    K = 1

# Sを倍にする
S = S_orig * 2

### 前述の計算 ここから ###
letters = string.ascii_lowercase
score = 0
for i in range(0, len(S) - 2):
  if S[i] == S[i + 1]:
    S[i + 1] = letters.strip(S[i]).strip(S[i + 2])[0]
    score = score + 1

if S[-2] == S[-1]:
  S[-1] = letters.strip(S[-2]).strip(S[0])[0]
  score = score + 1
else:
  if S[-1] == S[0]:
    S[-1] = letters.strip(S[-2]).strip(S[0])[0]
    score = score + 1
### ここまで ###

# 2個くっつけた場合、前半と後半で置き換え方が異なりうるので、
# 置換回数を別個に計算する（pre = 前：previous, fol = 後：following）
score_pre, score_fol = 0, 0
for i in range(0, len(S_orig)):
  if S_orig[i] != S[i]:
    score_pre = score_pre + 1

for i in range(0, len(S_orig)):
  if S_orig[i] != S[len(S_orig) + i]:
    score_fol = score_fol + 1

# Kの値に応じて集計
if K == 1:
  total = score_pre
elif K % 2 == 0:
  total = (score_pre + score_fol) * K / 2
else:
  total = (score_pre + score_fol) * (K - 1) / 2 + score_fol
# 最後の文字を置換する必要がないのに置換していたら1回分回数を減らす
if (S_orig[-1] != S[-1]) and (S_orig[-1] != S_orig[-2]) and (S_orig[0] != S_orig[-1]):
  total = total - 1
print(int(total))

ここまで書いて最後の１つのWAが解消できず、失敗
解説放送を見て色々思うところがあったので別途書く予定