LoginSignup
0

More than 1 year has passed since last update.

posted at

超初心者がAtcoder ProblemsのC問題を181回から190回までをpythonで解いてみた

解き方を忘れないためにまとめてるだけなのでコードはめちゃくちゃ不細工です、ここもっと良くできるよって場所あったら教えていただけるとありがたいです!!

181 Collinearity

practice.py
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            x1,y1 = points[i]
            x2,y2 = points[j]
            x3,y3 = points[k]
            if (y3-y1)*(x2-x1) == (y2-y1)*(x3-x1):
                print("Yes")
                exit()
print("No")

この問題は3≤N≤10**2なので、全探索しても間に合っちゃいます!!楽しいね。同一線上にあるということは傾きが同じということです。私の場合はx1,y1をベースにしたので、(y3-y1)/(x3-x1)と(y2-y1)/(x2-x1)の値が等しければ条件クリアということです。しかし/はあんまし好きじゃないので形を直して(y3-y1)(x2-x1)と(y2-y1)(x3-x1)の形に直しました。条件がクリアされた瞬間にYesを出力して、処理を終わらせます。

182 To 3

practice.py
from itertools import product
INF = 1<<60

def judge(pro):
    num = ""
    for i in range(leng):
        if pro[i]:
            num += n[i]
    if not num:
        return INF
    if int(num) % 3==0:
        return leng - len(num)
    else:
        return INF

n = input()
leng = len(n)
ans = INF
for pro in product((0,1), repeat=leng):
    ans = min(ans, judge(pro))
if ans==INF:
    print(-1)
else:
    print(ans)

この問題はbit全探索を使いましょう!!(ドンっ!)お前は何をアホなこと言っとるんだ1≤N<10**18じゃんと思ったあなた、考え方が足りないよ...この問題は桁数に注目した問題なので桁数ベースで解いてしまえばnの最大値が18(多分)として、その桁を消すか消さないかの考え方でbit全探索ができてしまいます。judgeメソッドの中ではまず空の文字列を用意します。そしてfor文を桁数の数だけ回して、もしpro[i]がTrueならば空の文字列の中にnのi桁目の数字をぶちこんであげましょう。3の倍数かを調べる前に、もし文字列に何もはいっていなかったらエラーが出てしまうので文字がはいっているか調べてあげて入っていないのならば、INFを返して弾き飛ばします。最後に3の倍数かどうかを調べて、もし3の倍数なら、消した桁の数を返してあげましょう。

183 Travel

practice.py
import itertools

n,k = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(n)]
mat = [i for i in range(1,n)]
ptns = list(itertools.permutations(mat))
cnt = 0
for ptn in ptns:
    ptn = [0] + list(ptn) + [0]
    tmp = 0
    for i in range(n):
        tmp += T[ptn[i]][ptn[i+1]]
    if tmp == k:
        cnt += 1
print(cnt)

順列全探索パイセンチッすチッす。 2≤N≤8とNの値がめちゃめちゃ小さいので順列全探索を使うことがわかります。ただ最初と最後が1にならないといけないので、最初と最後の値を抜いた配列で作れるパターンを洗い出します。(配列を作るときのrangeが(1,n)なのはインデックス番号で操作していきたいから)。そしてfor文の中で、先に作り出した全パターンの最初と最後に[0]を付け足して、最初と最後に1を通るという条件を強引に満たさせます。その後は問題の説明通りに移動距離を足し合わせて、もしkの値と同じならcntに1を追加し、最後にcntの値を出力します。

184 Super Ryuma

practice.py
def solve():
    if a==c and b==d:
        return 0
        
    if a+b==c+d:
        return 1
    if a-b==c-d:
        return 1
    if abs(a-c)+abs(b-d) <= 3:
        return 1
    
    if abs(a-c) + abs(b-d) <= 6:
        return 2
    if (abs(a - c) + abs(b - d)) % 2 == 0:
        return 2
    if abs((a+b)-(c+d)) <= 3:
        return 2
    if abs((a-b)-(c-d)) <= 3:
        return 2
    
    return 3

a,b = map(int, input().split())
c,d = map(int, input().split())
print(solve())

正直、30分考えても全く分からんかったからunidayo先生の力借りました、解説がバチわかり易くて助かります...
助けてもらってきてね
https://qiita.com/u2dayo/items/f59a6661fc8037414a01#c%E5%95%8F%E9%A1%8Csuper-ryuma

185 Duodecim Ferra

practice.py
from math import comb

n = int(input())
ans = comb(n-1,11)
print(ans)

この問題は数学的知識が求められる問題っぽいっすね。まず、この問題に必要なのは重複組み合わせという考え方です。
重複組合せについて
https://manabitimes.jp/math/1101
この問題に合わせて説明すると、問題の条件で"このとき分割後の各棒の長さが全て正整数になるように分割しなければなりません。"とあるので、まず全ての分割された棒に1の長さを与えます。その後余った棒の、分配パターンを考えていきます。重複組み合わせの考え方で言うと、(n-12)のボールと11個の仕切りを一列に並べるということです。なので式としては(n-12+11)H11になります。これをmathライブラリのcombメソッドを使って求めればACできます!

