2022-12-11

競プロ典型90問　007 - CP Classes（★3）コード解説

はじめに

お疲れ様です。私事ですが、昨日Netflixを契約しました！今までアマプラで十分かな～とか思って契約してなかったけど、いざ契約してみたら見たかったものがあれもこれも…。ジョジョ6部にヴァイオレットエヴァーガーデン、バキ、etc...。これは年末まで忙しくなりそうですね！

さて、本日は競プロ典型90問の★3問題から『007 - CP Classes』を解説していきたいと思います。

はじめに
競プロ典型90問
007 - CP Classes（★3）
コード
おわりに

競プロ典型90問

atcoder.jp

007 - CP Classes（★3）

競技プログラミングの塾には、クラスのレーティングと生徒のレーティングがあり、各生徒のレーティングとその生徒が所属するクラスのレーティングの差が最小になるようにするという問題です。

考え方としては、各生徒のレーティングとそれぞれのクラスとの差を取って不満度を計算して最小の不満度を算出し、それを合計するといったものです。しかし、そのまま実装しようと思ってもTLEとなってしまいます。

ここで、少し考え方を変更する必要があります。

自分のレートに最も近いクラスを見つけるには、全てのクラスのレートと比べるのではなく、「クラスをレートが低い順に並べたときに、自分のレーティングはどのクラスに一番近いのか」を考えていきます。以下に流れを示します。

クラスのレーティングを低い順に並べる。
自分のレーティングがどのクラスの間にあるのかを調べる。
その2つのクラスのレーティングと自身のレーティングを比較して、小さいほうを不満度として加算する。

ここで2について、２分探索というアルゴリズムを用いることで、効率的にどのクラスの間に値を挿入できるかを求めることが出来ます。２分探索のアルゴリズムの詳細については解説しませんが、Python ではbisectライブラリで簡単に実装することが出来ます。

コード

from bisect import bisect_left
 
n = int(input())
a_list = list(map(int, input().split(" ")))
q = int(input())
a_list.sort()
 
for i in range(q):
    b = int(input())
    if b <= a_list[0]:
        distance = abs(a_list[0] - b)
        print(distance)
    elif b >= a_list[-1]:
        distance = abs(a_list[-1] - b)
        print(distance)
    else:
        x = bisect_left(a_list, b)
        distance = min(abs(b - a_list[x]), abs(b - a_list[x-1]))
        print(distance)

おわりに

今回は競プロ典型90問の★3問題を解説していきました。次回以降ですが、ABC281の解けなかったD問題が動的計画法で解けるらしいので、そちらを本格的に学習していこうかなと考えています。お疲れ様でした。

2022-12-10

Atcoder Beginner Contest 281コード解説[A, B, C]

はじめに

本日はAtcoder Beginner Contest 281に参加してきました。
成績はAからCの3問正解で今回もDは解けませんでした・・・。解説を見てみると動的計画法を使っていましたので、そちらの学習をしていこうかなと決意したのがさっきのことです。
今回は自分が解けた3問を解説していこうと思います。

はじめに
Atcoder Beginner Contest 281
A - Count Down
B - Sandwich Number
C - Circular Playlist
おわりに

Atcoder Beginner Contest 281

atcoder.jp

試験期間じゃなくてもいつでも問題を解くことはできます。

A - Count Down

0からNまでの数字をカウントダウンで出力するだけです。

n = int(input())
 
for i in range(n, -1, -1):
    print(i)

B - Sandwich Number

与えられた文字列が、 2つの英大文字で6桁の数字が挟まれているかを判定します。ここでは以下の流れで判定します。 - 長さが全体で8 - 1番目（インデックスは0）が大文字 - 2番目から7番目の要素が数字で100000以上999999以下 - 8番目の要素が大文字これらすべてを満たしているものがYesとなります。

s = input()
flag = False
if len(s) == 8:
    if s[0].isupper():
        if s[1:7].isdigit():
            if 100000 <= int(s[1:7]) <= 999999:
                if s[7].isupper():
                    print("Yes")
                    flag = True
 
if flag == False:
    print("No")

C - Circular Playlist

音楽がループ再生されている場所で、今の時間の曲と、その曲が始まってからの時間を答える問題です。まずはどの曲が流れているかについて考えます。

