Atcoder 灰diff埋め AGC002~AGC024 振り返り
AGC021 A - Digit Sum 2【AC】
N 以下の正の整数の10進法での各桁の和の最大値を求める問題でした.0からN順に各桁の和を求めていって最大値を出す方法では,N<10^16であるため間に合いません.
総和の最大値なので,単純に考えると沢山9がある数字が最大値のように思います.実際にこれは正しく,例えばN=555なら,499が最大になります.これは各桁を9に変換し,N以下である必要があるため1桁目を-1する操作と言えます.555なら1桁目の5を4にし,それ以外の5を9に変換してます.
これでACかと思いきや例外がありWAです.N=5などNが1桁だった場合です.この方法だとN=4となってしまいます.よってNの各桁の総和と上記処理をした総和の大きい方を出力すればACになります.
N = list(map(int, list(input()))) print(max(N[0]-1 + 9*(len(N)-1), sum(N)))
Atcoder ABC255 振り返り
A - You should output ARC, though this is ABC.【AC】
言われた通りにします.atcoderは大抵1-indexなので,入力された数字は-1する事を忘れないようにします.
R, C = map(int, input().split()) A = [] A.append([int(i) for i in input().split()]) A.append([int(i) for i in input().split()]) print(A[R-1][C-1])
B - Light It Up【AC】
N<1000なので全探索しても間に合います.
光源とその他の点同士の距離を求めておきます.距離をソートしておき,距離が小さい方からその点は光に照らされたとしてカウントしていきます.カウントがNになったらその時の距離を答えとして出力します.あらかじめ距離をソートしているので,始めにカウント==Nとなった時の距離が最小の距離となります.
最初の提出時には距離を入れるリストdisに,距離と相手の点の2つの要素が入ったリストをappendしていましたが,これではTLEになりました.リストのソートは各要素に対してソートを回すので遅くなります.disに2つの要素が入ったリストをappendするのではなく距離のみをappendするようにしました.そして,それに対応する相手の点は距離がkeyで相手の点をvalueにした辞書を作るようにしました.これでソートが早くなりACする事が出来ます.
N, K =map(int, input().split()) A = [int(i)-1 for i in input().split()] tizu = [] for _ in range(N): tizu.append([int(i) for i in input().split()]) dis = [] dic_dis = {} for a in A: for j in range(N): if a == j: continue d = (abs(tizu[j][0] - tizu[a][0])**2 + abs(tizu[j][1] - tizu[a][1])**2)**(1/2) dis.append(d) dic_dis.setdefault(d, []) dic_dis[d].append(j) dis = sorted(dis) dic = {i:0 for i in range(N)} cou = K for a in A: dic[a] = 1 ans = 0 for d in dis: for k in dic_dis[d]: if dic[k] == 0: cou += 1 dic[k] = 1 ans = d if cou >= N: print(ans) break
C - ±1 Operation 1【AC】
初項と項数が決まっているため,良い数の上限下限が決まっています.Xがその範囲に入るかどうかでまず処理を変えます.範囲に入らなかった場合,単純にXから上限下限の値を引けば求まります.
良い数はA+(N-1)Dで求まります.この問題はX-(A+(N-1)D)が最小となるようなNを求めれば良いです.そこで,X=A+(N-1)DとなるようなNが存在すると仮定してN=(X-A)/D+1を求めます.勿論そのようなNが存在しない事もあるので(X-A)/Dが割り切れない事があるので切り捨てしておきます.切り捨ての関係でNが最も最適なNか分からないためN-1,N,N+1についてA+(N-1)Dを求め,それとXの差の最小値を求めれば解になります.
X, A, D, N = map(int, input().split()) if D >= 0 and X <= A: print(A-X) elif D < 0 and X >= A: print(X-A) elif D >= 0 and X >= A + (N-1)*D: print(X-(A + (N-1)*D)) elif D < 0 and X <= A + (N-1)*D: print(A + (N-1)*D-X) else: n = (X-A)//D + 1 nm1 = n-1 np1 = n+1 print(min(abs(X - (A+(nm1-1)*D)), abs(X - (A+(n-1)*D)), abs(X - (A+(np1-1)*D))))
シェル・ワンライナー160本ノック week1 練習1.3.a~練習1.3.e
はじめに
私はプログラムはPythonしか書けず,CLIでのコマンド操作もcdやlsのような超基本的なコマンドしか使ってこなかったため,コマンドが使えなくて困ったという場面に出くわしたことはありませんが,なんとなく今まで引け目を感じていました.そんなときにこの本を見つけ,この機会にUnix系OSのシェル操作を習得しようと決意しました.
半年以内に習得とあるのでweek26位で完結できるように毎週7問程度取り組んでいこうと思います.最初の方はそれほど難しくないためそれ以上の問題数解くかも知れません.
環境はWindowsのWSLで解いていきます.
練習1.3.a
sedによる置換
sedコマンドで文字列を置換することが出来ます.
$ echo あいうえお | sed 's/あ/ア/' アいうえお
引数の一番目のsが文字の置換を行う宣言?で/a/bで文字列のaをbに置換出来ます.
&による再利用
$ echo あいうえお | sed 's/あい/&&&/' あいあいあいうえお
&で検索対象の文字を再利用できます.今回は&があいとなるので,&&&はあいあいあいとなります.
\による後方参照
$ echo あいうえお | sed -E 's/(あ)(い)(う)/\3\2\1/' ういあえお
文字列を()で囲む事で順番に番号が与えられます.それを\1\2と呼び出すことが出来ます.1-indexのようです.この()はあくまで文字に順番を与えるという役割しか与えてないっぽいため,
$ echo あいうえお | sed -E 's/(あ)(う)(お)/\3\2\1/' あいうえお
この出力は おいうえあ にはならずに あいうえお となります.あ が番号1,う が番号2,おが番号3として置換を行うわけではなく,あうお という文字列を探して置換しているためです.あいうえお には あうお という文字列は存在しないため,出力はそのままあいうえおとなります.
1.3.c
1.3.d
1.3.e
sort
三項演算子によって 条件?条件が真の時:偽の時 という記述が出来ます.これを使って偶数ならgusuに奇数ならkisuに文字を置き換えます.
$ seq 5|awk '{print $1%2 ? "kisu":"gusu"}' kisu gusu kisu gusu kisu
これをsortによってソートします.
$ seq 5|awk '{print $1%2 ? "kisu":"gusu"}'| sort gusu gusu kisu kisu kisu
uniq
uniqでユニークな要素,つまり重複を取り除いて出力します.
$ seq 5|awk '{print$1%2 ? "kisu":"gusu"}'| sort|uniq gusu kisu
更にオプションとして-cを付けるとその要素数を出力します.
$ seq 5|awk '{print$1%2 ? "kisu":"gusu"}'| sort|uniq -c 2 gusu 3 kisu
PyTorch実戦入門 第2章 演習問題 解答まとめ
1
a
必要な前処理は,第2章で行ったことと同じで,256×256にリサイズする事と,テンソルに変換する事です.
preprocess = transforms.Compose([transforms.Resize(256), transforms.ToTensor()]) img = Image.open("golden.png") img_t = preprocess(img)
b
入力したゴールデンレトリーバーの画像は以下になります.
出力結果は以下になります.
上のゴールデンレトリーバーはウマと認識されているのかシマ模様が出来ています.下のゴールデンレトリーバーはウマの学習データに,このような寝そべった体勢の画像が無かったからか耳など一部しかシマ模様になっていないことが分かります.
2
b
例えばこのリポジトリのプロジェクトがあります.
github.com
yoloとは物体検出を行うモデルであり,yolov5その最新のモデルになります.
Atcoder 灰diff埋め ARC131~ARC136 振り返り
ARCの灰埋め全て終わりました!次はAGCです.
ARC130 A - Erase by Value【AC】
始め,最大値を取り除いて表示するだけで良いだろうと思い提出しました.
N = int(input()) A = [int(i) for i in input().split()] max_a = max(A) ans = [] for a in A: if a != max_a: ans.append(str(a)) print(" ".join(ans))
しかし,これでWAが7個出てしまいました.原因は単純で,例えば2,1,3という数列だった場合,上のコードでは2,1となってしまいますが,正しくは1,3です.単純に最大値を取り除くだけでは行けないことが分かります.
この例からも分かる通り,取り除くべきは最大値ではなく,i
N = int(input()) A = [int(i) for i in input().split()] x = A[-1] for i in range(N-1): if A[i] > A[i+1]: x = A[i] break ans = [] for a in A: if a != x: ans.append(a) print(*ans)
Atcoder ABC254 振り返り
純粋に気付いたら夜9時過ぎてて泣く泣くバチャ参加でした……
A - Last Two Digits【AC】
インデックスにマイナスを付けると後ろから数える事が出来て便利です.
N = input() print(N[-2:])
B - Practical Computing【AC】
N<30なので,全ての要素で計算しても間に合います.
まず,[[0]+[1 for _ in range(i)] for i in range(N)]で答えのリストを作っておきます.j=0の時0と決まってるので,そのようにしています.また,j=iの時1と決まっているので,とりあえずj=0以外は1になるように設定します.
リストを作ったら,全てのi, jについて計算します.aijについて,ai-1, j-1を利用する必要があるので,ijは0から計算しなければ行けません.
N = int(input()) A = [[0]+[1 for _ in range(i)] for i in range(N)] for i in range(N): for j in range(i+1): if j == 0 or i == j: A[i][j] = 1 else: A[i][j] = A[i-1][j-1] + A[i-1][j] for a in A: print(" ".join(map(str, a)))
C - K Swap【AC】
K=2の時,どのように入れ替えても1番目の値と2番目の値が入れ替わることはありません.K=2なら入れ替わるのは1, 3, 5, 7...番目の値が入れ替わります.入れ替えは何度も出来るので1, 3, 5, 7...番目の値では完全にソートできます.また,2 ,4, 6, 8...番目の値も同様にソートできます.これを合わせたときに,正しくソートされているか判別できれば良いです.
pythonでは,[a:b:c]でa番目からb番目までc飛ばしでリストの値を取り出す事が出来ます.よって,cをKとすればKおきの値を取ることが出来ます.このリストに対してソートし,元のリストに値を書き換えます.これをK回繰り返し,全ての値をまとめてソートしたときと値が同じならソート可能,そうでないならソート不可能となります.
N, K =map(int, input().split()) A = [int(i) for i in input().split()] sorted_A = sorted(A) for i in range(K): AA = sorted(A[i::K]) for j, a in enumerate(AA): A[K*j + i] = a if sorted_A == A: print("Yes") else: print("No")
Atcoder 灰diff埋め ARC116~ARC130 振り返り
ABCのdiffとARCのdiff全然難易度が違う気がする……
ARC130 A - Remove One Character【解説AC】
全てのSiの文字列を生成し,その個数を記録しておいて,nCrで求める手法はTLEになります.
SiとSjが等しいと言うことに対し,他にどのような性質があるかを考える必要があります.i番目の文字が削除されると言うことは,i+1文字目移行の全ての文字が,i文字目に移動するという性質を利用します.SiとSjが等しいならば,i番目からj番目までの文字は全て等しいと言うことになります.
これを利用して,連続して等しい文字の数を記録し,それを足し合わせることで答えを出すことが出来ます.
import math N = int(input()) S = list(input()) n = 0 ans = 0 for j in range(1, N): if S[j] == S[j-1]: n += 1 else: n = 0 ans += n print(ans)