masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

yukicoder No.893 お客様を誘導せよ

python3 yukicoder 競技プログラミング

この問題は別に書かなくてもいいかなと思ったけど，みんなそう思ったのか解説記事が少なそうなので一応書くことにした。

問題

No.893 お客様を誘導せよ - yukicoder

やり方はすぐわかると思われる。 f:id:masuTomo:20200103003557p:plain

上図のようにレジ（塗りつぶしがレジ，白の四角が人）に人が並んでいるとすると出力すべき答えは 32745861である。
実装のポイントは以下の2点。

  • 入力の受け取り

  • レジに並んでいる人数の把握 入力の受け取りはこうした

N = int(input())
P = [0 for _ in range(N)]
A = [[] for _ in range(N)]
for i in range(N):
    P[i],*A[i] = map(int,input().split())

これでP,Aは以下のようになる

#入力
#3
#3 1 2 3
#2 4 5
#1 6

#出力
#P：[3, 0, 1, 2, 0]
#A：[[1, 2, 3], [], [4], [5, 6], []]

あとはＡに格納されている要素を前から順に出力する。このときにindexを指定してもよいがpopを利用すると楽である。

5. データ構造 — Python 3.8.1 ドキュメント

ざっくりいうと，指定したindexの要素を取り出して，削除する。
list.pop(0)とすれば先頭の要素を取り出して，その要素を削除するので，pop(0)を繰り返せば常に先頭の要素が取り出せる。
さらにそのときに，P[i]の値を１ずつデクリメントしておけば，out of indexのエラーがでることも防げる。

N = int(input())
P = [0 for _ in range(N)]
A = [[] for _ in range(N)]
cnt = 0
for i in range(N):
    P[i],*A[i] = map(int,input().split())
    cnt += P[i]
i,j = 0,0
while 1:
    if P[i%N] > 0:
        print(A[i%N].pop(0), end=" ")
        j += 1
        P[i%N] -=1
        if j == cnt:
            exit()
    i += 1

yukicoder No.897 compαctree

yukicoder python3 競技プログラミング

一問ずつ記事をかくのはどうなのか？という思いもある。

問題

No.897 compαctree - yukicoder

少し図を書いて考察すればすぐに規則がわかる。 N = 41, K = 3として考えてみる。
深さを最小にしたいので，各頂点に対する子の数はＫ個とするのが最良である。 f:id:masuTomo:20200102233221p:plain

図からわかるように，
深さ０のとき，頂点数は１個
深さ１のとき，頂点数は３個
深さ２のとき，頂点数は９個
深さ３のとき，頂点数は２７個 であり，Ｋ倍ずつになっている。これの和がNを初めて超える深さを求めればよい。 Ｋのべき乗で増えていく，つまりどんどん増えるので単純にＫのべき乗の和を計算して，Ｎを超えたときの深さを素直に出力すればＯＫ。
K=1のときだけ少し注意。

Q = int(input())
for i in range(Q):
    N,K = map(int,input().split())
    if K == 1:
        print(N-1)
    else:
        ans = 1
        i = 1
        while ans < N:
            ans += K**i
            if ans >= N:
                print(i)
                break
            i += 1
おまけ

高校数学の知識を覚えている人がいれば，以下のように考えても問題を言い換えてもよい。 初項1，公比Kの等比数列の第n項までの和 \frac{K ^n -1}{K-1} \gt N を満たす最小のnを求める。 不等式を変形して n \gt \log _K (N(K-1)+1) を満たす最小のnを求めればよいことになるので，
pythonのmathモジュールmath --- 数学関数 — Python 3.8.1 ドキュメント
が使える環境であれば以下のようにしてもよい。

import math
Q = int(input())
for i in range(Q):
    N,K = map(int,input().split())
    if K == 1:
        print(N-1)
    else:
        print(int(math.log(N*(K-1)+1,K)))

yukicoder No.927 Second Permutation

python3 yukicoder 競技プログラミング

時間ができたらyukicoderの★1.5～★2あたりを解いて勉強することにしている。今日はこれ。

No.927 Second Permutation

No.927 Second Permutation - yukicoder

問題を読んだら，やることはわかる。
というか短い桁数のものなら人間の手でやった方が楽ちん。 （競技プログラミングの最初につまづきそうなポイントとして，やりたいことはあるけど（わかってるけど）うまく実装できないということがあると思うが，この問題はまさにそんな感じ）

  1. 入力を取得（43581）

  2. 降順にソートする（85431）

  3. 末尾の数字から順番にチェックしてうまいこと数字を入れ替える（85413)

