競プロ典型90問 ★2問題コード解説[2]
はじめに
最近はかなり冷え込みが厳しくなってきましたね。最近は椅子に座るときも足に毛布を巻いています。椅子に座りながらこたつのような温かさと安心感があってとてもよいですね。
今回は競プロ典型90問の★2問題を2問解説していきたいと思います。 競プロ典型90問については、以下のリンクからご覧ください。
022 - Cubic Cake（★2）
ケーキに切れ込みを入れてすべてのピースを立方体にするためには、何回切ればよいか、という問題です。
この問題を解くカギは、
各辺に対して等分する必要がある
ということです。
ケーキに切れ込みを入れるときは、スパッとすべて切断する必要がある（一部だけ切れ込みを入れることはできない）ので、切断後の1辺の長さは、全ての辺の約数である必要があります。
また、操作を行う最小回数を求める必要があるので、できるだけ大きく切る必要があります。
それらの条件を満たすのは最大公約数なので、a, b, cの最大公約数が切断する1辺の長さとなります。切断回数は切断後のピースの数 - 1で求めることが出来ます。
Pythonだと、mathライブラリをインポートしてmath.gcd(a, b)で簡単に最大公約数を求めることが出来ます。
import math a, b, c = map(int, input().split(" ")) #1辺の長さ length = math.gcd(math.gcd(a, b), c) output = (a//length-1)+(b//length-1)+(c//length-1) print(output)
024 - Select +／- One（★2）
2つの数列が与えられ、K回の +1か -1でそれらを一致させられるかを判定する問題です。この問題を解くカギは、
+1 と -1を1回ずつの2回の操作を行えば、今の状態をキープできる
ということです。
つまり、添え字が同じ数列の数値の差を合計して、それとKとの差が2の倍数であれば、K回の操作で数列を一致させることが出来るということです。
n, k= map(int, input().split(" ")) a_list = list(map(int, input().split(" "))) b_list = list(map(int, input().split(" "))) sum_diff = 0 for i in range(n): sum_diff += abs(a_list[i] - b_list[i]) if (k - sum_diff) % 2 == 0 and (k - sum_diff) >= 0: print("Yes") else: print("No")
おわりに
今回は典型90問の★2問題の2問を解説していきました。予定では前回の続きのABC280のD問題を解説しようとしたのですが…アルゴリズムを理解したつもりになってもACにならずで…。まだ少し時間がかかりそうです。
次回のABCまでには何とか理解して記事を書きたいですね。
Atcoder Beginner Contest 280 レポート
はじめに
本日、Atcoder Beginner Contestに初参加しました！！
結論から申し上げますと、A, B, Cの３問正解で３完といったところでした。
D問題の素因数分解を使うことはわかりましたが、それから先が出来なかった…。解説を読み込んでこのブログでも解説できるように頑張ります…。
では今回は私が解けた問題の解説を行います。
A - Pawn on a Grid
問題文
解法
こちらの問題は読み込んだ文字列の中に #がいくつ入っているかカウントする、といったものです。
list(文字列)で文字列を1文字ずつのリストに直して、for文で検索しています。
ただ、A問題はfor文を使わなくても解けるらしいので、別解はたくさんありそうです。
h, w = map(int, input().split(" "))
cnt = 0
for i in range(h):
s = input()
s = list(s)
cnt += s.count("#")
print(cnt)
B - Inverse Prefix Sum
問題文
解法
こちらの問題は、入力された数列の要素と次の要素の差を要素とした新たな数列を作ればOKです。
n = int(input())
s_list = list(map(int, input().split(" ")))
ans = []
for i in range(len(s_list)):
if i == 0:
ans.append(s_list[0])
else:
ans.append(s_list[i] - s_list[i-1])
print(" ".join(map(str, ans)))
C - Extra Character
問題文
解法
2つの文字列を一致させるために、どこに文字を挿入するかという問題です。
for ループの中で２つの文字列の各要素を比較して、異なればそこに文字を挿入するべきなので、そのインデックスを出力します。
ただ、この実装だと一番最後に挿入する場合がカバーできないので、flagで判断して最後に挿入しています。
s = input()
t = input()
s_list = list(s)
t_list = list(t)
flag = False
for i in range(len(s)):
if s_list[i] != t_list[i]:
print(i+1)
flag = True
break
if flag == False:
print(len(t))
おわりに
ABCに初参加して思ったのが、「100分は意外と早く過ぎる」ということですね。コードを早く正確に書く時間はもちろんのこと、使うアルゴリズムの判断や数学の能力など自分に足りないものが浮き彫りになりました。
できる限り毎回参加してレートが上がるよう頑張っていきます。
目指せ茶コーダー！！
競プロ典型90問 ★2問題コード解説[1]
記事の目的
Atcoderを始めまして、前回で初心者用の教材である「Atcoder Beginner Selection」を解きました。
次に何をしようかと思案してAtcoderの常設コンテストを覗いてみると「競プロ典型90問」というのが目につきました。
詳しいことは上記のリンクから見ていただくとして、製作者のE869120様の他にも様々な方が解説ブログを書いてくださっていて、非常に勉強しやすいです。
自分はPythonを使っていますので、こちらの方のGithubを参考にさせていただきました。
競プロ典型90問は★1から★7で構成されていて、数字が大きくなるほど難しくなっていきます。★2が「Atcoder Beginners Contest」の300点問題レベルだといわれていますので、まずは★2問題をすべて解けるように頑張っていきたいと思います。
004 - Cross Sum（★2）
問題文
要約すると、与えられた行列のすべての要素に対して、その要素を含む行と列にある要素の合計を求める、という問題ですね。
以下が解法になります。
h, w = map(int, input().split(" "))
a_list = []
for i in range(h):
a_row = list(map(int, input().split(" ")))
a_list.append(a_row)
row_sum = [sum(i) for i in a_list]
column_sum = []
for i in range(len(a_list[0])):
sum = 0
for j in range(len(a_list)):
sum += a_list[j][i]
column_sum.append(sum)
sum = 0
output_list = []
output_tmp = []
for i in range(len(row_sum)):
for j in range(len(column_sum)):
val = row_sum[i] + column_sum[j]
val = val - a_list[i][j]
output_tmp.append(val)
output_list.append(output_tmp)
print(" ".join(map(str, output_tmp)))
output_tmp = []
かなりコードがごちゃついていますが、まずは与えられた行列について、「行の合計」と「列の合計」を前計算しています。
その要素が含まれる縦横の要素の合計は、
「行の合計」＋「列の合計」ー「その要素の値」
となります。「行の合計」にも「列の合計」にも「その要素の値」が含まれているので、１つ分を引く必要があります。
010 - Score Sum Queries
問題文
こちらの問題、N人分の名簿があって、Q個の質問がありますので、単純に２重ループかと思いきや、２重ループで解こうとするとTLE（タイムアウト）となります。
ですのでこちらの問題、各クラスの累積和を事前に計算します！
n = int(input())
c = [0 for i in range(n)]
p = [0 for i in range(n)]
for i in range(n):
c[i], p[i] = map(int, input().split(" "))
score_sum_A = [0]
score_sum_B = [0]
nowA = 0
nowB = 0
for i in range(n):
if c[i] == 1:
nowA += p[i]
else:
nowB += p[i]
score_sum_A.append(nowA)
score_sum_B.append(nowB)
q = int(input())
for i in range(q):
quest1, quest2 = map(int, input().split(" "))
print(score_sum_A[quest2] - score_sum_A[quest1-1], score_sum_B[quest2] - score_sum_B[quest1-1])
始めのforループでは、学籍番号における各クラスの点数の累積和を保存しています。つまり以下の表のようになります。
こうして頭からの累積和を事前に算出しておくことによって、LからRまでの累積和も「Rまでの累積和」ー「L-1までの累積和」で計算することが出来ます。
おわりに
今回は競プロ典型90問の★2問題を2問解いてみました。計算量で躓くことも多く、競プロっぽくなってきたなと思います。
明日はABCに初参加するので、参加した感想や問題の解説（解けたら）などをまとめていけたらと思います。
Atcoder Beginners Selection コード解説[3]
記事の目的
Atcoderの初心者向けの課題である「Atcoder Beginners Selection」のC問題のコードを解説していきます。より良い解法など、コメントお待ちしております。
ABC085C - Otoshidama
問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
うらやまし～！！！！
お札の枚数が指定されていて、金額がその枚数で実現できるかどうか判定するといった問題です。
はじめはそれぞれのお札の枚数について３重ループを組んでみましたが、TLE（タイムアウト）してしまいました。
この問題は３重ループを２重ループにすることが出来ます。
この連立方程式が成り立つとすると、変数を一つ消すことが出来ます。
それを踏まえて、実行したコードがこちらになります。
n, y = map(int, input().split(" ")) flag = False for i in range(n+1): for j in range(n+1): if i + j <= n: k = n - (i + j) if 10000*i + 5000*j +1000*k == y: print("{} {} {}".format(i, j, k)) flag = True break else: continue break if flag == False: print("{} {} {}".format(-1, -1, -1))
変数が1つ消えたので、2重ループで解を見つけ、見つけ次第処理を打ち切っています。また、処理終了まで解が見つからなかった場合は(-1, -1, -1)が出力されるようになっています。
ABC049C - 白昼夢
問題文
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
T の末尾に dream, dreamer, erase, eraser のいずれかを追加する。
一見簡単そうですが、文字列を前から検索してdreamerという文字が出てきた場合、それがdreamerなのかdream + eraseなのかがわかりません。
そこでこの場合は、文字列を後ろから探索します。
s = input()
s_reversed = s[::-1]
tmp_s = s_reversed
while len(tmp_s) > 0:
if tmp_s[0:5] == "maerd":
tmp_s = tmp_s[5:]
elif tmp_s[0:5] == "esare":
tmp_s = tmp_s[5:]
elif tmp_s[0:6] == "resare":
tmp_s = tmp_s[6:]
elif tmp_s[0:7] == "remaerd":
tmp_s = tmp_s[7:]
else:
print("NO")
break
if len(tmp_s) == 0:
print("YES")
私の実装では、後ろから探索する代わりに、文字列を反転させて、前から探索しています。もちろん見つけ出す文字もdreamがmaerdのように反転することになりますが、探索する文字が部分的に一致するというようなことが起こりません。
また、Pythonでは文字列の反転が、s[::-1]で簡単にできます。
ABC086C - Traveling
問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 tiに 点 (xi,yi) を訪れる予定です。 AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。
AtCoDeer君！AtCoDeer君じゃないか！！
AtCoDeer君が座標平面上を移動して、ある時刻にある点に存在できるかを判定するという問題です。その場にとどまることはできませんが、時刻を2つ使って行ったり来たりすることはできます。
つまり、自分の今いる点から目的の点まで、最短何時刻で行けるかを求めたうえで、指定された時刻と最短時刻の差が偶数なら実行可能といえます。
s = input()
t_list = []
x_list = []
y_list = []
for i in range(int(s)):
t, x, y = map(int, input().split(" "))
t_list.append(t)
x_list.append(x)
y_list.append(y)
now_time = 0
place_x = 0
place_y = 0
flag = True
for i in range(len(t_list)):
t = t_list[i] - now_time
dis_x = abs(x_list[i] - place_x)
dis_y = abs(y_list[i] - place_y)
if dis_x + dis_y <= t and (t- dis_x - dis_y) % 2 == 0:
place_x = x_list[i]
place_y = y_list[i]
now_time = t_list[i]
else:
flag = False
if flag == True:
print("Yes")
else:
print("No")
今いる場所から指定された場所まで向かうための、最短時刻は以下の図のように算出できます。
おわりに
今回はABCのC問題について解説しました。これでABCは終了しましたので、次は競プロ典型90にチャレンジしてみようと思います。
Atcoder Beginners Selection コード解説[2]
記事の目的
Atcoderの初心者向けの課題である「Atcoder Beginners Selection」のB問題のコードを解説していきます。 より良い解法など、コメントお待ちしております。
ABC081B - Shift only
問題文
黒板に N 個の正の整数 A1, ..., AN が書かれています． すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます． 黒板に書かれている整数すべてを，2 で割ったものに置き換える． すぬけ君は最大で何回操作を行うことができるかを求めてください．
つまり与えられた整数すべてが偶数なら、それらを２で割るのを繰り返していき、それが何回までできるか、ということですね。
n = int(input()) list_a = input().split(" ") int_list_a = list(map(int, list_a)) cnt = 0 flag = True while flag == True: for i in range(len(int_list_a)): if int_list_a[i] % 2 != 0: flag = False else: int_list_a[i] = int_list_a[i] / 2 if flag == True: cnt += 1 print(cnt)
コードはこうなりました。（自分でも正直もっと冴えたやり方がありそうだと感じてる…） まずすべての整数に対して2で割れるかどうかの判定をして、可能であれば２で割った後にその回数をカウントしています。
ABC087B - Coins
問題文
あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。 同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。 各効果の組み合わせを全探索して、条件に一致した回数をカウントしました。今回は効果の種類が３種類なので３重ループになりましたが、テストケースによっては計算量の関係でタイムアウトする可能性もありますね…。
a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0
for i in range(a+1):
for j in range(b+1):
for k in range(c+1):
if x == 500*i + 100*j + 50*k:
cnt += 1
print(cnt)
コードはシンプルに書けました。
ABC083B - Some Sums
問題文
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。
1以上N以下のすべての整数について、各桁の和を計算して、それがA以上B以下であるものの個数をカウントする、という流れで進めていきます。
n, a, b = map(int, input().split(" "))
cnt = 0
for i in range(1, n+1):
i_list = [int(a) for a in str(i)]
if sum(i_list) >= a and sum(i_list) <= b:
cnt += i
print(cnt)
list()メソッドで文字列を簡単に分割できるので、pythonですっきり実装できましたね。
ABC088B - Card Game for Two
問題文
N 枚のカードがあります. i 枚目のカードには, aiという数が書かれています. Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります. 2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
「最適な戦略」というのが難しく聞こえますが、要は数字の大きいカードを交互に取っていくだけです。
n = int(input())
a_list = list(map(int, input().split(" ")))
now_turn = "Alice"
alice_point = 0
bob_point = 0
while True:
if max(a_list) == -1:
break
if now_turn == "Alice":
alice_point += max(a_list)
a_list[a_list.index(max(a_list))] = -1
now_turn = "Bob"
elif now_turn == "Bob":
bob_point += max(a_list)
a_list[a_list.index(max(a_list))] = -1
now_turn = "Alice"
print(alice_point - bob_point)
交互にプレイヤーのターンを入れ替えて、リスト内の最も大きい数字を自分のポイントに加算しています。
ABC085B - Kagami Mochi
問題文
X 段重ねの鏡餅 (X≥1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。 ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は di センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。
ダックスフンドのルンルンが餅を積み重ねて鏡餅を作る、というよくわからない設定ですが、入力から重複している値を除くだけで鏡餅の最大重ね数がわかります。
n = int(input())
d = []
for i in range(n):
d.append(int(input()))
d = list(set(d))
d.sort()
print(len(d))
pythonはset()メソッドで数学の集合を扱えるため、自動で重複を取り除いてくれます。sort()してるのは、下から餅を大きい順に重ねるためですが、今回は最大の段数だけが知りたいので、必要なかったですね。
終わりに
今回はABSのB問題を解説していきました。自分のコードに納得できない箇所がいくつかあったので、要勉強ですね。 次回はC問題を解説しようと思います。
Atcoder Beginners Selection コード解説[1]
記事の目的
初投稿です。
Atcoderを始めた人がまず最初に取り組む課題である「Atcoder Beginners Selection」を解き終えたのでまとめます。（正直n番煎じですが…）
ここをこうするとより良いよ！！みたいなコメントはいつでも大歓迎です！
Atcoder Bigenners Selectionって？
プログラミングサイトAtcoderが提供する、いわば初心者向けの教材です。
主要な言語なら基本的になんでも使えるので、登録して一番初めにやってみましょう。プログラミングの勉強を始めたての人でも簡単に解けるA問題から、解くのに慣れが必要なB問題、数学的な考え方が必要なC問題の良問がピックアップされています。
参加は上の画像の左上からできます。
本記事ではA問題を見ていきましょう。なお、A問題は3問ありますが、「PracticeA - Welcome to AtCoder」は割愛します。また、実装はPythonで行っています。
ABC0086A - Product
問題文
シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。偶数ならEven、奇数ならOddと出力してください。
いわゆるFizzBuzz問題ってやつですね。問題の解法よりAtCoDeerくんの方が気になるかもしれません…。AtCoDeerくんは他の問題にも登場するので長い付き合いになりそうですね。
a, b = map(int, input().split())
if a*b %2 == 0:
print("Even")
else:
print("Odd")
Atcoderでは入力はすべてinput()で受け取ります。入力はすべて文字列型ですから、受け取った後に数値型に変換する必要があります。一行目のコードは受け取ってから数値型に変換するまでを行っています。（入力が数行にわたる場合は行の数だけinput()をする必要があります。）
数値型で受け取った後は、「aとbの積が偶数か奇数かを判定」して、結果を出力するだけです。基本的には2で割った余りが0か1かで判定します。
ABC081A - Placing Marbles
問題文
すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス i には siが書かれています。 すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。
この問題は文字列が与えられて、その中の1の個数をカウントするというものですね。A問題はfor文が無くても解けるようにできてるらしいのですが、これも3桁の数字を調べて1の個数をカウントすればよさそうですね。
input = list(input())
cnt = 0
for i in input:
if i == "1":
cnt += 1
print(cnt)
pythonはlist(文字列)で文字を１文字ずつリストに格納できるので、簡単に実装できました。正直for文を使わなくても３桁程度ならよさそうですね。
おわりに
はてなブログを開設したので練習がてら執筆してみました。これからも自分のモチベーション維持のため、定期的に更新していきたいと思います。とりあえず上位50%くらいの茶色を目指していきます！
