2022-12-18

競プロ典型90問　 Large LCM（★3）コード解説

はじめに

　本日はM1グランプリでしたね！私はYoutubeに上がっている動画を1回戦からすべて見てるくらいM1が好きですので、今年の楽しく拝見させていただきました！
ウエストランドのお二方、本当におめでとうございます！！
失礼ですが始まる前は正直優勝するとは思いませんでした…。以前からの悪口の勢いとあるなしクイズのフォーマットがマッチしててとても聞きやすくて密度の高い5分間でした！

正直、M1で満足してお休みモードなので今日はブログの更新を休もうと思ったんですけど、こういうのは1日でも休んだら気持ちが緩むので、気合を入れてやっていきます！
今回も競プロ典型90問の★3問題です。

はじめに
競プロ典型90問
038 - Large LCM（★3）
おわりに

競プロ典型90問

atcoder.jp

038 - Large LCM（★3）

最小公倍数を求めて、それが10^18より大きければLargeを出力するといった問題です。
考え方自体は簡単だと思いますが、競プロだし、なんかあるんでしょ～？と思われる方もいらっしゃると思いますが、実はPythonだと、とてもシンプルなコードで書くことが出来ます。

import math
a, b = map(int, input().split(" "))

lcm = a*b // math.gcd(a, b)
if lcm > 10**18:
    print("Large")
else:
    print(lcm)

まず、mathモジュールを用いて、最小公倍数はmath.lcmで求めることが出来ます。が、Atcoderではエラーが出力されました。ですので代わりの手法で最小公倍数を求める必要があります。
最小公倍数は最大公約数math.gcdを用いて、以下の式で表すことが出来ます。

lcm(a, b) = a*b // gcd(a, b)

それが10¹⁸より大きいか小さいかを判断して答えを出力します。ここがポイントで、Pythonは多倍長変数と言ってめちゃくちゃ長い数値を扱える言語なので、このまま判定することが出来ます。

しかし言語によってはオーバーフローして計算できないため、工夫する必要があるらしいです。私はPython以外はほとんどわからないので、気になった方は調べてみてください。

おわりに

今回はPython勢にとって有利すぎる問題でしたね。

今から見損ねた敗者復活戦の動画を見ますので、今日はこの辺で…。お疲れ様でした。

2022-12-17

AtCoder Beginner Contest 282　A, B, C問題コード解説

はじめに

　今回のABCはいつも通り、ABC3完でした。またDが解けない…。アルゴリズムの理解を深めないと計算量を小さくできなそうですね…。
　あー次こそは解きたいいいいいいいいい！！！！！！！

はじめに
AtCoder Beginner Contest 282
A問題
- コード解説
B問題
- コード解説
C問題
- コード解説
おわりに

AtCoder Beginner Contest 282

atcoder.jp

A問題

コード解説

k = int(input())
str1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
print(str1[0:k])

B問題

コード解説

n, m = map(int, input().split(" "))
 
tokerumondai = [set() for i in range(n)]
 
for i in range(n):
    s = list(input())
    for j in range(len(s)):
        if s[j] == "o":
            tokerumondai[i].add(j)
cnt = 0
for i in range(len(tokerumondai)):
    for j in range(i+1, len(tokerumondai)):
        wa = tokerumondai[i] | tokerumondai[j]
        if len(wa) == m:
            cnt += 1
print(cnt)

C問題

コード解説

n = int(input())
s = input()
s_list = list(s)
 
mode = "finish"
 
for i in range(len(s_list)):
    if s_list[i] == "\"" and mode == "finish":
        mode = "start"
    elif s_list[i] == "\"" and mode == "start":
        mode = "finish"
 
    if s_list[i] == ",":
        if mode != "start":
            s_list[i] = "."
 
print("".join(s_list))

おわりに

次回はD解くぞーーーーーーー！！！

2022-12-16

競プロ典型 90 問　032 - AtCoder Ekiden（★3）

はじめに

今回は年始の駅伝を先回りして、競プロ典型90問から、「032 - AtCoder Ekiden」を解いてみたいと思います。
正直正月の駅伝見たことないけれど…。

はじめに
競プロ典型90問
032 - AtCoder Ekiden
おわりに

競プロ典型90問

atcoder.jp

032 - AtCoder Ekiden