で，上記のうまいことの部分をちゃんと実装することが大切（例外処理とかもあるけど，まぁそれは置いておこう）。
一番小さい数字と2番目に小さい数字を入れ替えるということでよい。 ただし，一番小さい数字が複数個あった場合にも対応できるようにしておくこと。肝の部分は以下のような感じで書けばよい。

#X：入力で受け取った整数をlistにして格納
#cntMin：一番小さい数字の個数
X[-cntMin-1], X[-cntMin] = X[-cntMin], X[-cntMin-1]

ちなみに，pythonでは値Aと値Bの入れ替えが以下のように簡単に書ける。

A,B = B,A

また，listの一番後ろの要素から順番にアクセスするにはこんな感じ。

L = ["a","b","c"]
print(L[-1],L[-2])

#c b

コード全体はこのようにしてみた。

X = list(str(input()))
X = sorted(X, reverse=True)
setX = set(X)
if len(setX) <= 1 or len(X) - X.count("0") <= 1:
    print(-1)
    exit()

minX = min(setX)
cntMin = X.count(minX)
X[-1*cntMin-1],X[-1*cntMin] = X[-1*cntMin],X[-1*cntMin-1]
for x in X:
    print(x,end="")

以下の部分は例外処理。
入力の数字がすべて同じ場合と0以外の数字が1個しかないときは2番目に大きい数字が作れないので-1を出力している。

if len(setX) <= 1 or len(X) - X.count("0") <= 1:
    print(-1)
    exit()

ABC149 A～Dについて

AtCoder python3 競技プログラミング

遅ればせながら年末にあったAtCoderのABC149のA ～D問題をやった。

AtCoder Beginner Contest 149 - AtCoder

A - Strings

A - Strings

入力された文字列を結合して出力すれば良い（順番に注意）。
各々が使用している言語の文字列結合の方法について学習すれば良い。
私は文字列自体は結合せずに，2つの文字列を出力する際に，空白無しで出力することで対応した。

S, T = input().split()
print(T,S,sep="")

sepオプションはT,Sの出力の間をどのようにするかを決定する。
指定しない場合は空白が入る。空文字列をしていすればT,Sがつづけて出力される。

B - Greedy Takahashi

B - Greedy Takahashi

まず，高橋くんが持っているクッキーのうちK枚（K>AのときはA枚まで）を食べる。
次に，青木くんが持っているクッキーのうちK-A枚（K-A>BのときはB枚まで）を食べる。

A,B,K = map(int,input().split())
if A >= K:
    A -= K
    K = 0
else:
    K -= A
    A = 0
if B >= K:
    B -= K
else:
    B = 0
print(A,B)

C - Next Prime

C - Next Prime

素数判定ついて知っていれば大丈夫そうである。　　 入力Xから始めて順番に素数判定していけばよい。 ちょっと変わったやり方してみた

def makePrime(n):
    i = 3
    while i*i < n:
        for p in P:
            if i%p == 0:
                i += 2
                break
        P.append(i)
        i += 2

X = int(input())
if X == 2:
    print(2)
    exit()
P = [2]
makePrime(X)
flg = 0
while 1:
    flg = 1
    for p in P:
        if X%p == 0:
            flg = 0
            X += 1
            break
    if flg:
        print(X)
        exit()

X以下の素数をあらかじめ列挙しておいて，X以上の数に対して，X以下のすべての素数で割り切れないようなもののうち最小のもの求めるものである。

D - Prediction and Restriction

D - Prediction and Restriction

じゃんけんで相手の出す手がわかっている。ただし自分はK回前と同じ手は出せない，という条件。

貪欲法で解けばよい。つまり勝てるときは勝ち，Ｋ回前の手の制限により勝てる手が出せない場合はＫ回あとで勝てなくならないように手を出す。ちなみにあいこと負けは0点でまったく同じなので，勝ち以外の手のどちらを出したかは結果の得点には関係しない。

def getPt(h):
    if h == "s":
        return R
    elif h == "p":
        return S
    elif h == "r":
        return P

N, K = map(int,input().split())
R, S, P = map(int,input().split())
T = list(input())
pt = 0
for i in range(N):
    #最初のK回は必ず勝てる
    if i < K:
        pt += getPt(T[i])
    else:
        #相手の出す手がK回前と同じときは，今回は勝てない
        if T[i] == T[i-K]:
            #i回目ではあいこor負けの手を出すので，
            #K回後では必ず勝てるので，T[i]を書き換えておく
            T[i] = "" 
        else:
            pt += getPt(T[i])
print(pt)
なぜ貪欲法で解けるのか

