F - Programming Contest
皆さん、こんにちは！
ハリーです。今回は競プロを始めて以来、精進で初めて F 問題を解くことができたので解説記事を書いていこうと思います。
それでは解いていきましょう！
F - Programming Contest
問題文
高橋くんはプログラミングコンテストに参加します。 このコンテストのコンテスト時間は $T$ 分間で、 $N$ 問の問題が出題されます。
高橋くんは超能力者なので、$ i $ 番目の問題が$ A_i$ 分で解けることが分かっています。
高橋くんは $N$ 問の中から $0$ 問以上を、解くのにかかる時間の総和が $T$ 分以下になるように選び、それらの問題を解きます。
選んだ問題を解くのにかかる時間の総和の最大値を求めてください。
制約
- 入力は全て整数
- $1 \leq N \leq 40$
- $1 \leq T \leq 10^9$
- $1 \leq A_i \leq 10^9$
入力例１
5 17 2 3 5 7 11
出力例１
17
入力例２
6 100 1 2 7 5 8 10
出力例２
33
入力例３
6 100 101 102 103 104 105 106
出力例３
0
入力例４
7 273599681 6706927 91566569 89131517 71069699 75200339 98298649 92857057
出力例４
273555143
実装方法
まず、この問題を実装するにあたって、使用するアルゴリズムは「半分全列挙」と「二分探索」、「bit 全探索」です。そして、bisect というPythonのモジュールを使用します。
半分全列挙
今回の問題を普通に bit 全探索すると計算量が $O(2^N)$ もかかってしまいます。すると、最大の計算量は $2^40$ もかかってしまいます。この計算量を抑えるために半分全列挙を使います。
まず、配列を半分に分けます。そして、分けた配列それぞれを全探索すると計算量は $O(2 × 2^N/2)$ まで抑えることができます。
これが半分全列挙のおおまかな概要です。
参考サイト
それぞれのアルゴリズムと bisect について詳細に解説している、私が参考にしたサイトは以下の 3 つです。
Pythonでの実装
まず初めに、bisect モジュールをインポートします。
import bisect
入力を受け取ります。
N, T = map(int,input().split())
A = list(map(int,input().split()))
配列 A を半分に分けます。
A1 = A[:20]
A2 = A[20:]
次に、分けた配列をそれぞれ bit 全探索していきます。
sum = [0]
for i in range(2 ** len(A1)):
total = 0
for j in range(len(A1)):
if (i >> j) & 1:
total += A1[j]
sum.append(total)
sum2 = [0]
for i in range(2 ** len(A2)):
total = 0
for j in range(len(A2)):
if (i >> j) & 1:
total += A2[j]
sum2.append(total)
bit 全探索で求めたそれぞれの配列の和のリストを昇順にソートします。
sum.sort()
sum2.sort()
最後に二分探索を行い、条件を満たす最大値を探します。
二分探索を行うとき、片方のリストの要素を固定して行います。今回は前半の 20 個の和を保存している配列 sum を固定して探索を行います。そして、最大値を更新していき、最後に出力すれば終わりです。
ans = 0
for i in sum:
if T - i >= 0:
ans = max(ans, i + sum2[bisect.bisect_right(sum2, T - i)-1])
print(ans)
ACコード
import bisect
N, T = map(int,input().split())
A = list(map(int,input().split()))
A1 = A[:20]
A2 = A[20:]
sum = [0]
for i in range(2 ** len(A1)):
total = 0
for j in range(len(A1)):
if (i >> j) & 1:
total += A1[j]
sum.append(total)
sum2 = [0]
for i in range(2 ** len(A2)):
total = 0
for j in range(len(A2)):
if (i >> j) & 1:
total += A2[j]
sum2.append(total)
sum.sort()
sum2.sort()
ans = 0
for i in sum:
if T - i >= 0:
ans = max(ans, i + sum2[bisect.bisect_right(sum2, T - i)-1])
print(ans)
おわりに
いかがだったでしょうか？今回は初 F 問題 AC できたので、興奮してすぐに記事を書いてしまいました！半分全列挙を用いた問題だったのですが、個人的にはとても面白かったです。灰コーダーの私でも解くことができたので、是非皆さんも解いてみてはいかがでしょうか？
それではまた！
C - Counting 2
皆さん、こんにちは！
ハリーです。今回はパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) に出題された C - Counting 2 を解いていきたいと思います。私はコンテスト中にこの問題を解くことができなかったので、しっかりと復習していきたいと思います。それでは、解いていきましょう！
C - Counting 2
問題文
$N$ 人の生徒からなるクラスがあり、$i(1 \leq i \leq N)$ 番目の生徒の身長は $A_i$ です。
$j=1,2,…,Q$ について、以下の質問に答えてください。
制約
- $1 \leq N, Q \leq 2 × 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq x_j \leq 10^9$
- 入力は全て整数
入力例１
3 1 100 160 130 120
出力例１
2
入力例２
5 5 1 2 3 4 5 6 5 4 3 2
出力例２
0 1 2 3 4
入力例３
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
出力例３
5 3 5 5 5
実装方法
bisect のモジュールをインポ―トします。
from bisect import bisect_left
入力を受け取り、A の配列を昇順にソートします。
N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for 文内で入力 $x$ の値を受け取り、bisect_left で昇順にソートされた配列 A の x 以下の人数を取りだし、全体の人数から x 以下の人数を引いた値を出力します。
for i in range(Q):
x = int(input())
print(N - bisect_left(A, x))
ACコード
from bisect import bisect_left
N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(Q):
x = int(input())
print(N - bisect_left(A, x))
おわりに
いかがだったでしょうか？今回の復習で bisect の理解を深めることができたので、良かったです。次も、また別なカテゴリの問題を解いていきたいと思います！
それでは皆さん、また来週！
C - The Kth Time Query
皆さん、こんにちは！
ハリーです。今回は、C - The Kth Time Query を解いていきたいと思います。この問題は HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）で出題された問題です。私もこのコンテストに参加していたのですが、解くことができなかったので復習していきたいと思います！
C - The Kth Time Query
問題文
長さ $N$ の数列 $A = (a_1,a_2,...,a_N)$ があります。
以下で説明される $Q$ 個のクエリに答えてください。
- クエリ $i :$ 整数の組 $(x_i ,k_i)$ が与えられます。$A$ の要素を $a_1 ,a_2 ,…$ と前から順に見ていったときに、数 $x_i$が $k_i$ 回目に登場するのは $A$ の前から何番目の要素を見たときかを出力してください。
ただし条件を満たす要素が存在しない場合は $−1$ を出力してください。
制約
- $1 \leq N \leq 2 × 10^5$
- $1 \leq Q \leq 2 × 10^5$
- $0 \leq a_i \leq 10^9(1 \leq i \leq N)$
- $0 \leq x_i \leq 10^9(1 \leq i \leq Q)$
- $1 \leq k_i \leq N(1 \leq i \leq Q)$
- 入力はすべて整数である。
入力例１
6 8 1 1 2 3 1 2 1 1 1 2 1 3 1 4 2 1 2 2 2 3 4 1
出力例１
1 2 5 -1 3 6 -1 -1
入力例２
3 2 0 1000000000 999999999 1000000000 1 123456789 1
出力例２
2 -1
実装方法
まず初めに、collections ライブラリのimport を行います。
from collections import defaultdict
次に入力を受け取ります。
N, Q = map(int, input().split())
a = list(map(int, input().split()))
ここで、defaultdict を作成して引数に d という関数を設定します。
(※defaultdict の参考記事はこちらです）
d = defaultdict(list)
配列 d の 受け取った a の要素の index 番目に値を加えていきます。
for i in range(N):
d[a[i]].append(i + 1)
$x$ と $k$ を受け取り、d[x] の長さ（length) が $k$ 以上の場合は、d[x] の前から $k$ 番目の値を出力します。d[x] の長さが $k$ 未満の場合は、$-1$ を出力します。この工程を $Q$ 回繰り返します。
for _ in range(Q):
x, k = map(int, input().split())
if len(d[x]) >= k:
print(d[x][k - 1])
else:
print(-1)
ACコード
from collections import defaultdict
N, Q = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(list)
for i in range(N):
d[a[i]].append(i + 1)
for _ in range(Q):
x, k = map(int, input().split())
if k <= len(d[x]):
print(d[x][k - 1])
else:
print(-1)
おわりに
どうでしたでしょうか？今回は defaultdict を使う問題を解いてみました。defaultdict を使った問題はコンテストでもよく出題されるので、しっかり復習することができて良かったです！次の記事でも、もう1問くらい解いていきたいと思います。
ダイクストラ法をPyhtonで書く！
皆さん、こんにちは！
ハリーです。今回は先週の続きでダイクストラ法をやっていきたいと思います。今回のテーマとしては、前回やったダイクストラ法を Python で書いていきたいと思います。それではやっていきましょう～！
ダイクストラ法
ダイクストラ法とは、グラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年にEdsger Dijkstra氏 によって考案されました。
Pythonでの実装
まず、ダイクストラ法を実装するにあたって、ヒープキューを使用します。（ヒープキューとは、要素の追加と最小の要素の取り出しをそれぞれ $O(log N)$ で実行できるデータ構造です）
初めに、heapq モジュールをインポートします。
from heapq import heappush, heappop
次に、始点とノード数を受け取ります。
合計距離を保存するための配列 dist 、距離とノードを入れるための配列 hq 、ノードが確定済みか確認するための配列 check を準備します。
dist = [INF] * n
hq = [(0, s)]
dist[s] = 0
check = [False] * n
では、ダイクストラ法の手順で処理を行います。
1. 今いるノードを取り出します。
2. 訪問済みの True を入れます。
3. if 文で、訪問済みではない、かつ暫定距離より短いかどうかを判定します。
4. 3 の条件に当てはまる場合、距離を更新します。
5. これを繰り返していきます。
while hq:
v = heappop(hq)[1]
check[v] = True
for to, cost in graph[v]:
if check[to] == False and dist[v] + cost < dist[to]:
dist[to] = dist[v] + cost
heappush(hq, (dist[to], to))
return dist
おわりに
いかがだったでしょうか？初めてのダイクストラ法でしたが、個人的には BFS (幅優先探索) よりややこしように感じました。まだまだ理解が足りていませんが、これからいろいろな問題を解いて慣れていこうと思います。これで、私のライブラリが 3つになりました！もっと増やしていきたいですね。来週はテスト週間なのでお休みさせてください！留年をかけた勝負をしてきます....。
それでは、皆さんまた再来週！
ダイクストラ法ってなに？
皆さん、こんにちは！
ハリーです。競プロ精進日記の４週目になります。今回は、新しいアルゴリズムを学んでいきたいと思います。今回、勉強していくアルゴリズムは「ダイクストラ法」です。
それではやっていきましょう！
ダイクストラ法
ダイクストラ法とは、グラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年にEdsger Dijkstra氏 によって考案されました。
例題を見ながら考えていきましょう。
◆例題
ハリーくんの家とＲくんの家があります。ハリーくんは R くんの家に行きたいと思っています。R くんの家に行く道の途中には、いくつか交差点があります。ハリーくんは歩くのがとても嫌いなので、最短の経路で R くんの家に行こうと考えています。歩く速度は一定です。最短で何分で R くんの家に着くことができるでしょうか。
例えば、下記の経路で R くんの家に行くと 14 分で着くことができます。
しかし、最短経路で R くんの家に行くと 9 分で着くことができます。
グラフ理論において、ここで示された交差点(頂点) のことを「ノード」、道(辺) のことを「エッジ」、各道の所要時間を「重み」と呼ばれています。
上記の例題は、「単一始点最短経路問題」という最短経路を求める問題のひとつです。今回の例題は、頂点の数も少なくシンプルな問題でしたが、今回の例題よりも、ノードやエッジの数が増えていくと経路のパターンはもっと増加します。
ダイクストラ法の手順
- スタート点からスタート点までの確定距離を0とする。
- 距離が確定した点と隣り合っている点までの暫定距離とたどる元の点を求める。
（暫定距離 ＝ 確定距離 ＋ 隣り合っている点までの移動距離）
ただし、隣り合っている点の暫定距離がすでに求まっている場合、より短い暫定距離が出た場合のみ上書きする。また、隣り合っている点の確定距離がすでに求まっている場合は無視する（すでに確定してるので更新されない）。 - 暫定距離が出ている点の中で、一番暫定距離が小さいものを確定距離とする。
- すべての距離が確定するまで2, 3を繰り返す。距離が確定した際の経路は、ゴールから元の点をたどっていることで求めることができる。
先ほどの例題でもう一度考えてみましょう。
各ノードに a ～ e の名前をつけます。そして、V（頂点全体集合）と S（頂点集合）、V-S（Sに含まれていない頂点集合）をまとめると下図のようになります。
水色で塗られている点は必要な時間が確定している点です。点の外にある赤字の数字は必要な時間を表しています。
次は、a から行くことができる b、c、d について距離の更新を行います。
b、c、d については、8分、5分、3分で移動できるので各ノードに 8、5、3 の数字が入っています。
上図において、まだ色が塗られていない頂点のうち、最も所要時間が短いものを見ます。今回は d が一番短いので d の経路を考えます。
ここで、d が最も総所要時間が短いことを意識して d に行く経路を考えてみると、他の経路を通った場合の総所要時間は必ず 3 以上になってしまうことがわかります。なので、d を塗りつぶします。そして、d から行ける頂点は e しかないので e を塗りつぶします。最後に、e から f に行くことができるので R くんの家に 14 分で行ける経路があることがわかります。
ここからは、先ほどと同じように所要時間が最も短いものを探します。今回は、 c ですね。
b には既に、a → b の経路があり、総所要時間に 8 が入っていましたが、c を経由すると 7 分で移動できることがわかったため更新します。そして、f にも移動できる道があります。この経路は d → e を経由する時間より短い時間で e に行くことができるので、e の総所要時間を更新します。
この後も、同じことを繰り返します。残りの点は b と f ですが、所要時間が短いのは bなので、b を見ていきます。
b を塗りつぶし、総所要時間を更新するために頂点を見ます。こちらは c → f を経由するより短い時間で行くことができるので、総所要時間を更新します。
これで、a から f までの最短経路を求めることができました。
D - Number of Shortest paths
皆さん、こんにちは！
ハリーです。今回も BFS（幅優先探索）に関連する問題を解いていきたいと思います。いつまで続けるのかって？私が BFS マスターになるまでです！それでは、解いていきましょう！
D - Number of Shortest paths
問題文
AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。
道路 $i$ を通ると都市 $Ai$ と都市 $Bi$ の間を双方向に1時間で移動することができます。
都市 1 から都市 N へ最も早く移動することができる経路は何通りありますか？
答えは非常に大きくなる可能性があるので $(10^9 + 7)$ で割ったあまりを求めてください。
制約
- $2 \leq N \leq 2 × 10^5$
- $0 \leq M \leq 2 × 10^5$
- $1 \leq Ai < Bi \leq N$
- $( Ai, Bi ) $は相異なる
- 入力に含まれる値は全て整数である
入力例1
4 5 2 4 1 2 2 3 1 3 3 4
出力例1
2
入力例2
4 3 1 3 2 3 2 4
出力例2
1
入力例3
2 0
出力例3
0
入力例4
7 8 1 3 1 4 2 3 2 4 2 5 2 6 5 7 6 7
出力例4
4
実装方法
まず初めに、collections ライブラリのimport を行います。
from collections import deque
次に、入力を受け取ります。
まず、NとMの値の入力を受け取り、道路によってつながっている都市を保存する graph 配列を用意します。
n, m = map(int,input().split())
graph = [ for _ in range(n)]
道路によってつながっている都市の入力を受け取り、0-index に値を合わせ 配列 graph に値を入れていきます。
for i in range(m):
a, b = map(int,input().split())
a = a - 1
b = b - 1
graph[a].append(b)
graph[b].append(a)
割ったあまりを出すために mod を用意します。
mod = 10**9 + 7
deque オブジェクトを生成します。そして、最短距離を表すdist 配列と経路の数を表すcnt 配列を作成し、初期値を入れます。
q = deque()
dist = [-1] * n
dist[0] = 0
cnt = [0] * n
cnt[0] = 1
q.append(0)
キューからpopした都市から遷移できる都市が未到達の場合は、移前の距離に1を足して更新します。遷移できる都市jが到達済みの場合でも、最短距離 dist の値が同じであれば cnt[ j ] に遷移前の数を足し合わせることで最短経路の数を更新していきます。
while q:
p = q.popleft()
for i in graph[p]:
if dist[i] == -1:
dist[i] = dist[p] + 1
q.append(i)
cnt[i] = cnt[p]
elif dist[i] == dist[p] + 1:
cnt[i] += cnt[p]
cnt[i] %= mod
最後に、都市Nまでの最短経路の数 cnt[n-1]を出力すれば終了です。
print(cnt[n-1])
ACコード
from collections import deque
n, m = map(int,input().split())
graph = [ for _ in range(n)]
for i in range(m):
a, b = map(int,input().split())
a = a - 1
b = b - 1
graph[a].append(b)
graph[b].append(a)
mod = 10**9 + 7
q = deque()
dist = [-1] * n
dist[0] = 0
cnt = [0] * n
cnt[0] = 1
q.append(0)
while q:
p = q.popleft()
for i in graph[p]:
if dist[i] == -1:
dist[i] = dist[p] + 1
q.append(i)
cnt[i] = cnt[p]
elif dist[i] == dist[p] + 1:
cnt[i] += cnt[p]
cnt[i] %= mod
print(cnt[n-1])
最後に
どうでしたでしょうか？今回も今までやってきたことの応用のような問題でしたね。
早くコンテストで BFS の問題が出題されてほしいです！今週もお疲れ様でした！
それでは皆さん、また来週！
C - Cat Snuke and a Voyage
皆さん、あけましておめでとうございます！！
ハリーです。今回は、前回やった BFS（幅優先探索）に関連する問題を解いていきたいと思います。前回の問題とは形式が違った問題ですが、頑張っていきましょう！
C - Cat Snuke and a Voyage
この問題をやろうと思ったきっかけは、一緒に競プロをやっている友人から BFS を教えてもらった時に、おすすめされたからです。この形式の問題は過去にも何度か出題されているので、しっかりとやっていきたいと思います。
問題の概要
N個の島からなる諸島があり、これらの諸島の間では船の定期便がM種類運行されています。定期便はそれぞれ つの島の間を行き来しており、$i$ 種類目の定期便を使うと、 島 $ai$ と島 $bi$ の間を行き来する事ができます。
すぬけくんは今島 にいて、島 に行きたいと思っています。 しかし、島 から島 への定期便は存在しないので、定期便を つ使うことで、島 に行けるか調べます。
制約
- $3 \leq N \leq 200,000$
- $1 \leq M \leq \leq 200,000$
- $1 \leq ai < bi \leq N$
- $(ai,bi) \neq (1,N)$
- $i \neq j $ ならば $(ai,bi) \neq (aj,bj)$
入力例1
3 2 1 2 2 3
出力例1
POSSIBLE
入力例2
4 3 1 2 2 3 3 4
出力例2
IMPOSSIBLE
入力例3
100000 1 1 99999
出力例3
IMPOSSIBLE
入力例4
5 5 1 3 4 5 2 3 2 4 1 4
出力例4
POSSIBLE
実装方法
まず初めに、collections ライブラリのimport を行います。
from collections import deque
次に、入力を受け取ります。
まず、NとMの値の入力を受け取ります。さらに、島くを行き来することができるかの判定を行うための、INF の設定と行き来できる島を保存するための配列を作ります。
n, m = map(int, input().split())
INF = 10**18
graph = [ for _ in range(n)]
次に、行き来できる島を受け取り 0-index に値を合わせ 配列 graph に値を入れていきます。
for i in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
入力例1の場合だと、graph の要素は下記のような感じになっています。
3 2
1 2
2 3
[[1], [0, 2], [1]] # graphの中身
距離を保存するための配列を用意します。初期値として、各要素に INF を入れます。
そして、deque オブジェクトを生成します。生成したら初期値の 0 を入れます。
dist = [INF] * n
q = deque()
q.append(0)
dist[0] = 0
ここの while 文は前回やった幅優先探索の while 文とほとんど一緒で、条件分岐がひとつ減っただけです。INF が入っている場所は行き来することができない場所なので、無視するということになります。
while q:
v = q.popleft()
for i in graph[v]:
if dist[i] != INF:
continue
dist[i] = dist[v] + 1
q.append(i)
最後に、たどり着けるかどうかの判定を行います。
今回の問題では島 N に定期便を 2 つだけ使うことで、たどり着けるかどうかなので、dist の N-1 番目の要素が 2 以下であればたどり着けるということになります。
if dist[n-1] <= 2:
print('POSSIBLE')
else:
print('IMPOSSIBLE')
ACコード
from collections import deque
n, m = map(int, input().split())
INF = 10**18
graph = [ for _ in range(n)]
for i in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
dist = [INF]*n
q = deque()
q.append(0)
dist[0] = 0
while q:
v = q.popleft()
for i in graph[v]:
if dist[i] != INF:
continue
dist[i] = dist[v] + 1
q.append(i)
if dist[n-1] <= 2:
print('POSSIBLE')
else:
print('IMPOSSIBLE')
最後に
もう2021年がおわり、2022年になりましたね。皆さんが今年の目標や抱負などはあるでしょうか？私は今年、就職活動があるのでいろいろと大変な1年になりそうです...。今年は競プロも就活も両立して頑張りたいと思います。あと、卒業研究もですね...。ではでは、皆さんの1年が良い1年になりますように！それでは皆さん、また来週！
