2021-05-31

ABC203 C問題 Friends and Travel costs を工夫してシンプルに解く

ABC203 C問題を解説します。基本的には公式解説と同じ方針です。

問題の概要

$10^{100} + 1$ 個の村があり、1円払うと1つ先の村へ行けます。
友達がいる村 $A_i$ では $B_i$ 円もらえます。
1つの村に複数友達がいる場合もあります。
何番目の村までたどり着けるか求める問題です。

難しいポイント

村の数が $10^{100} + 1$ と多いのと、友達がいる村も最大で $10^{18}$ で多いです。
例えば、友達のいる場所と金額を連想配列に保存して、到達した村まででもらえるお金を合計するなんてことをやろうとすると、
すぐに $10^{18}$ の地獄に引きずり込まれます。

解き方の方針

私は遠回りしながら解法に辿り着きましたが、現実的な制約が友達の数 $1 \leq N \leq 10^5$ に着目すると割と思いつくかもしれません。

村は1円ずつ消費しながら1個ずつ進むので、友達のいる村に到達できないことはあっても飛び越すことはないです。
5番目の村で6円持ってたら、必ず $5 + 6 = 11$ 番目の村に到達できます。

まず友達の位置と友達からもらえる金額を配列に保存して、位置でソートします。
到達できる位置を変数にしておきます。
友達の配列をループして、到達できる位置と友達の位置を比較して、到達できる位置の範囲に友達がいれば、金額の分だけ到達できる位置を足します。
最後に到達できる位置を出力します。

実装

N, K = map(int, input().split())
b_arr = [list(map(int, input().split())) for _ in range(N)]

b_arr = sorted(b_arr)
until = K

for b in b_arr:
    if until >= b[0]:
        until += b[1]

print(until)

遠回りして時間をロスしてしまいました。。。
もっと問題解いてると割とすぐに気づくんだろうなと思いました。

2021-05-23

ABC202 D問題 aab aba baa をメモして解く

ABC202 D問題を解説します。
基本は公式解説と同じですが、具体例を書きながら解説します。

atcoder.jp

問題

A 個の a と B 個の b からなる長さ $A + B$ の文字列のうち、辞書順で K 番目のものを求めてください。

難しいポイント

AもBも最大で30なので、全量は列挙しきれません。
なので辞書順でKという情報から文字列を求めないといけませんが、どうやって。。。
何かしら閃くために具体的に書き出すと ${}_n C_r$ が見えては来ますが。。。

解き方の方針

まずは"a"か"b"を頭からつけて導くことを考えます。
具体的にA = 2、B = 3のケースを列挙してみます。
1. aabbb
2. ababb
3. abbab
4. abbba
5. baabb
6. babab
7. babba
8. bbaab
9. bbaba
10. bbbaa

書き出してみると、先頭にaがくるケースは、その後に続く文字のバターン数になっていることがわかります。
この場合では、残り4文字で $A=1, B=3$ のパターンの数です。つまり4つの中から1つのaが入る組み合わせの数 ${}_4 C_1 = 4$ です。
先頭にbがくるケースは、残り4文字で $A = 2, B = 2$ のパターン数。 ${}_4 C_2 = 6$ です。
なので先頭にaが来るのは、Kが ${}_4 C_1 = 4$ 以下の時になります。そうでない場合はbです。

1文字目が決まったので、2文字目の場合も同様に処理していきたいのですが、注意が必要です。
Kを具体的に示しながら、解説します。
K = 4だとしたら、1文字目は"a"です。2文字目を考える時に、さっきのように残り3文字でパターン数を考えます。
ここで注意が必要なのは、2文字目が"a"の時にそれ以降は"bbb"になるパターンです。
2文字目に"a"が来る場合は1パターン、"b"が来る場合は ${}_3 C_2 = 3$ で3パターンです。

単純に数式では表現できないということがわかったので、2次元配列にメモします。
aの残りの数とbの残りの数が与えられた時のパターン数memo[a][b]を求めます。
aかbのどちらかが0の時は"aa"や"bbb"などの1パターンしかないので、1になります。
他の場合は、 ${}_{a+b} C_{a}$ などの組み合わせの数になりますが、パスカルの三角形（二項定理）の要領で左隣と上の数字を足して求めます。
ja.wikipedia.org

