Atcoder 灰diff埋め ARC001~ARC020 振り返り
ARCも意外と灰diff多いですね……
ARC004 A - 2点間距離の最大値 ( The longest distance )【AC】
このコードで提出したところMLEが出ました．メモリの使いすぎというエラーです．このようなエラーは初めて出たので困惑しましたが，これはこの問題が初期のコンテストによるものであり，メモリ制限が厳しいのが理由になります．最近のコンテストはメモリ制限が1024MBであるのに対し，このコンテストは64MBでした．
そして，このコードをPypy3で提出したところ，PyPyはメモリを大きく使うためメモリ制限に引っかかったと言う事になります．Pythonを使えばAC出来ました．
初期のコンテストを解くときはこれに気をつける必要がありそうです．
def find_dist(p1, p2): x1, y1 = p1 x2, y2 = p2 return ((x1-x2)**2 + (y1-y2)**2)**0.5 N = int(input()) lis = [] for _ in range(N): x, y = map(int, input().split()) lis.append((x, y)) ans = 0 for i in range(N-1): for j in range(i+1, N): ans = max(ans, find_dist(lis[i], lis[j])) print(ans)
エラトステネスの篩をPythonで実装して関数化する
概要
以前この記事で
hirohirohirohiros.hatenablog.com
エラトステネスの篩は実装しました．しかし，以前のコンテストでこの関数では対応出来ない問題に当たりました．
このエラトステネスのふるい関数はiが素数の時リストi番目がTrue，素数でないときFalseが入ったリストを返す関数です．しかし，単に素数のみが入ったリストが欲しい場合もあります．このような場合に対応するために，関数を書き換えます．
get_primesというbool型の変数を新たに引数に用意します．なお，既に使われているコードに新たに書き換える必要を無くすためにget_primes=FalseとデフォルトではFalseとなるようにしています．これがTrueの時，新しい処理を追記します．
今まで，あらかじめ全てが素数だと仮定しておき，素数出なかったらFalseにするという処理にしていたので，while文の条件式はp^2
pythonコード
def erato_sieve(x, get_primes = False): """エラトステネスの篩 0からxまでの素数を返す 計算量: O(n loglog n) Args: x (int): 素数判定をしたい数の最大値 get_primes(bool): 素数のみが入ったリストを返すかどうか Returns: list: get_primesがTrueの時 素数飲みが入ったリスト get_primesがFalseの時 i番目が素数ならTrue, そうでないならFalse """ primes = [] prime_list = [True]*(x+1) prime_list[0] = False prime_list[1] = False p = 2 while p <= x: if not prime_list[p]: p += 1 continue primes.append(p) i = p*2 while i <= x: prime_list[i] = False i += p p += 1 return primes if get_primes else prime_list
Atcoder ABC250 振り返り
A - Adjacent Squares【AC】
場合分けしてO(1)で解くことも出来ますが，早解きでミス無く書くのは難しいので(1敗)H, W<=10であることを活かして全探索します．
マスの数は最大でも100しかないので，全てのマスについて辺で隣接しているかチェックすれば良いです．チェックは問題文にある定義を使えば良いです．
H, W = map(int, input().split()) R, C = map(int, input().split()) ans = 0 for h in range(1, H+1): for w in range(1, W+1): if abs(h-R) + abs(w-C) == 1: ans += 1 print(ans)
B - Enlarged Checker Board【AC】
アルゴリズムというよりは実装力が求められる問題でした．nタイル目のnの偶奇で色が決まります．あとは頑張って実装します．
N, A, B = map(int, input().split()) ans = ["" for _ in range(N*A)] for i in range(N): for j in range(N): if (i+j) % 2 == 0: tile = "." else: tile = "#" for ii in range(A): ans[ii+i*A] += tile*B for a in ans: print(a)
C - Adjacent Swaps【AC】
値を入れ替えるときに，リストのどこに値があるのかをindex()関数などで探すとそれだけでO(N)かかってしまうので，ここを短縮することを考えます．辞書で値を取得するのはO(1)で出来るため，辞書でこの操作ができないかを考えます．
鍵にインデックス，値に数字を持つ辞書i2v_dicと，鍵に数字，値にインデックスを持つ辞書v2i_dicの2つを用意します．値がリストのどのインデックスにあるかを調べるためにv2i_dicを使い，実際に値を入れ替える動作をi2v_dicで行います．入れ替えた後，2つの辞書とも値を入れ替える必要があるため気をつけます．
N, Q = map(int, input().split()) i2v_dic = {i:i+1 for i in range(N)} v2i_dic = {i:i-1 for i in range(1, N+1)} for _ in range(Q): x = int(input()) ind = v2i_dic[x] if ind != N-1: v2i_dic[x] = v2i_dic[i2v_dic[ind+1]] v2i_dic[i2v_dic[ind+1]] = ind i2v_dic[ind], i2v_dic[ind+1] = i2v_dic[ind+1], i2v_dic[ind] else: v2i_dic[x] = v2i_dic[i2v_dic[ind-1]] v2i_dic[i2v_dic[ind-1]] = ind i2v_dic[ind], i2v_dic[ind-1] = i2v_dic[ind-1], i2v_dic[ind] ans = [] for i in range(N): ans.append(str(i2v_dic[i])) print(" ".join(ans))
D - 250-like Number【AC】
エラトステネスのふるいを使います．p*q^3<=10^18を満たすqは，pが最小値の2を取ったとしても必ずq < 10^6となる事が分かります．よって探索するp, qは10^6以下の素数である事が分かります．
エラトステネスのふるいを使ってO(N loglogN)で素数を列挙します．これは10^6までなら間に合います．列挙された素数に対してp*q^3＜Nを満たすかをチェックしていけば良いです．
エラトステネスのふるいは以前実装しました．
hirohirohirohiros.hatenablog.com
しかし，これを使って提出するとTLEになってしまいます．コードに誤りがあるわけではありません．このコードの出力は数字iが素数ならi番目がTrue，素数でないならFalseが入ったリストです．この長さ10^6のリストを使って，リスト[i]がTrueなら……とやっていると時間が足りなくなります．
よって，初めから素数のみが入ったリストを出力するようにコードを書き換える必要があります．といっても新しくprimesというリストを用意してやり，prime_listがTrueならprimesにappendするという処理を追記すれば良いです．これによりループする回数が減りACする事が出来ます．
def erato_sieve(x): primes = [] prime_list = [True] * (x + 1) prime_list[0] = False prime_list[1] = False p = 2 while p <= x: if not prime_list[p]: p += 1 continue primes.append(p) i = p*2 while i <= x: prime_list[i] = False i += p p += 1 return primes N = int(input()) prime_list = erato_sieve(10**6+1) ans = 0 l = len(prime_list) for i in range(l-1): for j in range(i+1, l): if prime_list[i] * prime_list[j]**3 > N: break ans+=1 print(ans)
論文読み CLIP まとめ
hirohirohirohiros.hatenablog.com
どんなもの？
画像からその画像を説明している文章を予測するモデル．ゼロショット学習により未知の画像データでも正しく予測できる．
先行研究と比べどこが凄い？
文章を直接予測するのでなく，対応する単語を予測させる．
技術や手法のキモはどこ？
文章を直接予測するのでなく，対応する単語を予測させる．
どうやって有効だと検証した？
共通する要素(例 バナナ)を異なる画風(例 スケッチ おもちゃ)で映した画像で従来のモデルより高い認識精度を確認。
議論はある？
MNISTなど学習データに全く類似したものがない場合正しく予測できていない．
論文読み まとめ
概要
論文を読む機会が増えたので，読んだ内容について落合洋一教授の論文まとめフォーマットに則ってまとめたいと思います．
まとめ
Atcoder 灰diff埋め ABC148C~ABC214C 振り返り
ABCの灰diffが全て埋まりました！次はARCを埋めていきます．
ABC148 D - Brick Break【AC】
ぱっと見難しい問題に見えます．しかし，1,2,3...の順番さえ守っていれば，どのレンガを壊しても答えは変わらない事に気付けば簡単になります．今残す数字をkと記憶しておき，kとレンガの数が一致してたらレンガを壊さずkを+1し，kとレンガの数が異なっていたらレンガを壊します．全てのレンガを見た後k=1，つまりレンガを1つも壊さなかったとき，満足する事が出来ないので-1を出す事に気をつけます．
N = int(input()) A = [int(i) for i in input().split()] ans = 0 k = 1 for a in A: if a == k: k += 1 else: ans += 1 if k == 1: print(-1) else: print(ans)
ABC149 C - Next Prime【AC】
hirohirohirohiros.hatenablog.com
以前実装したエラトステネスのふるいを使います．エラトステネスのふるいは0からNまでの数字について，素数判定をO(N loglog N)で行ってくれるアルゴリズムです．これを使えばN=10^6までの素数判定も十分間に合います（ACしたコードの実行時間は80msでした）．
X以上の素数のなかで，最小の素数を求める問題なので，Xが素数が判定し素数でなければX+1するのをXが素数になるまで繰り返せばよいです．
def erato_sieve(x): """エラトステネスの篩 0からxまでの素数を返す 計算量: O(n loglog n) Args: x (int): 素数判定をしたい数の最大値 Returns: list: i番目が素数ならTrue, そうでないならFalse """ prime_list = [True]*(x+1) prime_list[0] = False prime_list[1] = False p = 2 while p**2 <= x: if not prime_list[p]: p += 1 continue i = p*2 while i <= x: prime_list[i] = False i += p p += 1 return prime_list X = int(input()) prime = erato_sieve(10**6) while not prime[X]: X += 1 print(X)
ABC214 C - Distribution【AC】
まず思い付くのは，時間T[i]にiが宝石を受け取った後その宝石が他の人に受け取られる時間を記録していき，全てのiについて記録が終わったらその最小値を取るという手法です．しかしこの手法では，iについて他の人に受け取られる時間を記録する工程でO(N)，全てのiについて記録する工程でO(N)かかるので，合わせてO(N^2)の計算量が掛かってしまい間に合いません．
そこで発想を逆転し，他の人に受け取られる時間を記録するのでなく，自分が他の人から宝石を受け取る時間について考えるようにします．すると，宝石は隣の人からしか受け取ることはないので，見るポイントは隣の人の時間しかないことが分かります．これでiについて記録する工程がO(1)となるので，全体の計算量はO(N)となり間に合います．
なお，2*N回ループさせないと，T[0]とT[-1]についての探索が行われず正しい答えが求まらないので注意します．
N = int(input()) S = [int(i) for i in input().split()] T = [int(i) for i in input().split()] for i in range(2*N): T[(i+1)%N] = min(T[(i+1)%N], T[i%N] + S[i%N]) for t in T: print(t)
Atcoder 灰diff埋め ABC120C~145C 振り返り
ABC120 C - Unification【AC】
無駄にテクニカルな解法で解いたけれど，解説でよりシンプルな方法に気付いたパターンです．
cou[0]=赤色のボールの数，cou[1]=青色のボールの数とします．Sの左から順にボールを入れていき，ボールの数に合わせcouの値を上下させます．ボールを入れたことでボールが消えるパターンを考えます．異なる色のボールが一つでも存在したら，入れるボールと異なる色のボールが1つ必ず消えます．
異なる色のボールをプログラムで，s^1と表現しました．sはボールの色を表す0か1です．^はxorを表す演算子で0^1=1, 1^1=0となります．右項を1にすれば，s^1はsを反転した値が返ってくることが分かります．これで，異なる色のボールを表せられます．
S = map(int, list(input())) cou = [0, 0] ans = 0 for s in S: if cou[s^1] != 0: ans += 2 cou[s^1] -= 1 else: cou[s] += 1 print(ans)
しかし，そもそも最終的に筒には1種類のボールしか残らないので，少ない方の色のボールは全て消え，その個数分多い方のボールも消えるので2*min(赤色のボールの個数, 青色のボールの個数)とすれば良いです．
S = input() print(2*min(S.count("0"), S.count("1")))
ABC141 C - Attack Survival【AC】
逆から考える事で解けるようになる問題です．問題に書いてあるとおり，正解した人以外のポイントを-1するという方法で解くと，正解者以外の値を-1する必要があるので一問ごとにO(N)の時間が掛かり，問題がQ個あるのでO(NQ)となり間に合いません．
今回は，正解者以外の値を-1する工程がボトルネックとなっているので，ここをなんとかすることを考えます．正解者以外の値を操作しようとするとO(N)ですが，正解者のみの値を操作するのならO(1)です．
まず始めに全員が全ての問題で不正解だったと仮定します．するとポイントはK-Qとなります．ここから，正解者のみに値を+1します．そして，最終的に値が1以上なら勝ち抜けたと分かります．
処理を逆から考える事で計算量を削減できることがある事が分かります．
N, K, Q = map(int, input().split()) A = [K-Q for _ in range(N)] for _ in range(Q): A[int(input())-1] += 1 for a in A: if a > 0: print("Yes") else: print("No")