上記の貪欲法よりも得点が高い手があると仮定する。上記の方法でi回目のじゃんけんで勝てない（得点が入らない）のはK回前のじゃんけんで同じ手を出しているからである。　　　 i回目のじゃんけんで勝つためにはi-K回目のじゃんけんで違う手を出す必要があるが，そうするとi-K回目のじゃんけんで勝てないことになる。ここで，i回目のじゃんけんとi-K回目のじゃんけんで得られる得点は（同じ手で勝っているので）同じ得点である。
もし，i-K回目で勝たずにi回目で勝つように手を変えても得られる得点は同じ（もしくはi回目のじゃんけんがない場合は得点が減る）なので，上記の方法が最善であることがわかる。

E,Fについて

まだちょっと僕には難しいです。　　　 がんばります(やってない）。

マスター・オブ・整数で競技プログラミング その３ つづき

python3 数学 整数 競技プログラミング 高校数学

問題

入力：自然数N

出力：A ^ 2 + B ^ 2 + G ^ 2 + L ^2 = Nを満たすA，B（A \gt B）の組の総数。

ただし，A，Bは自然数，G，LはそれぞれA，Bの最大公約数と最小公倍数

解説

A = A' G, B = B'Gと書き直すと A', B'は互いに素。また， AB = GL。これらを A ^ 2 + B ^ 2 + G ^ 2 + L ^2 = Nに代入して整理すると (A' ^ 2 +1)(B' ^2 + 1) G^ 2 = N

ここで N の素因数分解を考える。

  1. Nが素数のとき

    A' ^ 2 + 1 = N, B' ^ 2 + 1 = 1, G = 1のときのみ条件を満たすが， A, B は自然数より条件を満たすような A, Bは存在しない。

  2. N = p _1 ^ {a_ 1} \cdot p _2 ^ {a_ 2} \cdot \cdots \cdot p _n ^ {a_ n} のとき

    • すべての i についてa _i = 1のとき
      G = 1，つまり， A, Bは互いに素となり， A = A', B = B'なので，満たすべき条件式は (A ^ 2 +1)(B ^2 + 1) = Nである。 Nの素因数分解がわかっているので， N = P \times Q ( P > Q)の形に因数分解して，条件式を満たすかどうか全探索すれば良い。

    • ある k についてa _k \geq 2のとき
      G = a _kとすれば， N' = \frac{N}{a ^2 _ k}として， (A' ^ 2 +1)(B' ^2 + 1) = N'を満たす A' , B'を N'の素因数分解を元にして全探索すればよい。

    • 結局全探索するので，上記のG=1とG \neq 1の場合分けは無くても良い。また，Nの素因数分解を考える代わりに，Nの約数を列挙している（どうせA', B'で約数を用いることになる）。

#Nの約数を取得
def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
#平方数かどうか
def isSquare(n):
    if n < 0:
        return False
    if (n**0.5).is_integer():
        return True
    else:
        return False
#最大公約数を取得
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
#互いに素かどうか
def isCoPrime(a,b):
    if gcd(a,b) == 1:
        return True
    else:
        return False

N = int(input())
N0 = N
divisors = []
make_divisors(N)
#Nが素数の場合
if len(divisors) == 2:
    print("No ans")
    exit()
for g in divisors:
    N = N0
    if not g**2 in divisors:
        continue
    else:
        N //= (g**2)
    for d in divisors:
        d /= g**2
        dd = N//d
        if 1 in (d,dd):
            continue
        elif d >= dd:
            if isSquare(d-1) and isSquare(dd-1) and isCoPrime(int(d**0.5),int(dd**0.5)):
                print(int(d**0.5)*g,int(dd**0.5)*g)

というコードを書いた。多分正しいと思うが，N=1300のケース以外を確認できていない。

マスター・オブ・整数で競技プログラミング その３

python3 整数 競技プログラミング 高校数学

３　最小公倍数と最大公倍数

最小公倍数と最大公約数の利用
  • たてＡ cm, 横Ｂ cm, 高さＣ cmの直方体がたくさんある。この箱を隙間なく並べて立方体を作る。作ることができる最小の立方体の1辺の長さを求めよ。

Ａ,Ｂ,Ｃの最小公倍数を求めればよい。最小公倍数や最大公約数を手計算で求める際は，素因数分解して素因数と指数を見てやれば求めることができるがプログラミングしようとするとめんどくさいので，以下のように行う。

A，Bの最小公倍数を l,最大公約数を gとする。

  1. ユークリッドの互除法を利用して最大公約数 gを求める。
  2. A \times B =l \times gを利用して lを求める。
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

def lcm(a,b):
    return a*b//gcd(a,b)

A = int(input())
B = int(input())
g = gcd(A,B)
l = lcm(A,B)

３つの数Ａ，Ｂ，Ｃに対して最小公倍数（最大公約数）を求める場合はまず，任意の2数（Ａ，Ｂ）に対して最小公倍数Ｌ１を求める。Ｌ１とＣに大して最小公倍数を求めればそれが，Ａ，Ｂ，Ｃの最小公倍数である。

A = int(input())
B = int(input())
C = int(input())
l1 = lcm(A,B)
l = lcm(l1,C)
  • 直方体が全部でN個しかない場合に作ることができる最大の立方体の1辺の長さを求めよ。 最小の立方体を作るのに必要な直方体の数を求める。各辺の方向にいくつ直方体を並べるかを数えればよいので，

最小公倍数をＬとしたとき，

M = (L \div A) \times (L \div B) \times (L \div C)

が必要な直方体の個数である。 最大の立方体を作るには最小の立方体を縦，横，高さの3方向に同じ数ずつ並べて作ることができるので一方向に並べる最小の立方体の個数をx個とすると，

M \times x ^ {3} \leq N

が成り立つ。これをみたす最大の整数 x _0 に対し L \times x _ 0が求めたい最大の立方体の1辺の長さである。

N = int(input()) #直方体の個数
l1 = lcm(A,B)
L = lcm(l1,C)
M = L//A * L//B * L//C
x = int( (N/M) ** (1/3) )
print(L*x)

マスター・オブ・整数で競技プログラミング　その2

python3 数学 整数 競技プログラミング 高校数学

2 素因数分解の利用　素因数の個数

2で割り切れる回数

自然数Ｎに対して，１～Nまでの自然数の積をPとする。

  • (1)Pが2で何回割り切れるか。

愚直な実装をすれば，素直に2で割り続ければよい。

def func(n):
    if n == 1:
        return 1
    return n*func(n-1)

N = int(input())
P = func(N)
cnt = 0
while P >= 1:
    if P % 2 == 0:
        P //= 2
        cnt += 1
    else:
        break
print(cnt)

ちなみに，

N = 100
P = func(N)
print(P)

--->P = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

であり，N=100程度でもP=N!はけっこう大きい数（158桁）である。

また，N!は再帰関数を用いなくても単純にループ処理でよい。

P = 1
for i in range(1,N+1):
    P *= i

しかし，愚直に割り算を繰り返す方法だと2で割り切れる回数だけ計算を行うことになり，効率が悪い。「2で1回割り切れる」＝「素因数として２を１つ含む」と考える。すると「２でｎ回割り切れる」＝「素因数として２をn個含む」となることがわかる。つまり，P=N!について素因数2の個数を調べればよい。 たとえば，N=100として考える。１から100までのそれぞれの自然数に含まれる素因数２の個数と，１から100までの自然数の積に含まれる素因数２の個数は等しいので（これ重要），１から100それぞれの数について素因数２の個数を数えてそれを合計すればよい。明らかにすべての偶数（2,4,8,10,,,,,48,50）は素因数２を含んでいるので，50個は素因数２が含まれていることがわかる。この50個という数は，100÷2=50として求められる。

しかし，４や８はそれぞれ２の２乗，２の３乗なので，４は素因数２を2個，８は３個含んでいるため，このような数について考慮する必要がある。したがって，100÷(2の2乗)=25であることから，素因数２を2個含む数は100までに25個あることがわかる。同様に素因数２を3個含む数は100÷（2の3乗）= 12 あまり４なので，12個。このように考えていくと 100 \div 2 = 50 \\ 100 \div 4 = 25 \\ 100 \div 8 = 12 \cdots 4 \\ 100 \div 16 = 6 \cdots 4 \\ 100 \div 32 = 3 \cdots 4 100 \div 64 = 1 \cdots 1\\ したがって素因数2の個数は50+25+12+6+3+1=97（個）

と求めることができる。

N = int(input())
ans = 0
i = 1
while N//(2**i) >= 1:
    ans += N //(2**i)
    i += 1
print(ans)
  • (2)また，Pの末尾に（10進法で）0がいくつ続けて並ぶか。 これは(1)の応用である。末尾に0が来るということは10で割り切れるということであり，それは素因数として2と5を1つ含んでいるということである。したがって，(1)と同様に素因数5の個数を数えて min(素因数2の個数,素因数5の個数)が答えである。さらに minをとらなくても，そもそも素因数2の個数と素因数5の個数では素因数5の個数の方が少ないのは明らかなので，最初から素因数5の個数を答えとしてしまってよい。
#2**iを5**iに変更しただけ

N = int(input())
ans = 0
i = 1
while N//(5**i) >= 1:
    ans += N //(5**i)
    i += 1
print(ans)