もう1つ罠があるので先頭に"b"が来るパターンも考えます。
K=8のパターンをみていきます。
最初に"b"がくる場合は、2文字目を考えるときにKの値に注意が必要です。
K=8のまま考えると、a=2、b=2の時に8番目の数を選ぶということになってしまいます。
ここでは先程の先頭が"a"かどうかの閾値 4を考慮にいれて、 $8 - 4 = 4$ という数にKを更新してあげます。

実装

たかだか30文字なので再帰処理で実装しました。

A, B, K = map(int, input().split())

# memo[a][b] aがa個, bがb個の時の場合の数
memo = [[0 for _ in range(31)] for _ in range(31)]
memo[0][0] = 1
for i in range(A + 1):
    for j in range(B + 1):
        if i == 0:
            memo[i][j] = 1
            continue
        if j == 0:
            memo[i][j] = 1
            continue
        memo[i][j] += memo[i][j - 1] + memo[i - 1][j]


# 残りa文字、残りb文字の時にk番目の文字列
def get_S(a, b, k):
    if a == 0:
        return "b" * b
    if b == 0:
        return "a" * a
    if memo[a - 1][b] >= k:
        return "a" + get_S(a - 1, b, k)
    if memo[a - 1][b] < k:
        return "b" + get_S(a, b - 1, k - memo[a - 1][b])


print(get_S(A, B, K))

2021-05-16

ABC201のC問題 Secret Numberを解く

ABC201のC問題を解説します。

atcoder.jp

問題

高橋くんは、暗証番号を忘れてしまいました。暗証番号は 0 から 9 までの数字のみからなる 4 桁の文字列で、0 から始まる場合もあります。
0 から 9 までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ 10 の文字列 $S_0, S_1, \dots, S_9$ によって表されます。
$S_i$ が o のとき : 数字 i は暗証番号に確実に含まれていた。
$S_i$ が x のとき : 数字 i は暗証番号に確実に含まれていなかった。
$S_i$ が ? のとき : 数字 i が暗証番号に含まれているか分からない。
高橋くんが忘れてしまった暗証番号としてあり得るものは何通りありますか？

難しいポイント

3桁以下の数字は頭に0がつくのは、どう処理しようか悩みました。
文字列で数字が含まれているか判定しようか、各桁の数字を抜き出して数字として判定しようか、地味に迷いました。

解き方の方針

4桁なので、0から9999まで全量を探索して、条件に合ってるものをカウントします。

実装

数字は文字列に変換して、oがついた数字が全て含まれているか、xがついた数字が含まれていないことを確認します。
3桁以下の数字については頭に0がつくことが確定なので、0がxの場合、暗証番号の可能性は無くなります。
0がoの時はスルーして次の文字を検索にまわします。

判定する関数は以下のようになりました。

def is_num_ok(num: str) -> bool:
    for o in ok_num:
        if o == '0' and len(num) <= 3:
            continue
        if not(o in num):
            return False
    for n in ng_num:
        if n == '0' and len(num) <= 3:
            return False
        if n in num:
            return False
    return True

最終的なコードは以下のようになりました。

S = input()
ok_num = []
ng_num = []

count = 0

for i, s in enumerate(S):
    if s == 'o':
        ok_num.append(str(i))
    if s == 'x':
        ng_num.append(str(i))


def is_num_ok(num: str) -> bool:
    for o in ok_num:
        if o == '0' and len(num) <= 3:
            continue
        if not(o in num):
            return False
    for n in ng_num:
        if n == '0' and len(num) <= 3:
            return False
        if n in num:
            return False
    return True


for j in range(10000):
    str_j = str(j)
    if is_num_ok(str_j):
        count += 1

print(count)

意外と方針はすぐに思いつきましたが、もっと早く解けるようになりたいと思いました。

2021-05-10

ABC200のC問題 Ringo's Favorite Numbers 2 を工夫して解く

ABC200のC問題を解説します。

atcoder.jp

問題