まず1ループにおいて、aの各曲が終わるまでに、ループ開始から数えてどれだけ時間がたっているかを計算します。これを累積和といいます。ある要素に対する累積和は、（ある要素）＋（前の要素の累積和）で計算できます。
（例）

#入力
180 240 120

#累積和
180 420 540

この累積和の最後の値が、１ループにかかる時間を意味しています。

1ループの時間がわかったところで、現在(T)が何番目のループが始まってからどれくらい経つかを考えていきましょう。（何番目のループなのかは今回のコードでは必要ありません。）

# 何番目のループか
T// (1ループの時間)
# そのループが始まってどのくらいか
T % (1ループの時間)

これで求めることができます。

T % (1ループの時間)経過時に流れている曲は、累積和のリストに対して2分探索を行うことで実装しました。

#累積和
180 420 540

# T % (1ループの時間) に流れている曲が何曲目かを判断するために2分探索を用いる。今回の例では300の時を考える。

180 300 420 540

# どこに挿入されるかがわかると、今が何曲目か判断できる。今回は1曲目終了時と2曲目終了時の間にあるため、今は2曲目が流れていることがわかる。

今が何曲目かわかれば後はその曲が始まった時間と現在の時間を引けばよい。

import bisect
n, t = map(int, input().split(" "))
a_list = list(map(int, input().split(" ")))
 
a_list_ruisekiwa = [a_list[0]]
 
for i in range(1, n):
    a_list_ruisekiwa.append(a_list[i] + a_list_ruisekiwa[-1])
 
one_loop = a_list_ruisekiwa[-1]
 
idx = bisect.bisect(a_list_ruisekiwa, t%one_loop)
 
ans = []
ans.append(idx + 1)
if t % one_loop < a_list_ruisekiwa[0]:
    ans.append(t%one_loop)
else:
    ans.append(t%one_loop - a_list_ruisekiwa[idx-1])
 
print(" ".join(map(str, ans)))

おわりに

次は絶対D問題を解く！！

2022-12-09

競プロ典型90問★3コード解説　002 - Encyclopedia of Parentheses

はじめに

今回から競プロ典型90問の★3問題に挑戦していきたいと思います。★2よりもかなりアルゴリズムが複雑になるので、しっかり解説していきたいと思います。
ですので、★2問題の時は毎日2問解説していましたが、これからは毎日1問ずつ解説していきます。丁寧に解説するためです！~~決して文字数が多くなって面倒くさいわけではないです。~~

はじめに
競プロ典型90問
002 - Encyclopedia of Parentheses（★3）
bit全探索とは
実装
おわりに

競プロ典型90問

atcoder.jp

002 - Encyclopedia of Parentheses（★3）

問題文だけ見るとわかりにくいですが、例を見てみるとわかりやすいですね。つまりかっこが破綻しないように(と)を、長さがNになるように配置していくという問題です。

この問題で注目したい点は2点あり、 - 文字が(と)の2通り - 文字列の長さが最大20

です。このように選択肢が2通りで探索範囲が狭い場合は、
bit全探索という手法を用いるとうまくいくことが多いです。

bit全探索とは

bit全探索とは、考えられる範囲の0と1の組み合わせをすべてに対して操作を行うアルゴリズムです。探索する範囲は、Nの最大値が20なので 2²⁰ = 1048576であり、そこまで大きな数字ではありません。（Pythonが1秒間に1億回計算できると言われています。）
今回の問題では(を1に、)を0に対応させます。
以下の流れで問題を解いていきます。