186 Unlucky 7

practice.py
n = int(input())
cnt = 0
for i in range(1,n+1):
    if "7" in str(i):
        cnt += 1
        continue
    i = format(i,'o')
    if "7" in str(i):
        cnt += 1
        continue 
print(n-cnt)

ふつーに全探索しておわおわりです。for文の中では7がはいっているか簡単に確かめるためにiの数をstr型に変換してあげると良いです。最初に10進数の値で調べてあげて、もし10進数の値に7がはいっていなかったら8進数にして10進数の時と同じ処理をしてあげます。最後にcntにはいっているのは7を含む数なのでnの数から引いてあげればオッケです。

187 1-SAT

practice.py
n = int(input())
zeros = []
ones = []
for i in range(n):
    char = input()
    if char[0] == "!":
        ones.append(char[1:])
    else:
        zeros.append(char)
zeros = set(zeros)
ones = set(ones)
for zero in zeros:
    if zero in ones:
        print(zero)
        exit()
print("satisfiable")

!がついてる文字用と、ついてない文字用のリストをはじめに用意してあげます。次に、for文を回して、入力値に!がついているならonesに格納し(char[1:]にしてるのは、あとで調べるときに!が邪魔だから)、入っていなければzerosに格納します。次に、計算量を少なくしたいのでset型にして、重複を消します。最後にzerosを元にfor文を回して、zeroの値がonesにもはいっていたなら、zeroの値を出力して、処理を終わらせます。for文が回り切っても処理が終わっていなかったらsatisfiableを出力してあげて終わりです。

188 ABC Tournament

practice.py
n = int(input())
alist = list(map(int, input().split()))
servivors = list(range(len(alist)))
while len(servivors) > 2:
    r = []
    for i in range(1, len(servivors), 2):
        t1, t2 = servivors[i - 1], servivors[i]
        if alist[t1] > alist[t2]:
            r.append(t1)
        else:
            r.append(t2)
    servivors = r
t1, t2 = servivors[0], servivors[1]
if alist[t1] < alist[t2]:
    print(t1 + 1)
else:
    print(t2 + 1)

この問題は生き残っている人を記録するためのservivors(スペル間違ってるかも)リストを作り、そこに敗退していない人のインデックス番号をラウンドごとに記録しておきます。servivorsの長さが2以下になるのは準決勝までの処理が終わったと言うことなので、その段階でwhile文を抜けます。while文の中では2つの数字を比べて、大きい方をservivorsリストに追加していきます。while文の後には小さい方の数字が入ったインデックス番号を抜き出し、1を追加しておわりです。

189 Mandarin Orange

practice.py
n = int(input())
alist = list(map(int, input().split()))
ans = 0
for i in range(n):
    mini = 10**6
    for j in range(i,n):
        dist = j-i+1
        mini = min(mini,alist[j])
        tmp = mini*dist
        ans = max(ans,tmp)
print(ans)

TLE出まくってまじでストレス溜まった、これに問題はunidayoさんの計算量を減らす方法を参考にしたので、そっちをみてみてください。(minでも計算量めっちゃ増えちゃうんだね、知らんかったわ...)
https://qiita.com/u2dayo/items/edd462bf0d8b2f2df55f#c%E5%95%8F%E9%A1%8Cmandarin-orange

190 Bowls and Dishes

practice.py
from itertools import product
from collections import Counter
  
def judge(pro):
    counter = Counter()
    for i in range(k):
        choice = choices[i][pro[i]]
        counter[choice] += 1
    cnt = 0
    for a,b in conds:
        if counter[a] > 0 and counter[b] > 0:
            cnt+=1
    return cnt
    

n,m = map(int, input().split())
conds = []
for _ in range(m):
    cond = list(map(int, input().split()))
    conds.append(cond)
k = int(input())
choices = []
for _ in range(k):
    choice = list(map(int, input().split()))
    choices.append(choice)
ans = 0
for pro in product((0,1), repeat=k):
    ans = max(ans, judge(pro))
print(ans)

この問題はbit全探索で行けちゃいます。これは1≤K≤16から何となく予測できます。まず、全ての条件、ボール置く皿の選択肢を受け取ります。そして、いつものようにproductメソッドを使ってbit全探索開始です。肝心の判定内では、それぞれの皿に置かれているボールの数を調べるためにCounterメソッドを使って計測用のcounter変数を作ります。その後for文を回してそれぞれの人により選択された皿にボールをおきましょう。最後に、それぞれの条件と照らし合わせて、満たされた条件の数を調べ上げ戻り値として返します。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0