ARC143 A - Three Integers
解説にあるような「どれか1つに1を加算する」（その後全部を1引く）操作を読み替えられた場合、上のコードのような感じで解ける。
なお、ABCの値はA[0]A[1]A[2]のリストとし、ソートしてA[0]が大きい前提としている。
A[1]とA[2]にA[0]を合わせるための加算回数をFlatとしているが、その回数だけ全部をマイナスしたいため、最大（結局A[0]なのだが）を超えるとNGとしている。
ここで問題がない場合、Flatにした操作と、Flatにしたことで残る最大の数（Max-Flat）の和なので、結局Maxが答え。
def resolve(): A = list(map(int, input().split())) A.sort(reverse=True) Min = min(A) Max = max(A) Flat = A[0] - A[1] + A[0] - A[2] if Flat > Max: print(-1) return ans = Flat + (Max - Flat) print(ans) resolve()
では、その操作の読み替えが思いつかない場合、どうするのがいいだろう。
ということで、以下のような愚直っぽいやり方に逃げるのもありかもしれない。
A[0]が抜きんでている分を、まずはA[1]に合わせたいが、A[0]だけを相対的に下げる操作は、A[0]とA[1]の選択＋A[0]とA[2]の選択、の複合なので、それを連打する。
これでも終わらないなら、A[0]とA[1]をA[2]に合わせにいく。
この途中でいずれかの値が負に入ったらNG。そうでない場合は、合わせる操作の合計＋A[0]（合った後に残った値）が正解。
import math def resolve(): A = list(map(int, input().split())) A.sort(reverse=True) if A[0] == A[1]: print(A[0]) return ans = 0 need = math.ceil((A[0] - A[1]) / 2) A[0] -= 2 * need A[1] -= need A[2] -= need ans += need * 2 if min(A) < 0: print(-1) return if A[2] == 0: print(ans + A[0]) return need = A[0] - A[2] A[0] -= need A[1] -= need ans += need if min(A) < 0: print(-1) return print(ans + A[0]) resolve()
と、スマートな解にたどり着けなくても、愚直に解けるようになっておいた方がよさそう（どっちも時間内に書けなかった・・・）
ABC257 E - Addition and Multiplication 2
def resolve(): N = int(input()) C = list(map(int, input().split())) Min = min(C) diff = [ [1, C[0]], [2, C[1]], [3, C[2]], [4, C[3]], [5, C[4]], [6, C[5]], [7, C[6]], [8, C[7]], [9, C[8]], ] for i in range(9): diff[i][1] -= Min diff = sorted(diff, key=lambda x: (x[1], -x[0])) keta = N // Min Cost = N - Min * keta ans = [diff[0][0]] * keta diff = sorted(diff, key=lambda x: (-x[0], x[1])) for i in range(keta): if Cost <= 0: break for d in diff: if d[1] <= Cost: ans[i] = d[0] Cost -= d[1] break if keta == 0: ans = [0] print(*ans, sep="") resolve()
つっこみどころがあるにはあるが
- 最小コストの数字（かつ最も数字が大きいもの）を連打し、最大桁数の初期解とする
- 最小コストの数字に対して、各数字に変える時の差分コストを列挙する
- あとは差分コストが低い（かつ数字が大きい）順に貪欲に・・・と思いきや、これをやると、NG。数字が大きい（かつ差分コストが低い）順に貪欲にやる必要がある
- そうでない場合、7777を9777にすべきところ、8877にしてしまうようなケースが発生する
と、ここまではもっと良質な解説があると思うので、この程度に。
地味にハマったポイントとして、巨大な数字を各桁ごとのリストで作成した場合に、どう出力しようとするか？でTLEしたので、メモしておく。
最後の結果出力部分を、いったん結果文字列を作ろうとしてこんな感じにすると、TLEする。
文字列の末尾への追加ならタダみたいなもんだと思い込んでいたが、そんなことはないので、↑のように、リストをそのまま出力しましょう。。。
ansS = "" for a in ans: ansS += str(a) print(ansS)
ABC251 D - At Most 3 (Contestant ver.)
解法は解説を見れば明らかなので略。
色々実験したけど、優位に速度が変わらないような気がした...（誤差の範囲？）
他のpython勢の提出も、17～19msあたりが最速に見えるので、これ以上は言語の限界だろうか
- 入力は受ける、答えとなるリストをrangeで生成する 30ms
- 答えは決め打ちで持っておく 34ms
- 上記に加え、importを減らしinputをreadlineにする 24ms
- もう入力すら無視して、決め打ちの答えを出力 20ms
- 入力無視して、更に一行でやる 18ms
ABC251 E - Tahakashi and Animals
iを1～Nとして、動物iを押さえたときに、用いた行動が、0：iなのか、1：i-1なのか、の2状態を持ち、それぞれの最小コストを更新するようなDPを持つ（苦手なので日本語が微妙…）
ここで、動物2に対して行動2(i)、動物3に対して行動2(i-1)のような選択は意味がないため、コスト0の遷移とする。
また、初期値、すなわち動物1を押さえたのは、行動1なのか、行動Nなのか、うまく表現できないので、このセットをもう一つ持つことにする。 （0→2 1→3に対応）
初期値に行動Nを取り入れている場合、動物Nは気にしなくてよいため、N-1（-2番目）を参照する。そうでない場合は、Nを気にするので、N（-1番目）を参照する。
def resolve(): N = int(input()) A = list(map(int, input().split())) INF = 10 ** 20 DP = [[INF] * N for i in range(4)] DP[0][0] = A[0] DP[3][0] = A[-1] for i in range(1, N): DP[0][i] = min(DP[0][i], DP[0][i - 1] + A[i]) DP[0][i] = min(DP[0][i], DP[1][i - 1] + A[i]) DP[1][i] = min(DP[1][i], DP[0][i - 1]) DP[1][i] = min(DP[1][i], DP[1][i - 1] + A[i - 1]) DP[2][i] = min(DP[2][i], DP[2][i - 1] + A[i]) DP[2][i] = min(DP[2][i], DP[3][i - 1] + A[i]) DP[3][i] = min(DP[3][i], DP[2][i - 1]) DP[3][i] = min(DP[3][i], DP[3][i - 1] + A[i - 1]) print(min(DP[0][-1], DP[1][-1], DP[2][-2], DP[3][-2])) resolve()
ABC250 E - Prefix Equality
先頭xおよびy要素のそれぞれの集合を事前に作っておいて、一致確認できれば簡単だけど、それをやるとTLEする。ある集合の状態をもっと軽量な値として管理したらよさそうで、それをハッシュ的にやる。
初登場の要素が来たら、乱数を生成して、ある要素に対するハッシュ値とする（値域が大きいため、事前にテーブル化はできず、defaultdictでやった）。で、AおよびBのある要素までのハッシュ累積和的なもの（集合を示したいので、集合に変動がない限り、値も変えない）を作っておくことで、集合のハッシュ化的なことができる。
from collections import defaultdict import random def resolve(): N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) Q = int(input()) D = defaultdict(int) ruiSA = [0] * N ruiSB = [0] * N SA = set() SB = set() hashA = 0 hashB = 0 for i in range(N): if D[A[i]] == 0: D[A[i]] = random.randint(0, 10 ** 10) if D[B[i]] == 0: D[B[i]] = random.randint(0, 10 ** 10) if A[i] not in SA: hashA += D[A[i]] ruiSA[i] = hashA if B[i] not in SB: hashB += D[B[i]] ruiSB[i] = hashB SA.add(A[i]) SB.add(B[i]) for i in range(Q): x, y = map(int, input().split()) if ruiSA[x - 1] == ruiSB[y - 1]: print("Yes") else: print("No") resolve()
ABC249 D - Index Trio
カウント対象が成立するためには、左辺が割り切れる必要がある（Aのそれぞれが整数のため）ことから、iについて全探索するとした場合に、Aiの約数を列挙しておくとよさそう。さらに、AjとAk相当は、まじめに探索しなくても、個数から引いてこれそうな気持ちになる。
約数列挙は、元の数が大きい場合に大変になりそうな気がするが、同じ数に対して計算をしなくていいように、とりあえずdefaultdictで持ってみることにした。
あとは、Aiを決めたときにあり得る、仮想的なAjとAkを全探索し、そのパターンが実際いくつあるかを数える。
Ajになり得るのはAiの約数であり、更にAiとAjを決めたときにAkになり得るのは、Ai//Ajである。i,j,kの重複はし放題のため、何ら条件は付けずに、これらの個数をかけ合わせればOK 。（Aに存在しないAjやAkは、個数が0で返ってくるので、変にカウントしてしまうこともない）
※なお、約数列挙はこちらから拝借しました qiita.com
from collections import defaultdict, deque def make_divisors(n): lower_divisors, upper_divisors = [], [] i = 1 while i * i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n // i) i += 1 return lower_divisors + upper_divisors[::-1] def resolve(): N = int(input()) A = list(map(int, input().split())) dy = defaultdict(list) #yakusuu dk = defaultdict(int) #kosuu for a in A: dk[a] += 1 if dy[a] == []: temp = make_divisors(a) dy[a] = temp ans = 0 for _i, v in dy.items(): inum = dk[_i] for _j in v: _k = _i // _j jnum = dk[_j] knum = dk[_k] ans += knum * jnum * inum print(ans) resolve()
ABC246 E - Bishop 2
基本的にはゴリゴリ探索し、枝狩り（というのか？）する。何法っていうのかよくわからない。
ただし、本番中には枝狩り不足で通せず。ソース整理してコメントも残したので、置いておきます。
def resolve(): N = int(input()) Ax, Ay = map(int, input().split()) Bx, By = map(int, input().split()) S = [] for i in range(N): S.append(list(input())) if Ax == Bx and Ay == By: print(0) return # i手目で到達可能なマスの集合。0手目を(Ax,Ay)として更新していく cand = [set() for i in range(N ** 2)] cand[0].add((Ax - 1, Ay - 1)) # 既に探索済の集合も管理していく(重複の防止) seen = set() seen.add((Ax - 1, Ay - 1)) dx = [1, 1, -1, -1] dy = [1, -1, -1, 1] for i in range(1, N ** 2): # i-1で到達可能マスそれぞれから、4方向に進めるだけ進んで、i手目の一覧を作る for Cx, Cy in cand[i - 1]: for j in range(4): diffx = dx[j] diffy = dy[j] while True: # 範囲外もしくはポーンにぶつかったら打ち切り if not ( 0 <= Cx + diffx < N and 0 <= Cy + diffy < N and S[Cx + diffx][Cy + diffy] == "." ): break # 探索済のマスは追加しない。 # ただし、その先は要探索かもしれないので、打ち切らない。 # 既に通った経路と直行してるだけかもしれない。 if not (Cx + diffx, Cy + diffy) in seen: cand[i].add((Cx + diffx, Cy + diffy)) seen.add((Cx + diffx, Cy + diffy)) # 新規の移動(到達可能マス扱い)時に、ゴールと一致したら、手数を出力 if Cx + diffx == Bx - 1 and Cy + diffy == By - 1: print(i) return # i-1手の到達済に今差し掛かるということは、その到達済マスを起点として、 # i手目の他経路にて、探索済or探索する予定なので、打ち切ってよい。 if (Cx + diffx, Cy + diffy) in cand[i - 1]: break diffx += dx[j] diffy += dy[j] print(-1)
