AtCoder Beginner Contest 147 ／ Python

• 初学者です。（ 2019 / 9 ～ 現在３ヵ月目 ）
• AtCoder の問題に Python で取り組んでいます。
• ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントください。

また２問しか解けんかった。
A問題、B問題まで10分で解いたのだが、
残り１時間半かけてC問題もD問題も出来ず。

くやしぃぃぃぃ。

結果

まだ４回目だから２問しか解けなくても上がるのね。

問題と解答と勉強

atcoder.jp

提出したコード

A1,A2,A3 = map(int,input().split())
 
if A1 + A2 + A3 >= 22:
    print("bust")
else:
    print("win")

atcoder.jp

提出したコード

S = input()
count = 0
 
for i in range(len(S)//2):
    if S[i] != S[len(S) - 1 - i]:
        count += 1
 
print(count)        

半分にして、
前と後ろを比べて、
一致しない数を合計して出す。

atcoder.jp

これが、嵌まってしまった。

どうしても人間が考える手順で考えさせようとしてしまうのだが、それが良くない、機械の考え方で考えさせるようにしないといけない。

僕は、まず仮に①が正直者だとすると、矛盾するかしないか、と考えようとしていたのだが、これは人間の考え方なのだ。

機械の考え方は、まず正直、不正直の組み合わせ全通りを出して、どれなら証言と矛盾しないかを全て試す、という手順らしい。

人間なら最もアホらしい解き方だが、機械にやらせるならこれで良いそうだ、この辺のズレを意識して考えられるようにならないと思考が沼に嵌まってしまう。

後で考えたコード

import itertools
 
N = int(input())
 
evidence_dit = {}
 
for i in range(N):
    A = int(input())
    x_y = []
    if A == 0:
        evidence_dit[i] = []
    for j in range(A):
        x_y.append(list(map(int,input().split())))
        
        evidence_dit[i] = x_y 
 
ans = 0

attribute = [0,1]
 
for i in itertools.product(attribute,repeat=N):
    flag = False
    
    for j in range(N):
       if i[j] == 1:
            
            for k in evidence_dit[j]:
                if i[k[0]-1] != k[1]:
                    flag = True
                    break
            if flag:
                break
 
    if flag == False:
        ans = max(ans,sum(i))
        
print(ans)

珍しく入力が面倒だった。

for i in range(N):
    A = int(input())
    x_y = []
    if A == 0:
        evidence_dit[i] = []
    for j in range(A):
        x_y.append(list(map(int,input().split())))
        
        evidence_dit[i] = x_y 

辞書型で置いておくことにした。
{0: [[2, 1], [3, 0]], 1: [[3, 1], [1, 0]], 2: [[1, 1], [2, 0]]}

ずっと証言が無い場合に [ ] を入れるというのを忘れたままになっていたので、最後にエラーで悩んだ。

attribute = [0,1]
 
for i in itertools.product(attribute,repeat=N):

正直、不正直のパターンを列挙するところ、僕はitertoolsで0,1の重複順列を作ったのだが、

for i in range(2 ** N):
    h = [0] * N
 
    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1

ほとんど皆、ビット演算子を使って作っていた。

僕はちょっとこれがどうなってるのか良くわからない。


メモ：
i >> j　i を右に j ビットシフト
5 >> 2　5 を右に 2 ビットシフト
　　　　 101｜　➡　001｜01　➡　001
　　　　 右へ２つずらして足りなくなった桁は0にする。
　
5 & 1　➡　101 AND 001　➡　001
　　　　　　両方１のところだけ１になる。

if 5 & 1:　5 & 1 の答えが１なら True、他は False

結局は、[0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] [0, 1, 1] [1, 1, 1]、のような0,1の全パターンを出しているのだが。

今回D問題もビット演算子だったので、ビット演算子を使う方が本筋なのだろう。問題に関連があるなら先の問題もチラッと見てから解いた方が良いのかも。



後は、それぞれのパターンについて、正直となっている奴の証言が矛盾しないかどうかをチェック、全部チェックが通ったものの中で一番正直者が多いものを答える。

flag = False

for 
        for 
            if 
                flag = True
                break
        if flag:
            break

あと、二重の for 文を２つとも抜けるやつ、ちょっと悩んだ。

何か初心者には詰まりやすいところが色々ある問題だった様な気がする、僕だけか？

atcoder.jp

時間オーバーするやつ

from itertools import combinations
N = int(input())
 
A_list = list(map(int,input().split()))
ans = 0
 
for i in combinations(A_list, 2):
    ans += i[0]^i[1]
    
print(ans%1000000007)   

言われた通り、組み合わせを全通り出して、排他的論理和とやらを出したやつ、答えは出るけど、当然時間で弾かれる。

時間を短縮するにはビットがなんちゃらという話っぽいので、ちょっとビットがよくわからないので、また今度気が向いたら解こうと思う。

atcoder.jp

動的計画法みたい。

これもそのうち解く。

atcoder.jp

例によってF問題はまだ良いや。