Atcoder-ABC204をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC204を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 入力で与えられた手を元に考える
- xとyが同じなら、同じ手を出力するとあいこになる
- xとyが違うなら、xともyとも違う手を出すとあいこになる
実装
x, y = map(int, input().split()) if x == y: print(x) else: ans = [0, 1, 2] ans.remove(x) ans.remove(y) print(ans[0])
結果
B問題
考察
- N<=1000 なので全文探索で考える
- 10個以上の場合のみ、10個残した数を足し続けていく
実装
N = int(input()) ans = 0 for a in map(int, input().split()): if a > 10: ans += a-10 print(ans)
結果
C問題
考察
- N<=2000 なので2重ループくらいまではやっても良さそう
- 行ったら帰ってこれないので、「有向グラフ」で考える
- グラフの探索で、ゴールまで探索しないといけないので「深さ優先探索(dfs)」を使って探索する
実装
import sys sys.setrecursionlimit(100000000) N, M = map(int, input().split()) ans = 0 graph = [[] for _ in range(N)] for _ in range(M): A, B = map(int, input().split()) graph[A-1].append(B-1) def dfs(v): global ans find[v] = True ans += 1 for next in graph[v]: if not find[next]: dfs(next) if M > 0: for i in range(N): find = [False] * N dfs(i) else: ans = N print(ans)
結果
D問題
コンテスト中は解けず、後日解説見ながら解いた
考察
- 数列を二つに分け(数列A, B)、max(A, B)の最小値を考える問題
- 「部分和問題」という動的計画法(DP)等を用いて解ける提携問題らしい
- 最大N=100個なので、2つのグループにそれぞれ分ける方法で全文探索するとTLEする
実装
N = int(input()) T = list(map(int, input().split())) s = sum(T) dp = [[False] * (s + 1) for _ in range(N + 1)] dp[0][0] = True for i in range(N): for j in range(s + 1): if T[i] <= j: dp[i + 1][j] = dp[i][j - T[i]] or dp[i][j] else: dp[i + 1][j] = dp[i][j] for i in range(s//2, s+1): if dp[N][i]: print(max(i, s-i)) break
結果
まとめ
- C問題が、DFS使うところに気づけて、時間内に解けたのがよかった
- 成長している気がした
- D問題で、DPの勉強をして、実際に時間かかったが解けたので、これからもDPの勉強を続けていきたい
- DPはよく出るし、応用範囲も広いのでぜひ身につけたい！
Atcoder-ABC203をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC203を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題通りに実装する
実装
a, b, c = map(int, input().split()) if a == b: print(c) elif b == c: print(a) elif a == c: print(b) else: print(0)
結果
B問題
考察
- N, K <= 9 のため全探索すれば良い
実装
N, K = map(int, input().split()) ans = 0 for i in range(1, N+1): for j in range(1, K+1): r = int('{}0{}'.format(i, j)) ans += r print(ans)
結果
C問題
考察
- max(N) = 2*105 のため、O(N2) では間に合わない
- for loop 一回程度の繰り返しで探索する
- Aくんに出会うまでにKが0になるか、そうでないかで判定する
- Aは順番が小さい順に並んでるわけではないので、sortし、Aを小さい順に並べる
実装
N, K = map(int, input().split()) pos = 0 ans = 0 AB = [] for _ in range(N): A, B = map(int, input().split()) AB.append((A, B)) AB = sorted(AB, key=lambda x: x[0]) for A, B in AB: if A - pos > K: ans = K + pos K = 0 break else: K = K + B - (A-pos) pos = A if K > 0: ans = K + pos print(ans)
結果
まとめ
- D問題は難し過ぎて手が出なかった
- 13回目にして茶色コーダになれた
- C問題までの早解の精度を上げていきたい
Atcoder-ABC202をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC202を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 反対面の目は、それぞれa, b, cから7引いた値になるので、それらを足し合わせれば良い
実装
a, b, c = map(int, input().split()) ans = 7-a + 7-b + 7-c print(ans)
結果
B問題
考察
- 入力の文字列を反転させた上で、6, 9のみに着目して処理すれば良い
- 6は9に変換
- 9は6に変換する
- Sは最大105程度の文字列であるが、
O(n)程度の処理なら十分間に合う
実装
S = list(input()) S.reverse() for i in range(len(S)): if S[i] == "6": S[i] = "9" elif S[i] == "9": S[i] = "6" print(*S, sep="")
結果
C問題
考察
- max(N) = 105 なのでO(n2) では間に合わない
- 配列A, B[C]を作成し、sortして、Aの値で、B[C]を2分探索するのであれば間に合いそう
- O(NlogN) くらいになるはず
- 数列内には同じ数値を含むため、注意する
- 今回は、
bisect_leftとbisect_rightを利用した
- 今回は、
実装
import bisect N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) C = list(map(int, input().split())) L = [] ans = 0 for j in range(N): L.append(B[C[j]-1]) L.sort() A.sort() for i in range(N): j = bisect.bisect_left(L, A[i]) k = bisect.bisect_right(L, A[i]) ans += k-j print(ans)
結果
D問題
方針は立てられたが、実装できず時間切れに
考察
- 全探索した場合、 max = 230 なので間に合わない
- そのため、工夫して高速に探索する必要がある
- 重複組合せによって場合の数を求める
- Kの数に応じて、頭の文字からa or bを決めていくことを繰り返していく
実装
from math import factorial A, B, K = map(int, input().split()) ans = [] def num_of_case(a, b): return factorial(a+b)//(factorial(a)*factorial(b)) def gen_strings(a, b, k): if a == 0: ans.append("b" * (a + b)) elif b == 0: ans.append("a" * (a + b)) elif num_of_case(a - 1, b) >= k: ans.append("a") gen_strings(a-1, b, k) else: ans.append("b") gen_strings(a, b-1, k-num_of_case(a-1, b)) gen_strings(A, B, K) print(*ans, sep="")
結果
まとめ
- またしてもD問題が解けなかったので、定型のアルゴリズムの勉強を続けていきたい
- C問題までの回答時間の削減も続けていきたい、20分程度で安定して終えられるようにしたい
Atcoder-ABC201をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC201を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 与えられた数列Aの要素を全て並び替えて、確認する
- 3!で6通りなので全て試せばよさそう
実装
from itertools import permutations A = list(map(int, input().split())) flag = False for a1, a2, a3 in permutations(A): if a1-a2 == a2-a3: flag = True break if flag: print("Yes") else: print("No")
結果
B問題
考察
- (山の名前, 山の高さ) の配列を作り、山の高さでsortし、2番目に高いものを出せばよさそう
- pythonなら、sortするkeyを指定できる
実装
N = int(input()) ST = [] for _ in range(N): S, T = input().split() T = int(T) ST.append((S, T)) # 山の高さでsortする sorted_ST = sorted(ST, key=lambda x: x[1]) print(sorted_ST[-2][0])
結果
C問題
愚直に全探索するべきなのに、場合の数とか考えて集合とかで数えられないかなと考え出してドツボにハマり時間切れした・・・
考察
- 必ず使われる数字の種類と、使われてるかもしれない数字の種類で考えて場合分けできそうだなと思って解いていた
- 実際、解けなくもなさそうだけど、自分はゴチャゴチャになって解けなかったww
- そもそも、パスワードのパターンは10000通りしかないので、条件に合致するものを全て調べあげた方がシンプル
- パスワードには、使われる数字の種類が、全て使われているか？
- パスワードには、使われていない数字が、含まれてないか？
実装
S = input() used = S.count("o") ans = 0 for i in range(10000): passwd = str(i).rjust(4, "0") cnt, flag = [False]*10, True for j in range(4): k = int(passwd[j]) if S[k] == "o": cnt[k] = True elif S[k] == "x": flag = False if cnt.count(True) == used and flag: ans += 1 print(ans)
結果
Atcoder-ABC200をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC200を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- Nが100で割り切れる場合とそうでない場合がポイントになりそう
- 100で割り切れる場合は、そのまま出力する
- そうでない場合は、100で切り捨て除算した値に1を足す
- ex. N=2021 の場合、20になるが、実際は21世紀なので1を足す
実装
N = int(input()) if N % 100 == 0: print(N//100) else: print(N//100+1)
結果
B問題
考察
- K<=20 なので問題文通りに実装し、全探索すれば良さそう
- pythonの場合、文字列200を後ろに付け加える部分は、一時的にstrで計算したのちに、intに直せばよさそう
実装
N, K = map(int, input().split()) for _ in range(K): if N % 200 == 0: N = N//200 else: N = int(str(N) + "200") print(N)
結果
C問題
考察
- N<=2*105 なので、全ての組みを探索するとTLE(実行時間超え)になりそう
- i, j に対して2重ループ書くことになり、計算量が 1010 程度になるため
- 入力例を見て行ったときに、200で割った余りが同じもの同士を用いて、組み合わせを用いることで、数え上げられそうと気づく
- ex1. 123, 223, 123, 523, 200, 2000
- 200で割った余りはそれぞれ、 123, 23, 123, 123, 0, 0
- 同じ余りのグループを作ると、(1, 3, 4) (5, 6) という集合ができる
- 上記グループよりそれぞれ2つ取り出す組み合わせが答えになる
- (1 ,3), (1, 4), (3, 4), (5, 6) が答えになる
- 今回は具体の組み合わせは不要で、何通りあるか出せば良いので 3C2+2C2 = 4 となる
- ex1. 123, 223, 123, 523, 200, 2000
- 200の余りが0~199になるため、配列を用意し、与えられる数列Aの要素の余りを計算し、特定の余りを持つ要素の数を数え上げ、組み合わせを用いてそれぞれ足し合わせていけばよさそう
実装
import math N = int(input()) A = list(map(int, input().split())) q = [0] * 200 ans = 0 def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n - r)) for a in A: idx = a % 200 q[idx] += 1 for i in q: if i >= 2: ans += comb(i, 2) print(ans)
結果
D問題
方針を誤り、時間内に解くことができなかった
考察
N<=200 のため、全ての場合の和を数え上げることも、bit探索で数え上げることも、時間内には不可能
- そのため、最初は累積和を求めて、累積和同士の差分を求めることで数え上げようとした
- この場合 20000回程度の計算量に収まり、解くことができると考えた
- ただ、この場合は連続した数列部分のみを探索することになり、例えば 1, 2, 5 と並ぶような数列はこのパターンから外れるため、答えとして No が必要以上に出てしまうことになる
- ここから方針転換し、どうやって解こうと思って考えてて時間切れしてしまった・・・
- そのため、最初は累積和を求めて、累積和同士の差分を求めることで数え上げようとした
今回は「鳩の巣原理」を用いて考えればよかったそう(解説を見て理解したw)
鳩ノ巣原理： n, mを自然数 n > mとする n個のものをm組にわけるとき、少なくともひとつの組は2個以上のものを含む
今回の問題に当てはめて利用する場合は、「200で割った余りは、200通りなので、201通り以上の範囲を調べれば少なくとも1つの組は2個以上含むことになり、B, Cが見つかることになる。」となる
- 28=256 なので、bit探索で与えられた数列の頭8番目までの要素を全探索することで1組見つけることができる
- 最悪のケースは頭8個の数列の部分数列の総和は、全て違う値になることだが、201通り以上探せば同じものは見つかる
- 数列内に同じ数字がある場合は、総和が同じになり普通に同じ余りになる数列が見つかる
- 28=256 なので、bit探索で与えられた数列の頭8番目までの要素を全探索することで1組見つけることができる
存在する場合はひとつ出力してください= 「少なくとも1つ以上存在する」のため、全部を丁寧に探す必要はないと言うヒントのため、見逃さないようにしたい- 1つでも見つかればいいので、探索する範囲を適切に制限することで解ける！場合が多そう(もちろん、効率よく全探索する場合もあるのだろうが)
実装
N = int(input()) n = min(N, 8) A = list(map(int, input().split()))[0:n] q_list = [[] for _ in range(200)] def solve(): for i in range(1, 2 ** n): bit = bin(i)[2:].rjust(n, "0") s, l = 0, [] for i, b in enumerate(list(bit)): if b != "1": continue s += A[i] l.append(i+1) idx = s % 200 q_list[idx].append(l) if len(q_list[idx]) >= 2: return idx return None ans = solve() if ans is None: print("No") else: print("Yes") x, y = q_list[ans][1], q_list[ans][0] print(*([len(x)]+x)) print(*([len(y)]+y))
結果
振り返り
- A, B ,C をもっと安定し解けるようになり、かつ20分以内に解けるようになりたい
- 今回のD問題のように、「あとちょっとでAC」になった際にDebugしてしっかり解き切れるようになるための力をつけたい
- 下記とかが参考になりそう
- E問題はDPで、DP勉強してといてみるのもアリだが、当分はA, B, Cの早解をしてrateをあげるのが良さそう
- 基本アルゴリズムの勉強は茶色になってから考える
Atcoder-ABC198をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC198を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 与えられる、整数Nに対し1~N-1まで数え上げれば良さそう
- N<=15 のため全探索しても計算量的に問題なさそう
- A君に1つ挙げた場合、B君にはN-1つあげることになるので、A君にあげる数に着目し数え上げれば良さそう
実装
N = int(input()) ans = 0 for n in range(1, N): ans += 1 print(ans)
結果
B問題
考察
- 回文かどうかは、文字の両端から値をチェックし続ければ良さそう
- pythonの場合は文字列を配列のように扱えるし、後ろから数える場合もマイナスをindexとして指定すればいいので、それで良さそう
- 頭に0をいくつつけるかは、文字の後ろに0がいくつあるかを数え上げ、それと同じだけ頭につけるので、良さそう
実装
N = input() flag = True cnt = 0 for i in range(1, len(N)): if N[-i] == "0": cnt += 1 else: break S = "0"*cnt + N for i in range(len(S)): if S[i] != S[-i-1]: flag = False break if flag: print("Yes") else: print("No")
結果
C問題
考察
- 到達点P(X,Y)までの、行き方が複数パターンありそう
- 半径Rで、ちょうど行くパターン
- 途中まで、半径Rで行き、直前でジグザグに行くパターン
- 半径R内に点Pがあり、2手で移動するパターン
- 問題といてる途中は、半径2R以内の点に対して、2手で行けることの確証はなかった
- なんとなく、そうなんじゃね？くらいに思ってて、ダメだったらやり直そうと思ってた
実装
- 半径内の点への場合わけが漏れていて、1回WAになった
from math import sqrt R, X, Y = map(int, input().split()) d = sqrt(X**2 + Y**2) if d % R == 0: print(int(d//R)) else: if d > R: p = d // R - 1 print(int(p+2)) else: print(2)
結果
D問題
TLEで解けず、コンテストは終了した
考察
覆面算という分野の問題らしい- 知らなかったので、コンテスト中にググった
- どうやら、inputのうち、10種類の文字列がある場合は解けないらしい
- 当たり前といえば当たり前か
- inputのうちユニークな文字列と、数字の辞書を作り、条件にマッチさせるまでぶん回せば良さそう
from itertools import permutationsを使えば良さそう
実装
めちゃくちゃTLEした、コンテスト後会社の後輩の指摘により無事解けた(自分の力ではない)
- 最初はこんな感じで解いてた
- 理由はよくわかってないが、
combinationsしてから、permutationsした方が若干早かった- 計算的には等価な気もしなくもないが、この辺りは深掘りが必要そう
permutationsのみでも、ACできたので、この辺りは不要ぽい
from itertools import combinations, permutations from sys import stdin def to_i(dic, s): n = 0 for c in s: n = n * 10 + dic[c] return n def solve(s1, s2, s3): uni_w = set(s1+s2+s3) if len(uni_w) > 10: return None for c in combinations(range(10), len(uni_w)): for p in permutations(c): dic = {k: v for k, v in zip(uni_w, p)} if dic[s1[0]] == 0 or dic[s2[0]] == 0 or dic[s3[0]] == 0: continue a, b, c = to_i(dic, s1), to_i(dic, s2), to_i(dic, s3) if a + b == c: return a, b, c return None def main(): S1, S2, S3 = stdin.readline().strip( ), stdin.readline().strip(), stdin.readline().strip() ans = solve(S1, S2, S3) if ans is None: print("UNSOLVABLE") else: print(*ans, sep="\n") if __name__ == '__main__': main()
結果
E問題
考察
- 与えられるデータは無向グラフである
グラフと木 from 京大 マイコンクラブ
www.slideshare.net
- グラフを全探索するということで、深さ優先探索を利用して解く
- stackの動きに合わせて、各ノードの色の数をcountしていく
- 深く潜って行くたびに +1する
- 浅く戻るときは、-1することを忘れないようにする
実装
ansにデータを入れる際にnot inでも調べ、重複を弾いていたが不要だった- むしろ、
inが O(n)なので、ansが大きな場合に、TLEを連発することになった- forで何度も巨大なlistに
not inするので計算量が莫大になった
- forで何度も巨大なlistに
- むしろ、
graph[a].append(b)のみで、sampleは通るが、bのノードに先にたどり着いてしまった場合aに遷移できない場合があり、全探索できてなかった- 無向グラフの場合は両方に有向辺を生やしてあげると素直に実装できてよいとのこと
- 会社の強い後輩のアドバイスでシュッと解けた
- 無向グラフの場合は両方に有向辺を生やしてあげると素直に実装できてよいとのこと
- graph, c_dictは今回辞書型だったが、別にlistでも問題はない
- むしろ、too muchなのでlistの方が良い
from collections import deque N = int(input()) C = tuple(map(int, input().split())) graph = {i: deque() for i in range(N)} c_dict = {C[i]: 0 for i in range(N)} for _ in range(N-1): a, b = map(int, input().split()) graph[a-1].append(b-1) graph[b-1].append(a-1) stack, seen, ans = [], [False]*N, [] def check(c): if c_dict[C[c]] == 1: ans.append(c) def dfs(i): seen[i] = True stack.append(i) c_dict[C[i]] += 1 check(i) while stack: s = stack[-1] if not graph[s]: p = stack.pop() c_dict[C[p]] -= 1 continue next = graph[s].popleft() if seen[next]: continue seen[next] = True stack.append(next) c_dict[C[next]] += 1 check(next) for i in range(N): if not seen[i]: dfs(i) ans.sort() for a in ans: print(a+1)
結果
追加
dfs は自分でスタックを管理するとバグらせやすいので再帰でかくアプローチが一般的な気がしますとのことで再帰でもdfsを実装してみた練習問題
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja
n = int(input()) graph = [[] for _ in range(n+1)] for _ in range(n): u, k, *v = map(int, input().split()) graph[u] = v time, find_time, finish_time = 0, [0]*(n+1), [0]*(n+1) def dfs(v): global time time += 1 find_time[v] = time for next in graph[v]: if find_time[next] == 0: dfs(next) time += 1 finish_time[v] = time for s in range(1, n+1): if find_time[s] == 0: dfs(s) for i in range(1, n+1): print(i, find_time[i], finish_time[i])
まとめ
Atcoder-ABC197をpythonでA,B,C,D問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC197を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
- 3文字の入力が与えられるが、先頭文字を末尾に移動して表示すれば良い
S = list(input()) print(S[1]+S[2]+S[0])
B問題
- 与えられた情報を2次元のlistに情報を格納する
- H * W の2次元配列を初期値0で作成する
- 入力情報で、壁がある場合は1で更新する
- 与えられた点から、縦横それぞれを調べれば良い
- 点から上を調べる、下を調べる、右を調べる、左を調べる
- 1つずつ調べ上げる中で、壁にぶつかったらそこで数えるのを止める
- 自分自身も含めないといけないので、それを重複して調べないようにすること
H, W, X, Y = map(int, input().split()) S = [[0] * W for _ in range(H)] ans = 0 for i in range(H): s = list(input()) for j, c in enumerate(s): if c == "#": S[i][j] = 1 # 基準点よりも上を調べる(自分自身を含める) for x in range(X-1, -1, -1): if S[x][Y-1] == 0: ans += 1 else: break # 基準点よりも下を調べる(自分自身を含めない) for x in range(X, H): if S[x][Y-1] == 0: ans += 1 else: break # 基準点よりも左を調べる(自分自身を含めない) for y in range(Y-2, -1, -1): if S[X-1][y] == 0: ans += 1 else: break # 基準点よりも右を調べる(自分自身を含めない) for y in range(Y, W): if S[X-1][y] == 0: ans += 1 else: break print(ans)
C問題
AC半分WA半分で本番中は解けなかった
- 与えられた数列を分割する方法を全部網羅するのにどうするか？が考慮が足りなかった
- bit探索を用いて、数列の分割を網羅的に探索する
- 例えば、長さ6(=N)の数列は、5(=N-1)つの分割するポイントがあるので、それをbitを用いて表現する
- あとは、全文探索(1 ~ 2N-1)を行い、xorの最小値を更新していけば良い
- 数列の分割点をlistに入れてあげて、それを用いてスライスで数列を分割していく
N = int(input()) A = list(map(int, input().split())) ans = pow(2, 30) def get_or(l): x = l.pop(0) for i in l: x = x | i return x def get_xor(l): x = l.pop(0) for i in l: x = x ^ i return x for i in range(1, 2 ** (N-1)): # スライスで分割する際に、頭を切れるように追加 L = [0] # bit列を文字列表す bit = bin(i)[2:].rjust(N-1, "0") # 1がある場合は分割する for j, b in enumerate(list(bit)): if b == "1": L.append(j+1) # スライスで分割する際に、最後尾切れるように追加 L.append(len(A)) O = [] for k in range(1, len(L)): # 分割した配列の計算結果をlistに追加 O.append(get_or(A[L[k-1]:L[k]])) # orの結果をxorした結果をget_xorで取得し、小さければansを更新 ans = min(ans, get_xor(O)) # len 1の時にはansが更新されなかったので修正した if len(A) == 1: print(A[0]) else: print(ans)
D問題
解き方はイメージできたが、時間切れで実装しきれず
- 各点Pは、P0とPN/2の中点を中心(点O)とした円上に存在する
- P1は、2pi/N だけP0をずらしたところに存在する
- P1は、半時計周りにずらすので、+ 2pi/Nする
- P0とPN/2の距離の半分が半径になる
- P1は、2pi/N だけP0をずらしたところに存在する
- 中心からのP1の角度は
atan2を用いることで求められる
- 原点を中心にした円上の座標は半径r, X軸からの角度θを用いて表すことができる
- x=rcosθ
- y=rsinθ
- 円状で求めた点を、原点から、中心Oまでの距離をずらしてあげる
from math import atan2, cos, pi, sin, sqrt N = int(input()) x0, y0 = map(int, input().split()) xn2, yn2 = map(int, input().split()) # 円の中心座標 ox, oy = (x0+xn2)/2, (y0+yn2)/2 # 円の半径 r = sqrt((x0-xn2)**2 + (y0-yn2)**2)/2 # 点P1の座標角度を求める theta = atan2(y0-oy, x0-ox) + 2*pi/N x1, y1 = r*cos(theta), r*sin(theta) # 原点から、中心Oまでの距離をずらす print(x1+ox, y1+oy)
まとめ
- 解説を軽くみて、無事D問題まで解けた。次は、時間内に解けて早く茶色コーダになれるように頑張りたい