問題の目的

かかる時間の最小値を求める。

問題の制約

嫌いな相手同士でたすきのやり取りが出来ない。

プログラムの方針

この問題は、 ①嫌いな相手を記録する ②制約の上で走る順番の全探索を行って最小値を探す
に分かれます。

①については、グラフ理論の隣接行列という考え方を使えば簡単に実装できます。

ここでは例を挙げて説明します。１さんは２さんと不仲で、２さんは３さんと不仲であると考えます。それをグラフで表したものが上の図となります。
この問題では不仲であればお互いにたすきをやり取りすることが出来ないので、無向グラフと呼びます。反対に向きが意味を持つグラフを有向グラフと呼びます。

プログラムでは、グラフを扱うことはできません。そこで図のようなリストを定義します。グラフと同じ意味を表していて、１さんと２さん、２さんと３さんとの間はFalseにしています。

次は②について考えていきます。今回は対象とするNが10以下と、比較的少ないです。なので10人が走る順番のすべての可能性を考えていきましょう。それは階乗を計算することで得られることが出来、itertoolsモジュールで計算して1通りずつ取得することが出来ます。

それぞれの組み合わせについて、全員ー１人分、後ろの人との関係性を、隣接行列を用いてチェックします。全員分の関係性をチェックして、不仲でなければその組み合わせは解答の候補となります。あとは全探索で最小のかかる時間を計算するだけです。以下がコードになります。

import itertools

n = int(input())
time_list = []
player_list = []

for i in range(n):
    time_list.append(list(map(int, input().split(" "))))
    player_list.append(i)

m = int(input())
adjacency_matrix = [[True for i in range(n)] for j in range(n)]

for i in range(m):
    x, y = map(int, input().split(" "))
    adjacency_matrix[x-1][y-1] = False
    adjacency_matrix[y-1][x-1] = False


min_time = 100000000
for v in itertools.permutations(player_list):
    time_sum = 0
    flag = True
    kukan = 0
    for w in range(len(v)-1):
        if adjacency_matrix[v[w]][v[w+1]] == True:
            time_sum += time_list[v[w]][kukan]
            kukan += 1
        else:
            flag = False

    time_sum += time_list[v[-1]][kukan]

    if time_sum < min_time and flag == True:
        min_time = time_sum

if min_time == 100000000:
    print("-1")
else:
    print(min_time)

おわりに

お疲れ様でした。今回はかなりコードが長いですが、やったことは単純です。隣接行列の考え方は便利そうなので、覚えておくとよいことがあるかもしれませんね。

2022-12-15

競プロ典型90問　020 - Log Inequality（★3）コード解説

はじめに

最近かなり冷え込みますね。今年は12月に入っても割と暖かめだったのに今は皮膚を刺すような寒さです。今年はヒートテックを買おうかなあ…。

さて、今回も競プロ典型90問の★3問題から1問やっちゃいますよ！
今まで★3問題も前から解いていっていたのですが、実は018の「Statue of Chokudai」は飛ばしています。問題自体は解けたんですよ…。ただ、三角関数の問題なので、解説するのが少し面倒くさい…。誰も読んでない零細ブログだからさ…。なのでモチベーションが上がったときに三角関数の表とか用意して記事を書こうと思います。　　　　ささ、気を取り直して今回は「020 - Log Inequality」です！

はじめに
競プロ典型90問
020 - Log Inequality
おわりに

競プロ典型90問

atcoder.jp

020 - Log Inequality

今回はめちゃくちゃシンプルな問題ですね。出力もYesかNoの2通りしかありません。

まずは愚直に式のまま実装してみましょう。
pythonでlog(n)を計算するにはmathモジュールを用います。

import math
a, b, c = map(int, input().split(" "))

if math.log2(a) < b * math.log2(c):
    print("Yes")
else:
    print("No")

結論から言うとこのコードはWAでした。TLEでもなくシンプルに間違いです。

なぜなら、コンピュータは直接logを扱えないので、内部で近似した少数として扱っているからです。その値の多少のずれがプログラムをWAにしているのです。

正しい解法は以下になります。

a, b, c = map(int, input().split(" "))

if a < c**b:
    print("Yes")
else:
    print("No")