200 という整数が大好きなりんごさんのために、次の問題を解いてください。
N 個の正整数からなる数列 A が与えられるので、以下の条件をすべて満たす整数の組 (i, j) の個数を求めてください。
$1\leq i \lt j \leq N$
$A_i − A_j$ は 200 の倍数である。

難しいポイント

Nの個数が最大で $2\times10^5$ なので、単純な全探索ではタイムオーバーします。
200の倍数というところから計算量を減らす方法に気づけるかどうかがポイントかと思います。

解き方の方針

ポイントになるのは $A_i − A_j$ は 200 の倍数という条件なので、余りだけに着目すれば良いことになります。
余りだと数字の範囲は0から199の範囲になります。
数列Aを全部200で割った余りに変換します。

引き算して200の倍数になるのはどういう余りの組み合わせになるか考えます。
例えば、余り1の数字があったときに、そこから0から199の間でどういう余りの数字を引けば200の倍数になるでしょうか。
そういうことを考えると余り1の数字から余り1の数字を引くしかないことがわかります。他の余りの数字を引いても200の倍数にはなりません。
なのでそれぞれの余りについて、同じ余りの数字から2つ選ぶ組み合わせの数を足した数が答えになります。

実装

実装は特別難しいことはしていません。

N = int(input())
a_arr = list(map(int, input().split()))
amari = [0 for i in range(200)]
for a in a_arr:
    amari[a % 200] += 1

ans = 0
for i in range(200):
    ans += (amari[i] * (amari[i] - 1)) // 2

print(ans)

2021-05-09

ABC200のD問題 Happy Birthday! 2 を工夫して解く

残念ながらABC200のD問題を解けなかったので、解説しつつふりかえります。

atcoder.jp

問題の概要

N 個の正整数からなる数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。以下の条件を全て満たす 2 つの数列
$B = (B_1, B_2, \dots, B_x), C=(C_1, C_2, \dots, C_y)$ が存在するか判定し、存在する場合はひとつ出力してください。
（省略）
$(A_{B_1} + A_{B_2} + \dots + A_{B_x})$ を200で割ったあまりと、 $(A_{C_1} + A_{C_2} + \dots + A_{C_y})$ を200で割ったあまりが等しい

$A = (A_1, A_2, \dots, A_N)$ の中から200で割った余りが等しくなる足し算の組み合わせが2組以上あるかどうか判定して、あればそれを出力、なければ'No'と出力する問題です。

難しいポイント

Nが最大で200なのですが、足し算の組み合わせを単純に考えると $2^{200}$ となり、とてつもない数になります。
何かに気づいて間引かないといけないです。

解き方の方針

公式解説の「鳩の巣原理」は気づかなかったです。。。
余りのパターンとしては200で割ったあまりなので、0から199の200通りしかありません。
なので少なくとも201個合計のパターンあれば、2組のパターンが存在してそれが答えになります。
それを考えると、ビット全探索で $2^{200}$ までやる必要はなく、数列の中に同じ数字はないので $2^{8} = 256$ まで全探索すれば必ず答えはあるはずです。
なければ'No'と出力します。

実装

2次元配列で、同じ余りになる組み合わせを記録しました。
例えば、ans_list[5] = [1, 2, 5] の時は、a_arr[0]+a_arr[1]+a_arr[4]の余りが5になるように記録します。

N = int(input())
a_arr = list(map(int, input().split()))
# 2**8の中で答えの組み合わせがある。Nが8より小さければ全通り探索する
n = min(N, 8)
# 同じ余りとなる組み合わせのリストを保存するリスト
# ans_list[5] = [1, 2, 5] はa_arr[0]+a_arr[1]+a_arr[4]の余りが5になる
ans_list = [[] for _ in range(200)]
for bit in range(2**n):
    tmp_sum = 0
    tmp_list = []
    for i in range(n):
        if bit & (1 << i):
            tmp_sum += a_arr[i]
            tmp_list.append(i + 1)
    amari = tmp_sum % 200
    # 同じ余りの組み合わせがあれば答えを出力して終了する
    if len(ans_list[amari]):
        print('Yes')
        print(len(ans_list[amari]), *ans_list[amari])
        print(len(tmp_list), *tmp_list)
        exit()
    ans_list[amari] = tmp_list