あるN桁の2進数について、前から0, 1の数を数える。
0の数が1の数を超えたらその2進数は除外（()が破綻しないためには、)が(より先に多く出現してはならない。）
0の数と1の数が等しければ解答に加える。
上記をN桁の自然数すべてに行う。

コードを見ながら詳しく解説していきます。

実装

n = int(input())
ans = []
for i in range(2**n):
    sample = bin(i)
    sample = sample[2:]

    cnt1 = 0
    cnt0 = 0

    if len(sample) == n:
        for j in range(n):
            if sample[j] == "1":
                cnt1 += 1
            else:
                cnt0 += 1
            if cnt1 < cnt0:
                break
        if cnt1 == cnt0:
            sample = sample.replace("1", "(")
            sample = sample.replace("0", ")")
            ans.append(sample)
print(*ans, sep="\n")

0から2^Nまでのすべての整数に対して、2進数にします。整数を2進数にするにはbin()が便利で、0b1001のような形式（str型）で返してくれます。2進数の部分は前の2文字を除外したものになります。

ループ内において、桁数がNの2進数においてのみ、前から0と1の出現回数をカウントします。ここで、0が1の個数を超えると処理を終了させています。処理終了時に0と1の数が等しければ()が破綻しないと考えることができます。

そして0と1を()に置き換えれば処理が終了です。

お疲れさまでした。

おわりに

今回は bit全探索を使って競プロ典型90問の002を解いていきました。★2に比べてかなり難易度は上がっていると感じています。
またbit全探索ですが、2進数のシフトと論理和を用いて行う方法もあるようですね。そちらの方法も面白そうなので今度調べたいと思います。

2022-12-08

楽しく実装しながらプログラミング学習！『アルゴ式』の紹介

はじめに

今回は最近ハマっているWebサイト、『アルゴ式』を紹介します。
プログラミング学習用のサイトで、現在はベータ版ですがすべて無料で、楽しみながらゲーム感覚でプログラミングやアルゴリズムの学習をすることが出来ます。
この記事を読んで興味をもっていただけたなら是非登録してみてください。

はじめに
アルゴ式とは
登録方法
登録したらまず最初に

アルゴ式とは

algo-method.com

プログラミングや情報科学をコツコツ学べる「教科書」
学んだ内容をゲーム感覚で大量に実践できる「練習問題」
の2つで構成される、Web上で完結した学習コンテンツです。（Webサイト上の紹介文）

まさにその通りで、教科書で学習した内容を、記憶が温かいうちに大量に練習問題を解くことが可能です。個人的にこのサイトの良いと感じたところをまとめます。
登録が簡単
すべてWeb上で完結できるので、環境構築など面倒なことが必要ない
有名どころのプログラミング言語はほとんど網羅している。
簡単な問題から徐々に難しくなっていくというようにステップアップしていけるので、自信がついていく。
入力の受け取り方や計算量の制約など、Atcoderと同様なので、その練習になる。

登録方法

以下のURLにアクセス

https://algo-method.com/users/new

新規登録
Twitterアカウントかメールアドレスがあれば登録できる。すぐおわるので使っている人はTwitterアカウントで新規登録するのがおススメ。
アルゴ式　新規登録画面

登録したらまず最初に

登録したらまず最初に、『コンテンツ』タブからコンテンツ一覧を見てください。こちらが現在提供されているものです。この画面まで来たら後は左上から順にやっていけばよいと思います。特にAtcoderなどの競技プログラミングに興味のある人はハマると思いますよ。

2022-12-07

競プロ典型90問　★2問題コード解説[5]

はじめに

競プロ典型90問　★2問題のコード解説は今回で最後になります。
難易度の目安として、★2問題が安定して解けるようになれば茶色くらいの実力はあるとされています。やっとスタートラインに立てたって感じですね。本当のスタートラインはレートで茶色になったときの気もしますが…。
何はともあれ本日も頑張っていきましょう！

はじめに
競プロ典型90問
067 - Base 8 to 9（★2）
078 - Easy Graph Problem（★2）
おわりに

競プロ典型90問

atcoder.jp

067 - Base 8 to 9（★2）

この問題は、8進法の整数Nについて、まずは9進法に直します。そして8を5に変換します。9進法に出てくる数字で一番大きい数字は8なので、それを5に直すということは、出てくる一番大きい数字が7になるということであり、8進法として解釈することが出来ます。それで得た8進法の整数について同様の操作をK回行う、という問題です。8進数を9進数に直接変換するのは大変そうですよね。
解法は以下のように表せます。

8進数を10進数に変換する。
10進数を9進数に変換する。
8 -> 5に変換する。

ここで便利なのがint関数です。int(str(8進数), 8)とすることで、8進数を10進数に変換することが出来ます。10進数を9進数に変換する方法は、数学Aで学習したと思いますが、9で割った余りを下の桁から並べていくことで実現できます。

以下、コードになります。

n,k = map(int, input().split(" "))
 
number8 = n
 
def number10_to_number9(num10):
    num9_list = []
    while True:
        num9_list.append(num10 % 9)
        num10 //= 9
        if num10 == 0:
            num9_list.reverse()
            return "".join(map(str,num9_list))
 
for i in range(k):
    number10 = int(str(number8), 8)
    number9 = number10_to_number9(number10) #str型
    number8 = number9.replace("8", "5")
 
print(number8)

また、例のごとくこちらのコードもPyPy3で実行しています。再帰が入らないコードはPyPyを使うのが丸いんじゃないかと思っています。

078 - Easy Graph Problem（★2）

N頂点M辺の無向グラフが与えられており、ある頂点より頂点番号が小さい隣接頂点が1つ存在するような頂点の数を求める問題です。接続のが与えられる都度、頂点番号をキーとしたディクショナリの要素に、隣接する頂点を追加します。この時、自身の頂点番号より頂点番号が低いときのみ、リストに追加してください。
なお、この問題では頂点の数が与えられているため、あらかじめdict型を用意するということもできましたが、defaultdictを使用しております。dafaultdictは存在しないキーが検索された場合、そのキーの要素がデフォルトのものに設定されるというものです。

from collections import defaultdict
n, m = map(int, input().split(" "))
 
d = defaultdict(lambda:[])
 
for i in range(m):
    a, b = map(int, input().split(" "))
 
    if a < b:
        d[b].append(a)
    elif b < a:
        d[a].append(b)
 
cnt = 0
for key, val in d.items():
    if len(val) == 1:
        cnt += 1
print(cnt)

おわりに

さて、これで★2問題は終了です。お疲れ様でした。かなり寒くなっておりますが、体調にお気をつけて。

2022-12-06

競プロ典型90問　★2問題コード解説[4]

はじめに

もう冬も本番になってきましたね。
買い物に行くと、店内BGMがクリスマスソングだったり、長靴に入ったお菓子が売られていたりと、年末を実感しますね。
本日も競プロ典型90問から★2問題を2問、解説していきたいと思います！

はじめに
競プロ典型90問
055 - Select 5（★2）
061 - Deck（★2）
おわりに

競プロ典型90問

atcoder.jp

055 - Select 5（★2）

直感的な解法としては、N個の整数から5つ数字を選んで、それがPで割れるかどうかを判定する、というのを5つ選ぶ組合せの数だけ行う、ということが考えられます。
しかし、競プロ的な考え方だと、５重ループは計算量が多すぎてTLEになってしまうのではないか、と考えるのが自然です。
しかし、実は５重ループでも、今回は5<=N<=100という制約があったり、ループ内の処理が簡単だということで、制限時間内に実行することが出来ます。

Pythonでは、itertoolsライブラリのcombinationsを用いて組み合わせを出力することが出来ます。組合せの計算はnC5 = 1/120 * N^5となり、５重ループと同等の計算量となります。

実は、このコード、言語をPythonとして実行すると、TLEになってしまいます。ですので、提出の際は、言語をPyPy3（現行では7.3.0）に設定して実行してください。

PyPy3は、ざっくりいうと通常のPythonより高速に動作する（ことが多い）処理系です。再帰が含まれるようなコード以外はPyPy3で実行するのが良いかもしれません。（PyPy３に関しては勉強中です…詳しいことはよくわかっていません…）

以下がコードになります。

from itertools import combinations
N, P, Q = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for a, b, c, d, e in combinations(A, 5):
    if a % P * b % P * c % P * d % P * e % P == Q: 
        ans += 1
print(ans)

061 - Deck（★2）

tの値に応じて、カードを上に入れるか下に入れるか、という問題です。
リストの初めをデッキの上、後ろをデッキの下という風に考えていきたいのですが、リストの頭に要素を挿入するのは意外と難しいです。
そこでPythonにはdepueという便利なモジュールがあります。
deque型はリスト型のappend()で後ろに追加するのと同様に、前に要素を追加することが出来ます。これによって、tの値に応じてカードを上に入れるか下に入れるかを簡単に実装することが出来ます。
以下、コードです。

from collections import deque
 
q = int(input())
d = deque()
 
for i in range(q):
    t, x = map(int, input().split(" "))
    if t == 1:
        d.appendleft(x)
    elif t == 2:
        d.append(x)
    else:
        print(d[x-1])

おわりに

ここまでご覧いただき、ありがとうございました。競プロ典型90問の★2問題は次回で最後となります。以降は★3問題の解説やブックレビューをしていこうかなと考えています。

2022-12-05

競プロ典型90問　★2問題コード解説[3]

はじめに

本日も競プロ典型90問から2問解説していきますよ～。何気に今日でブログの更新も１週間目、珍しく３日坊主から脱却しています。素晴らしい！！

以下が本日のメニューです。

はじめに
競プロ典型90問
027 - Sign Up Requests
033 - Not Too Bright（★2）
おわりに

競プロ典型90問

atcoder.jp

低橋くんが運営しているサイトのユーザ登録に関する問題です。ユーザネームがすでに存在する場合のみ登録を受理するという、ネトゲとかによくある仕様ですね。
~~そういえばAtcoderの開発者の名前って…~~

この問題の解法としては、 1. 名簿となるリストを用意する。 2. 名前が入力されたとき、名簿にその名前がなければ名簿に追加する。 3. 最終的に名簿を出力します。

以上を正直にコードに起こすと以下のようになります。

n= int(input())
user_list = [input() for i in range(n)]
meibo = []
 
for i in range(n):
    if user_list[i] not in meibo:
        meibo.append(user_list[i])
        print(i+1)

こちらのコードは一見正しそうに見えます。しかしこれだとTLE（時間切れ）してしまいます。理由はリストにあり、リストの中にある要素があるかどうか調べるin演算子は計算量がO(N)かかります。not in演算子でも同様だと思います。
そこで、リストの代わりに集合を扱うset型で名簿を用意します。
set型はin演算子をO(1)~O(N)で扱うことが出来ます。

以下がAC（正解）したコードになります。

n= int(input())
user_list = [input() for i in range(n)]
meibo = set()
 
for i in range(n):
    if user_list[i] not in meibo:
        meibo.add(user_list[i])
        print(i+1)

033 - Not Too Bright（★2）

イルミネーションが明るすぎないように、間をあけてLEDを配置するといった問題です。２×２の領域内にLEDが１つだけになるようなイルミネーションでLEDの個数が最大の場合を考えます。
また、２×２を満たさない場合、つまり１×NやN×１の場合は、N個のLEDを照らすことが出来ます。

この問題のカギは、縦横の最大点灯数を考えることです。
もしも縦の長さが3~4ならば、縦に配置できるLEDの最大の個数は2個です。横が5~6ならLEDの最大数は3個です。この場合、配置できるLEDの最大数は２×３の６個となります。
以下がコードになります。

h, w = map(int, input().split(" "))
 
if h == 1 or w == 1:
    print(max(h, w))
else:
    tate = (h+1)//2
    yoko = (w+1)//2
    print(tate*yoko)

おわりに

ここまでお読みいただきありがとうございました。
競プロ典型90問の★2問題も残り4問となってきました。
そのあとはどうするか現在考え中です。★3問題を解説するのもアリですが、かなり解説に文字を割く必要があるため、１日２問はきついかな～、なんて。
ABCの過去問のA~C問題とかやりましょうかね。

はじめに

競プロ典型90問

007 - CP Classes（★3）

コード

おわりに

はじめに

Atcoder Beginner Contest 281

A - Count Down

B - Sandwich Number

C - Circular Playlist

おわりに

はじめに

競プロ典型90問

002 - Encyclopedia of Parentheses（★3）

bit全探索とは

実装

おわりに

はじめに

アルゴ式とは

登録方法

登録したらまず最初に

はじめに

競プロ典型90問

067 - Base 8 to 9（★2）

078 - Easy Graph Problem（★2）

おわりに

はじめに

競プロ典型90問

055 - Select 5（★2）

061 - Deck（★2）

おわりに

はじめに

競プロ典型90問

027 - Sign Up Requests

033 - Not Too Bright（★2）

おわりに