対数を理解している必要がありますが、`blogc = logc^b"が成り立ちます。そして対数関数は単調に増加する関数なので、xが増加すればyも増加することになります。つまりlogの引数だけで比べることが出来ます。

おわりに

今回は問題文もコードも短かったので精神衛生上良い問題でしたね！

修論で病んでるのでちょうどよい気晴らしになりました。

お疲れ様でした。

2022-12-14

競プロ典型90問　016 - Minimum Coins（★3）コード解説

はじめに

もう12月の半ばです。12といえば…今週末のM1グランプリですね！

今年、個人的に目が離せないのはヨネダ2000です。結成して2年の女性コンビですが、ネタも振る舞いもとても若手とは思えないクオリティで、斬新すぎるネタは中毒性の塊です。（去年の敗者復活戦のネタを覚えている方もいるのでないでしょうか。）今週末を楽しみに木、金と乗り切っていきましょう！！

さて、今回は競プロ典型90問の★3問題を解説していきます！

競プロ典型90問

atcoder.jp

016 - Minimum Coins（★3）

A円、B円、C円のコインがそれぞれ何枚かあり、それらの合計値がN円になるような組み合わせで、合計枚数が最も少ないものを出力します。

一番オーソドックスなものは、A円のところが10円、50円、100円のように具体的な金額が与えられていることが多いですが、これも同様です。

方針としてはそれぞれのコインの枚数に対して全探索を行い、合計がN円となるタイミングの枚数を記録して、最も少なくなる時の合計枚数を出力します。

愚直にコーディングした場合が以下になります。

n = int(input())
a, b, c = map(int, input().split(" "))

num_coins = n
for i in range(10000):
    for j in range(10000):
        for k in range(10000):
            if a*i + b*j + c*k == N:
                num = i+j+k
                if num < num_coins:
                    num_coins = num 
print(num_coins)

お察しの方もいらっしゃると思いますが、これはTLEとなります。

制約でコインの総数が9999以下ということはわかっているので、各コインについて10000通りの探索を行っていますが、3重ループなので必要な探索数は、(10⁴)³ = 10¹²となります。 1秒間に可能な計算回数の目安は1億回（10⁸）と言われているので、TLEとなるのも仕方がないといえます。

そこでループを減らす方法を考えましょう。
実はaの枚数とbの枚数が決まると、残りのcによってNが実現できるかどうかが決定します。それは、
- N - (a(aの枚数) + b(bの枚数)) % c == 0
- N - (a(aの枚数) + b(bの枚数)) >= 0
の2つの条件によって判断できます。

これによって3重ループが2重ループで実現できるようになります。

n = int(input())
a, b, c = map(int, input().split(" "))

num_coins = n
for i in range(10000):
    for j in range(10000):
        if (n - (a*i + b*j)) % c == 0 and (n - (a*i + b*j)) >= 0:
            num = i + j + (n - (a*i + b*j)) // c
            if num_coins > num:
                num_coins = num
print(num_coins)

実はこのコード、Pythonで実行するとTLEになります。
え？さっき大丈夫って言ったじゃん！！嘘つき！！

安心してください、ACですよ。そうPyPyならね。
高速で動作するPyPy3で実行してみたらACしました。

おわりに

今回は計算量を削減するためにループを減らす問題でした。
かなり応用の効きそうな考え方なので、しっかり復讐しておきましょう。

お疲れ様でした。

2022-12-13

二分探索モジュール bisectの使い方

はじめに

今回は競技プログラミングでPythonを使っていたら、かなりの高頻度で使用するモジュール『bisect』を紹介していきたいと思います。内容は公式のドキュメントを参考にしています。

docs.python.org

はじめに
二分探索アルゴリズム
bisectの使い方
おわりに

二分探索アルゴリズム

bisectは配列二分法アルゴリズムで、簡単に言うと「ある数字を配列に挿入する場合において、何番目の大きさの値であるか」を算出することが出来ます。bisectを使わない場合、
1. 配列をソートする。
2. 数字をソートした配列の要素と前から比べていき、大きくなったところで処理を終了する。
といった流れになります。
ここで 2について考えていきたいです。
ここで説明している 2は「線形探索」と呼ばれるアルゴリズムです。もしも一番初めの要素より挿入する要素が小さければ１回で探索は終わります。しかし一番最後の要素よりも大きかった場合は、その配列の長さと同じだけ探索を行う必要があります。ここで配列の要素数をNとおくと、探索を行う平均回数は1/2 * Nと考えられます。つまり計算回数はNに比例するといえます。これをO(N)と表すことが出来ます。

線形探索よりも性能の良い挿入のアルゴリズムが「二分探索」です。先に計算量から説明すると、このアルゴリズムはO(log N)と表すことが出来ます。logNとNとの間の関係は以下の図で表される通りで、Nが大きくなるにしたがって差は広がっていきます。

アルゴリズムの流れを説明します。

配列の数字の真ん中の数字を見つける。
その数と挿入する数を比較して、小さければ真ん中より前、大きければ真ん中より後ろの配列を次の探索範囲にする。
1. 2を分割できなくなるまで行う。

結構シンプルな考えです。探索範囲が、Nの半分→Nの半分の半分→Nの半分の半分の半分というように小さくなっているので、線形探索よりも効率的なのがよくわかると思います。

計算量がlogNになる証明は以下のようになります。

分割を行う回数をsと置くと、最後に残る要素数は1であるため、

N/2^s = 1

つまり

N = 2^s

であり、底が 2の対数をとると、

s = log2(N)

となります。

bisectの使い方

ここからはコードを中心にbisectモジュールの使い方を解説していきます。

bisect_leftとbisect_rightがありますが、異なる点は、「リストの中に挿入する数字と同じ要素があった場合、それらの中で一番前（左）に挿入するか、後ろ（右）に挿入するか」です。

# モジュールをインポート
import bisect

#サンプルのリスト
sample_list = [3, 2, 3, 1, 6, 5, 2, 1, 5]

#ソート
sample_list = sorted(sample_list)

#output -> [1, 1, 2, 2, 3, 3, 5, 5, 6]

bisect.bisect_left(sample_list, 3)

#output -> 4

bisect.bisect_right(sample_list, 3)

#output -> 6

サンプルのリストを用意して動作の確認を行います。まずソートを行って、２分探索の準備を行います。結果を出力してみると3が2つあることを覚えておいてください。
その後、bisect_leftとbisect_rightを使ってみます。

bisect_leftは3を、3の集合体の一番左に挿入しています。bisect_rightは右に挿入していることがわかります。これが2分探索を使って行われるので線形探索よりも高速です。

おわりに

今回はbisectモジュールについて解説していきました。競プロでは頻出なので、存在だけでも覚えておきましょう。（細かい書式は覚えなくても調べればすぐにわかると思います。）
お疲れ様でした。

2022-12-12

競プロ典型90問　★3 014 - We Used to Sing a Song Together コード解説

はじめに

お疲れ様です。もう12月も半ばになり、年末年始の話をすることも増えてきましたね。
前回、本日から動的計画法（DP）の強化週間にしようと申し上げていたのですが、ちょっとトラブルがあって勉強が進まなかったので、競プロ典型90問の★3問題をやっていこうと思います。
本日も頑張っていきましょ～

はじめに
競プロ典型90問
014 - We Used to Sing a Song Together
おわりに

競プロ典型90問

atcoder.jp

014 - We Used to Sing a Song Together

AGCはたぶん「Atcoder Grand Contest」のことだと思います。めちゃくちゃ難易度が高く一流プログラマの方々がしのぎを削っているコンテストです。~~「AGC街道に住む小学生は性格が悪い」っていうのは意味深ですね。~~

小学生と同じ数だけ（N）小学校があって、それぞれが別の小学校に通うという条件のもと、それぞれの家から学校までの距離を最小化します。

結論から言えば、「家の場所と学校の場所をソートして、家のインデックスが対応する学校に行く」というのが、最も距離の和が短くなる通い方だといえます。コードは短く、以下のようになります。

n = int(input())
a_list = list(map(int, input().split(" ")))
b_list = list(map(int, input().split(" ")))
 
a_list.sort()
b_list.sort()
ans = 0
for i in range(len(a_list)):
    ans += abs(a_list[i] - b_list[i])
print(ans)

おわりに

今回は解説もコードもかなり短くなりましたね。どちらも短いほうが美しいですよね！（コードはともかく解説の手を抜いたわけではないですよ…！）
明日はDPできるといいな～お疲れ様でした。