print('No')

鳩の巣原理に気づけなくても動的計画法（DP）で解く方法もあったようですが、私には時間内に実装できるほど実力が足りてないです。
もっと勉強して、気づけなくてもDPなどを駆使して解けるようになろうと思います。

2021-05-06

ABC141 D問題 Powerful Discount Tickets を優先度付きキューで解く

ABC141D問題を解説します。
優先度付きキュー(heapq)の練習で取り組みました。

atcoder.jp

問題の概要

$N$ 個の商品と $M$ 枚の割引券があります。
1つの商品に複数回割引券を使うことができます。
全部の商品を買うために必要な最小の金額を求める問題です。

難しいポイント

方針はすぐに思いつくかもしれませんが、普通の配列を使って最大値を取り出したり、要素を追加したりすると、 $O(N)$ の計算量がかかってしまいます。
$N$ 、 $M$ は最大で $10^5$ なので、タイムオーバーします。

解き方の方針

一番高い値段に割引券を使うのが一番お得になります。
1枚ずつ1番高い値段の商品に割引券を使っていきます。
最大値を取り出す、要素の削除、要素の追加を高速に処理するために優先度付きキュー(heapq)を使います。
heapqのheappopで $O(1)$ で最小値を取り出せますし、 $\log{N}$ で要素を追加できます。

実装

heapq.heappopは最小値を取り出すので、データを読み込むときに-1をかけて、大小を逆転させておきます。

切り捨てのときにマイナスになっていると、値が大きくなってしまいます。
例えば、-13を2で割った切り捨ては-7になってしまいます。
なので、2で割る前に-1をかけて、割ってから-1をかけてあげます。

from heapq import heapify, heappop, heappush
N, M = map(int, input().split())
# 全ての値に-1をかけて大小を逆転させる
a_arr = list(map(lambda x: int(x) * -1, input().split()))
# 配列を優先度付きキューに変換する
heapify(a_arr)

for i in range(M):
    most_expensive = heappop(a_arr)
    # マイナスのまま切り捨ての割り算をすると大きい値になるので、
    # 一度-1をかけてから2で割って、最後に-1をかける
    most_expensive = ((-1 * most_expensive) // 2) * -1
    heappush(a_arr, most_expensive)

print(-1 * sum(a_arr))

2021-05-05

ABC006 B問題　トリボナッチ数列をメモ化再帰で解く

ABC006のB問題を解説します。

atcoder.jp

問題の要約

3つ前までの数字を足した数列（トリボナッチ数列）の $n$ 項目を求める問題です。
数字が大きくなるので $10^4 + 7$ で割ったあまりが求められています。
$a_1 = 0, a_2 = 0, a_3 = 1, a_4 = 1, a_5 = 2, a_6 = 7$ となります。

難しいポイント

$1 \leq n \leq 10^6$ が制約です。再帰関数を書いてしまうとタイムアウトしますし、スタックオーバーフローします。
あと単純に足すと数字がオーバーフローします。

解き方の方針

4項目からn項目まで順番に答えを配列に記録しておきます。
足すときに数字が大きく、求められていることが $10^4 + 7$ で割ったあまりなので、足した後に $10^4 + 7$ で割ったあまりを記録しておきます。
足し算の場合、途中で何回も割ったあまりを求めても答えは変わりません。

@drkenさんの記事を紹介しておきます。

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜 - Qiita

実装

n = int(input())
MOD = 10 ** 4 + 7

# 最初の3項は答えが決まっているので、すぐに答えをprintして終了する
if n in [1, 2]:
    print(0)
    exit()
if n == 3:
    print(1)
    exit()

tribo_memo = [0 for _ in range(n + 1)]
tribo_memo[3] = 1
# 4項からn項まで順番に答えを求めて配列に記録する
for i in range(4, n + 1):
    tribo_memo[i] = (tribo_memo[i - 1] + tribo_memo[i - 2] + tribo_memo[i - 3]) % MOD

print(tribo_memo[n])