AtCoder Beginner Contest 125 C - GCD on Blackboard
1月以来このブログ放置してたけど、ABCが思いのほか早く全完できたので解説記事を書いております。
解法
答えはAのどれかの要素の約数なので、答えの候補として（いっぱい約数がありそうな）max(A)の約数を列挙して配列Pに入れ、Aの要素それぞれがそれ（max(A)の約数）を約数に持つかチェックしていき、約数に持たないようなのが一つ以下であればそれを書き換えれば良い……と思って提出したのだけどWA。これは
N = 2
A = [2, 5]
で答え1になってしまう（P = [1] だが、5を2に書き換えれば正しい答えの2にできる）ので駄目だと気づいた。
そこで「一つしか書き換えられないので、答えはAの中で最大のものと2番めに大きいものどちらかの約数である必要がある」
と気づき、Aの中で最大のものと2番めに大きいものそれぞれの約数を配列Pに入れて上記の作業をしてAC。
（今考えてみると任意の異なる2つの要素であればいいので最大のものと2番めに大きいものでなくてよい、あとPの要素を大きい方から見ていって条件を満たせば出力して打ち切り、でよかった）
クソ汚いコード。
import math N = int(input()) A = sorted(list(map(int,input().split()))) def gcd(a,b): if b == 0: return a return gcd(b,a%b) M = A[-1] P = [1,M] for k in range(2,math.ceil(math.sqrt(M))+1): if M % k == 0: P.append(k) P.append(M//k) M = A[-2] P.append(M) for k in range(2,math.ceil(math.sqrt(M))+1): if M % k == 0: P.append(k) P.append(M//k) P = set(list(P)) ans = 1 for p in P: t = 0 for k in range(N): if A[k]%p != 0: t += 1 if t == 2: break if t <= 1: ans = max(ans,p) print(ans)
2019年の目標
2019年が始まったので目標を立てました！全部達成したい！（年始特有のハイテンション）
AtCoderで青（レート1600以上）になる
現在のレートは1213。400点以上の問題を埋めていき、コンテストにちゃんと出て復習していれば達成できると思う。
ベンチプレス100キロ
去年から不定期に市営ジムへ10回ほど行って75キロなので、毎週通えば今年中に100キロ挙がりそう。ジムに行くのが面倒だけど、運動すると気分も良くなるので頑張ろう。
片手懸垂
現在はフィニッシュ状態での片手懸垂ホールドが両手とも5秒程度、加重懸垂40キロ（体重55キロ）。梅雨頃まで加重とネガティブで筋力を強化して、夏に体重を落としつつ挑戦すれば可能なはず。
語学も何か目標があったほうが良いかなーと思いつつ、当面は現状維持で頑張ろうと思います。
気が向いたらTOEIC受けるかも。
CADDi 2018 C - Product and GCD
問題概要
N個の自然数a1,a2,...aNがある。a1*a2*...*aN = P であるとき、a1,a2,...aNの最大公約数は？
1 <= N,P <= 10^12
解法
N>=Pのときは最大公約数が1になる（a1,a2,...aNは全部自然数だから、少なくとも1つは1がある）。
N = 1のときはP自身が答え。
これらでないとき、a1,a2,...aNの公約数がkとすると、P = a1*a2*...*aN はkでN回割り切れる、つまりP%(k^N)==0。
これを(k^N)がP以下の場合で順に試していくのだけど、Nは10^12以下なので、Nが大きいとTLEになる。
そこでPの制約に着目する。10^12 < 2^40より、Nが40以上ならば最大公約数は1である。
（Nが40以上だと、a1,a2,...aNが全部2だとしてもPは10^12を超えてしまうため、少なくとも1つは1。つまり最大公約数1。）
N, P = map(int,input().split()) if N >= 40 or N >= P: print(1) exit(0) if N == 1: print(P) exit(0) ans = 1 k = 1 while pow(k,N) <= P: if P%pow(k,N)==0: ans = k k += 1 print(ans)
AtCoder Beginner Contest 114 C - 755
問題概要
1以上N以下の整数で、「十進法で表記したとき、数字7, 5, 3がそれぞれ1回以上現れ、これら以外の数字は現れない」ものはいくつあるか？
1 <= N < 10^9
解法
入力例3が最大のN（=99999999）で、このときの答えが26484だから、全部作れそう。
itertoolsのproduct（直積）でrepeat = kとすると、k個の["3","5","7"]から1個ずつ要素を取り出してきてできるセットのリストが作れる。
例えば list(itertools.product(["3","5","7"], repeat=2)) （これはlist(itertools.product(["3","5","7"],["3","5","7"]))と同じ）だと
[('3', '3'), ('3', '5'), ('3', '7'), ('5', '3'), ('5', '5'), ('5', '7'), ('7', '3'), ('7', '5'), ('7', '7')]になる。
これを使って3回以上Nの桁数回以下だけ["3","5","7"]から要素を取り出してきて、3,5,7が一つ以上入っていればくっつけてintに変換してLに加える。
あとはLをソートして、Nが挿入できる位置を答えにする。
# ABC 114 C import itertools, bisect N = int(input()) d = len(str(N)) L = [] for k in range(3,d+1): for a in itertools.product(["3","5","7"], repeat=k): if "3" in a and "5" in a and "7" in a: L.append(int("".join(a))) L = sorted(L) print(bisect.bisect_right(L, N))
AtCoder Beginner Contest 112 C - Pyramid
問題概要
（以下、座標は全部整数とする）
ピラミッドがある。
(Cx,Cy)が一番高く、ある(x,y)での高さは|Cx-x|+|Cy-y|だけ低い。高さは負にならない。
N個の座標とそこの高さが与えられるので、中心の座標と高さを求めたい。
解法
N=100, Cx,Cy<=100より全探索できる。
中心座標の候補xとyは0から100まで、高さの候補hは入力で一番高かったものmからm+100まで、入力が条件に合うかどうか見ていく。1つでも合わなかったらその時点で打ち切り。N個全部大丈夫だったら出力して終了。
x,yは0以上100以下だけど高さは10**9までなことに注意。（本番では8WAもしてしまった。気をつけよう！）
N = int(input()) L = [list(map(int, input().split())) for k in range(N)] m = 0 for l in L: m = max(m,l[2]) for x in range(101): for y in range(101): for h in range(m,m+101): f = 1 for l in L: if l[2]!=max(h-abs(l[0]-x)-abs(l[1]-y),0): f = 0 break if f: print(x,y,h) exit(0)
HACK TO THE FUTURE 2019予選に参加しました（解答解説ではなく感想文です）
はじめてのマラソン形式☆
マラソンマッチって設定が複雑そう＆実装が重そうで敬遠してたんだけど、時間的に参加しやすいし、今月はなるべく多くのコンテストに出ることが目標だから出てみた。マラソンに関する知識ゼロの状態で参加。
結果は3時間弱頑張って91963点（199位）
白紙提出だと80940点なので、それ以上の点数を取れて嬉しい。
最終的な解答はこれ
やったこと
1. 白紙提出（周りを壁で囲っただけ）→80940点
2. 最終的に4つ以上のロボットがくるとこにDをおいてみる→ ほんの少しだけ良くなる
（ここで「競プロ マラソン」でググる。すると今回の主催者であるtsukammoさんの記事競プロ解法紹介～レベル別マラソンの戦い方～ - Qiita
が一番上に出てくる（とてもありがたい）。どうやら初心者は乱択というのをするといいらしい。ということまで知ってから買い物に行く。そしてご飯を食べる。chokudaiさんにあやかってたこ焼きも食べる。）
3. シミュレーション（盤面をランダムにいっぱい生成して、点数を計算して、一番良かった盤面を出力。DとTマスは実装が難しいので入れない。ロボの存在できるマスが減るから#も入れない。）→90000点ちょい
4. チキンレース（対称性から、Rを使わずLと.だけで盤面を生成しても同じと気づく（よく考えると違ってたが結果オーライ）。あとはTLEにならない程度に繰り返しを増やす。）→ 91963点
3の実装が難しかったけど、最終的に思い通りのものができたときは興奮した。
題意すら理解できなかったらどうしようとか正の点数とれるかしらとか不安だったけど参加してみたらすごく面白かった。これからはマラソンの定石も勉強して、積極的にマラソンマッチにも参加していきたい。
作問はもちろんのことヴィジュアライザと賞金も用意していただいたおかげで心理的ハードルが下がったので、主催者のお二人にとても感謝しています。
DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 C-収納
テストも兼ねての初投稿です☆
収納
https://ddcc2017-qual.contest.atcoder.jp/tasks/ddcc2017_qual_c
問題概要
長さCの容器と、いろんな長さのN本の棒がある。1つの容器には2本まで入れられる。なるべく少ない容器に収納したい。
解法
ソートして貪欲（300点問題にはよくある）。小さい方と大きい方から見ていき、2本入れられれば入れる。
普通のリストだと間に合わなそうなのでdequeを使った。これは両端からすばやく要素を取り出せるので便利。
from collections import deque N, C = map(int,input().split()) L = [int(input()) for k in range(N)] M = deque(sorted(L)) ans = 0 while len(M) > 1: l = M[0] r = M[-1] if l+r+1 <= C: M.popleft() M.pop() ans += 1 else: M.pop() ans += 1 print(ans if len(M)==0 else ans+1)
