atcoder abc_124 を解いてみた(python3)
-A. [AC] Buttons
問題ページ【A - Buttons】
私のコンテスト中の解法
# -*- coding: utf-8 -*- A,B = map(int,input().split() ) sum = 0 for i in range(2): if A >= B : sum = sum + A A = A - 1 else: sum = sum + B B = B - 1 print(sum)
実行時間：17 ms メモリ：2940 KB
forループを二回まわしてAとBを比較する。
大きい方を合計に足していく。
chokudaiさんの解説の解法
# -*- coding: utf-8 -*- A,B = map(int,input().split()) sum = 0 sum = max(sum, A + A -1) sum = max(sum, A + B) sum = max(sum, B + B -1) print(sum)
実行時間：17 ms メモリ：2940 KB
ボタンは二回押すので、AとBの組み合わせは3つだけ。
その中からmaxを選ぶ。
-B. [AC] Great Ocean View
問題ページ【B - Great Ocean View】
私のコンテスト中の解法（解説も同じような解法）
# -*- coding: utf-8 -*- N = int(input()) lst = list(map(int,input().split())) max = 0 sum = 0 for i in range(N): if max <= lst[i]: sum = sum + 1 max = lst[i] print(sum)
実行時間：17 ms メモリ：2940 KB
山の数分forループをまわして、西から山を調べていく。
高い山をmaxに代入して、maxを更新していくたびにsumを増やす。
-C. [AC] Coloring Colorfully
問題ページ【C - Coloring Colorfully】
私のコンテスト中の解法
# -*- coding: utf-8 -*- *s, = map(int,input()) if len(s)%2 == 0: s0 = [0,1] *(len(s)//2) s1 = [1,0] *(len(s)//2) else: s0 = [0,1] *(len(s)//2) s0.append(0) s1 = [1,0] *(len(s)//2) s1.append(1) sum0 = 0 sum1 = 0 for i in range(len(s)): if s0[i] != s[i]: sum0 = sum0 +1 if s1[i] != s[i]: sum1 = sum1 +1 ans = min(sum0, sum1) print(ans)
実行時間：69 ms メモリ：5620 KB
Sと同じ長さのタイル列を、白黒白・・・と黒白黒・・・の2つ生成する。
Sとその2つのタイル列を比較して、違うとことがあったらsumを足していく。
最後に違いが少なかった方を出力。
解説の解法
# -*- coding: utf-8 -*- *s, = map(int,input()) # 初期値は大きい値 ans = len(s) # iは最初に使う色（0 or 1） for i in range(2): # 変える必要があるタイル数 cnt = 0 for j in range(len(s)): if (j % 2 == 0) ^ (s[j] == i): cnt = cnt +1 ans = min(ans, cnt) print(ans)
実行時間：82 ms メモリ：3956 KB
はじめが0だったら偶数番目は0になり、
はじめが1だったら偶数番目は1になる。
＾（XOR）を使っている。
偶数番目が i のとき、あっているのでcntはそのまま。
偶数番目が i ではないとき、変える必要があるのでcntは増える。←
奇数番目が i のとき、変える必要があるのでcntは増える。←
奇数番目が i ではないとき、あっているのでcntはそのまま。
j % 2 == 0 | s[j] == i | 0 or 1 =============================== True | True | 0 True | False | 1 ← False | True | 1 ← False | False | 0
atcoder abc_123 を解いてみた(python3)
今回のABCはいつもより難しく感じました。
chokudaiさんの解説を見て納得することが多かったので、
この記事は私の回答ではなくすべて解説を元に書きます。
-A.Five Antennas
問題ページ【A - Five Antennas】
# -*- coding: utf-8 -*- L = [] for i in range(5): a = int(input()) L.append(a) K = int(input()) if L[4]-L[0]<=K: ans = 'Yay!' else: ans = ':(' print(ans)
5つのアンテナ間の距離が一箇所でもK未満ならば ':(' を出力する。
つまり、すべてのアンテナ間の距離を調べなくても、
最も遠いアンテナ間 (A, E) のみを調べれば良い。
最初私はすべてのアンテナ間を調べた。
-B.Five Dishes
問題ページ【B - Five Dishes】
# -*- coding: utf-8 -*- #注文してから料理が届くまでの時間 Time = [] for i in range(5): a = int(input()) Time.append(a) #注文してから次の注文が出来るまでの時間 nextTime = list(map(lambda x: (x+9)//10*10, Time)) #bestに最短時間を代入 best = 10**5 sum = 0 for i in range(5): for j in range(5): if i == j: sum = sum + Time[j] else: sum = sum + nextTime[j] best = min(best, sum) sum = 0 print(best)
Time : 注文してから料理が届くまでの時間
nextTime : 注文してから次の注文が出来るまでの時間
#注文してから次の注文が出来るまでの時間 nextTime = list(map(lambda x: (x+9)//10*10, Time))
ここで何してるかの説明
・式について
ans = (x+9)//10*10
#例 ans = (20+9)//10*10 print(ans) #20 ans = (23+9)//10*10 print(ans) #30
ある数字の一の位が 0 のとき、十の位はそのままで、
一の位が 1 ~ 9 のとき、十の位は 1 増える。
つまり切り上げしてる。
・lambda関数【Pythonの無名関数（ラムダ式、lambda）の使い方 | note.nkmk.me】
（無名関数とも言う）
new = lambda 引数 : 式
deff を使わなくても簡単な new という関数が出来る。
・map関数【【Pythonステップアップ！】高階関数mapの便利な使い方 | 侍エンジニア塾ブログ（Samurai Blog） - プログラミング入門者向けサイト】
map(関数, シーケンス)
シーケンスとは複数の要素をもったオブジェクト。
シーケンスの各要素を、受け取った関数に渡して実行してくれる。
この一行で、Time の要素を自分で作った関数に渡して、
切り上げした値をリストにしてる。
二重forループで、一番最後に注文する料理を変えながら合計時間を出して
best に最小値が出るたびに代入していく。
-C.Five Transportations
問題ページ【C - Five Transportations】
# -*- coding: utf-8 -*- N = int(input()) L = [] for i in range(5): a = int(input()) L.append(a) Lmin = min(L) ans = (N+Lmin-1)//Lmin + 4 print(ans)
こういう問題を「ボトルネック」というらしい。
いろんな交通機関があるけれど、結局一番乗車人数が少ない乗り物に全体の能力を支配される。
Lmin に最小乗車人数を入れる。
次の一行で、切り上げを使って移動時間を計算している。
ans = (N+Lmin-1)//Lmin + 4 (N+Lmin-1)//Lmin #すべての人が都市1からいなくなる時間 + 4 #都市2に残ってた人が都市6につく時間
-D.Cake 123
問題ページ【D - Cake 123】
chokudaiさんはC++で実装して【AC】でした。
そのアルゴリズムをpythonで実装すると【TEL】になりました。
今の私にはこれ以上直せないので、C++も覚えようかと思います。
# -*- coding: utf-8 -*- X, Y, Z, K = map(int,input().split(' ')) *a, = map(int,input().split(' ')) *b, = map(int,input().split(' ')) *c, = map(int,input().split(' ')) a.sort(reverse=True) b.sort(reverse=True) c.sort(reverse=True) abc = [] for i in range(len(a)): if i > K+1: break for j in range(len(b)): if i+j > K+1: break for k in range(len(c)): if i+j+k > K+1: break abc.append(a[i]+b[j]+c[k]) abc.sort(reverse=True) for i in range(K): print(abc[i])
atcoder abc_122【We Like AGC】D問題 を解いてみた(python3)
今回初めてD問題を解いたので、記念に記事を残したくなりました。
この記事は私のような初心者が、初心者に向けて考え方を発信します。
拙い文章ではありますが誰かの参考になったら幸いです。
chokudauさんの解説（C++）をpython3で書き直しています。
-問題文
問題ページ【D - We Like AGC】
整数 N が与えられます。次の条件を満たす長さ N の文字列の数を 10^9+7 で割った余りを求めてください。
- A, C, G, T 以外の文字を含まない。
- AGC を部分文字列として含まない。
- 隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。
【注記】
文字列 T の部分文字列とは、T の先頭と末尾から 0 文字以上を取り去って得られる文字列です。
例えば、' ATCODER ' の部分文字列には' TCO ', ' AT ',' CODER ',' ATCODER ', (空文字列) が含まれ、' AC 'は含まれません。
【制約】3≤N≤100
-問題文の意味
問題文の意味が難しかったのですが、解説してくださっていたのでここでもまとめてみます。
条件文 2 について
例えば長さ 6 の文字列を作成したとき、
T A G C A C
という文字列には ' A G C ' が含まれているので条件を満たす文字列の数には含まれません。
T T G C A C
これならOK。
ここで、
A G C T ↓ ↓ ↓ ↓ 0 1 2 3
と置き換えさせてもらいます。つまり ' A G C ' → ' 0 1 2 ' と書き表します。
さて、条件文 3 を見るとちょっと難しいことが書いてあります。
どういう事かというと「作成した文字列の一箇所をswapして ' 0 1 2 ' が出来たら条件違反」ということ。
例を見たほうがわかりやすいですね。sawpして ' 0 1 2 ' が出来るということは、
# ? は 0 1 2 3 のどれか 1 0 2 --swap→ 0 1 2 0 2 1 --swap→ 0 1 2 0 ? 1 2 --swap→ ? 0 1 2 0 1 ? 2 --swap→ 0 1 2 ?
ということ。つまり作成した文字列の中に
0 1 2 1 0 2 0 2 1 0 ? 1 2 0 1 ? 2
が入っていると条件違反ということになります。
-アルゴリズム
条件文の意味が理解できたのでアルゴリズムについて考えていきます。
ここで条件を満たしている文字列を S と置きます。
そして S の後ろに新しい文字 a を足して新しい文字列を作ります。
例えば S = . . . . 3 0 1 とする。
後ろに a を足して出来る文字列を nextS とすると
a = 0 nextS = S + a = . . . . 3 0 1 + 0 =. . . . 3 0 1 0 a = 1 nextS = . . . . 3 0 1 1 a = 2 nextS = . . . . 3 0 1 2 ← a = 3 nextS = . . . . 3 0 1 3
4つの nextS が出来ました。ですが、 a = 2 の nextS の最後 3 文字に注目してください。
条件違反となる文字列 ' 0 1 2 ' が出来てしまいました。
つまり、新しい文字列 nextS を作成する際は、 S の最後の 3 文字に注目して条件違反にならないか確認しながら作りましょう。
それより前の文字列は条件を満たしていれば何でもいいです。
このように条件を満たす文字列を増やして一つ一つ保存して、入力 N で与えられた文字数の文字列の個数を数えれたば答えが出ます。
これはすごく時間がかかりそう・・・。
ここで DP（動的計画法）の出番です。
-DP（動的計画法）を使ってみる
DPについて初心者に優しく解説してくださってる記事があります。下からどうぞ。
qiita.com
- DP 配列全体を「DP の種類に応じた初期値」で初期化
- 初期条件を入力
- ループを回す
- テーブルから解を得て出力
これに従って今回の問題をDPに落とし込んで考えていきます。
先程の章で条件を満たした文字列で重要な部分は、最後の 3 文字と文字列長ということが分かりました。
今回注目するべき変数は 4 つあるので 4 次元配列をDP配列とします。
そして条件を満たしているとき 1 、条件を違反しているとき 0 が代入されるようにします。
len = 文字列長 c3 = 最後から 3 番めの文字 c2 = 最後から 2 番めの文字 c1 = 最後から 1 番めの文字 dp[len][c3][c2][c1]
あとはforループをたくさん回します。
「ある文字列」 に a を足したときの最後 3 文字が条件を満たしている場合、
「ある文字列」 から 「ある文字列 + a」 へ 1 or 0 が引き継がれます。
こうしてDP配列に値が代入された、DPテーブルができます。
あとはDPテーブルから文字列長が N のときの値を足していくと、条件を満たしている文字列数が得られるということです。
-プログラム
# -*- coding: utf-8 -*- N = int(input()) # A C G T を # 0 1 2 3 と置く dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(101)] dp[0][3][3][3] = 1 mod = 10**9+7 #文字列の文字数 for len in range(N): #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): #新しく追加する文字 for a in range(4): if c2 == 0 and c1 == 1 and a == 2 : #012 continue if c2 == 1 and c1 == 0 and a == 2 : #102 continue if c2 == 0 and c1 == 2 and a == 1 : #021 continue if c3 == 0 and c1 == 1 and a == 2 : #0?12 continue if c3 == 0 and c2 == 1 and a == 2 : #01?2 continue dp[len + 1][c2][c1][a] += dp[len][c3][c2][c1] ans = 0 #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): ans += dp[N][c3][c2][c1] ans %= mod print(ans)
分解してみますね。
dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(101)]
今回は 0 で初期化します。
4 次元配列のみため、ものすげえです。
dp[0][3][3][3] = 1
長さ0、最後から 3 文字目 ' 3 ' 、最後から 2 文字目 ' 3 ' 、最後から 1 文字目 ' 3 ' は、
条件を満たしているということにします。
こうしておくと、 a を足したときに 長さ 1 、 文字列 = 3 3 3 a となる。
つまり、3 3 3 の部分は無視できて a から長さをカウント出来る。
（ややこしくなってすみません）
#文字列の文字数 for len in range(N): #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4):
ここで 5 重ループのうち最初の4 重ループで、 dp[0][0][0][0] ~ dp[N][3][3][3] まで虱潰しに調べていきます。
for a in range(4): if c2 == 0 and c1 == 1 and a == 2 : #012 continue if c2 == 1 and c1 == 0 and a == 2 : #102 continue if c2 == 0 and c1 == 2 and a == 1 : #021 continue if c3 == 0 and c1 == 1 and a == 2 : #0?12 continue if c3 == 0 and c2 == 1 and a == 2 : #01?2 continue dp[len + 1][c2][c1][a] += dp[len][c3][c2][c1]
最後のループで文字列の最後につける a を回します。
中では「ある文字列」に a を足したときに条件違反になるかを調べています。
条件に引っかかると、「ある文字列 + a」 は0のままになり、条件を抜けると「ある文字列」の値を引き継ぎます。
ans = 0 #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): ans += dp[N][c3][c2][c1] ans %= mod
ここの 3 重ループで先程作ったDPテーブルから、文字列長が N のときの値をすべて抜き出して足してきます。
ans %= mod
オーバーフローする可能性があるので、毎回忘れずに10^9+7で割っておきます。
-最後に
ここまで見てくださって、ありがとうございました。
間違っていたり、変えたほうがいいところがあったらどうか教えてください。
つよつよの人はこれを10分くらいで実装するんですよね、すごいです。
私もいつかスラスラ解けるように精進します。
atcoder abc_122 を解いてみた(python3)
-A. [AC] Double Helix
問題ページ【A - Double Helix】
# -*- coding: utf-8 -*- b = input() if b=='A': print('T') elif b == 'T': print('A') elif b == 'C': print('G') else: print('C')
塩基が4つしかないので4パターンの条件分岐で通せた。
パターンが多い時は配列を使うといいらしい(今度書く)
-B. [AC] ATCoder
問題ページ【B - ATCoder】
# -*- coding: utf-8 -*- s = input() a = 0 max = 0 for i in range(len(s)): if s[i] == 'A' or s[i] == 'T' or s[i] == 'C' or s[i] == 'G': a = a+1 else: a = 0 if max < a: max = a print(max)
入力した配列を全探索し、'A','T','C','G'の場合aを1増やす。
そうではなかった場合はa=0に初期化する。
そしてaが最大値を更新する度に、maxにaを代入する。
-C. [AC] GeT AC
問題ページ【C - GeT AC】
chokudauさんの解説（C++）をpython3で書き直した。
# -*- coding: utf-8 -*- #入力 n, q = map(int,input().split()) s = input() l = [0]*q r = [0]*q for i in range(q): l[i], r[i] = map(int,input().split()) #累積和を求める sum = [0]*(n+1) for i in range(1,n): if s[i-1] == 'A' and s[i] =='C': sum[i+1] = sum[i] + 1 else: sum[i+1] = sum[i] #指定された範囲の中のACの数を出力 for i in range(q): ans = sum[r[i]]-sum[l[i]] print(ans)
累積和を格納する配列sum（長さ = n+1）を作る。
A C が並んだときにsumに1足される。
#累積和を求める sum = [0]*(n+1) for i in range(1,n): sum[i+1] = sum[i] if s[i-1] == 'A' and s[i] =='C': sum[i+1] = sum[i+1] + 1
↑累積和の求め方の記述は
この書き方のほうがシンプル by chokudaiさん
最初に自分で解いてLETだったやつ。
# -*- coding: utf-8 -*- n, q = map(int,input().split()) s = input() for i in range(q): l, r = map(int,input().split()) a = 0 for j in range(l-1,r-1): if s[j] == 'A' and s[j+1] =='C': a = a+1 print(a)
累積和というのを勉強しないとACにはならなそう。
-D. [AC] We Like AGC
問題ページ【D - We Like AGC】
chokudauさんの解説（C++）をpython3で書き直した。
# -*- coding: utf-8 -*- N = int(input()) # A C G T を # 0 1 2 3 と置く dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(101)] dp[0][3][3][3] = 1 mod = 10**9+7 #文字列の文字数 for len in range(N): #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): #新しく追加する文字 for a in range(4): if c2 == 0 and c1 == 1 and a == 2 : continue #012 if c2 == 1 and c1 == 0 and a == 2 : continue #102 if c2 == 0 and c1 == 2 and a == 1 : continue #021 if c3 == 0 and c1 == 1 and a == 2 : continue #0?12 if c3 == 0 and c2 == 1 and a == 2 : continue #01?2 dp[len + 1][c2][c1][a] += dp[len][c3][c2][c1] ans = 0 #最後から1文字目の文字 for c1 in range(4): #最後から2文字目の文字 for c2 in range(4): #最後から3文字目の文字 for c3 in range(4): ans += dp[N][c3][c2][c1] print(ans % mod)
詳しい解説ページ
naolllab.hatenablog.com
今回のコンテスト後のレート
javaで「Hallo world !!」を出力(VScode)
突然Javaを使用する必要が出てきたので、自分用のメモ&困ってる人用に手順やエラー解消法を残していく。
-VScode に Java の拡張機能追加
左端にある「拡張機能」ボタンをクリック
1.上のウィンドウに「java」と入力
2.Java Extension Packをクリック
3.インストール（画像はアンインストールになってる）
拡張機能追加完了
atcoder abc_121 を解いてみた(python3)
-A. [AC]White Cells
# -*- coding: utf-8 -*- H, W = map(int, input().split()) h, w = map(int, input().split()) print(H*W-h*W-w*(H-h))
-B. [AC]Can you solve this?
# -*- coding: utf-8 -*- n, m, c = map(int, input().split()) lst = [] for i in range(n+1): lst_1 = list(map(int, input().split())) lst.append(lst_1) a=0 b=0 for j in range(n): for i in range(m): a = a + lst[0][i]*lst[j+1][i] if a+c>0: b=b+1 a=0 print(b)
for文内でAとBのソースコードをリストとして読み取り、さらにリストに追加していく。
次のfor文内でBのソースコード(lst[0])の要素に、Aのソースコード(lst[1~n+1])の要素をそれぞれ掛けあわせる。
-C. Energy Drink Collector
-D. XOR World
今回のコンテスト後のレート
atcoder abc_120 を解いてみた(python3)
-A. [AC]Favorite Sound
# -*- coding: utf-8 -*- a, b, c = map(int,input().split()) if b//a >= c: print(c) else: print(b//a)
b/a で計算結果、b%a で余り、b//a で商を取得。
-B. [AC]K-th Common Divisor
# -*- coding: utf-8 -*- a, b, k = map(int,input().split()) lst = [] for i in range(1,101): if a%i == 0 and b%i == 0: lst.append(i) print(lst[-k])
range(1,101) は、i に 1~100 まで代入する。
公約数リストを作成して、append で余り0のとき追加。
lst[-k]で、後ろからk番目を出力。
-C. Unification
-D. Decayed Bridges
今回のコンテスト後のレート
