2021-08-28

ABC215 B問題 log2(N) を複数パターンで解く

ABC215のB問題を複数パターンで解きます。

問題

正整数 $N$ が与えられるので、 $2^k \leq N$ となる最大の整数 $k$ を求めてください。
制約
$N$ は $1 \leq N \leq 10^{18}$ を満たす整数である

難しいポイント

条件式の両辺に $log_{2}$ をつけて式変形すると $k \leq log_{2}{N}$ となります。
やった簡単！ $log_{2}{N}$ を求めて、少数を切り捨てた値を出力したのですが、いくつかのパターンでWrong Answerとなります。
$N$ がとても大きい数だと誤った答えになってしまうようです。。。
私はこれで何回かハマりました。

1つ目の解き方の方針

$N$ を2進数で表して、桁数 - 1 が答えです。
例えば、 $N = 3$ だったら2進数で $11$ 、pythonのbinメソッドを使うと文字列で'0b11'となります。
なので、binメソッドで得られた文字列の長さから3を引いた数が答えになります。

1つ目の実装

N = int(input())
bin_str = bin(N)
print(len(bin_str) - 3)

2つ目の解き方の方針

基本の考え方は1つ目と同じです。
$N$ を2進数で表して、桁数 - 1 が答え。
10進数から2進数を求めるとき、ひたすら2で割ってあまりを並べることを思い出します。
$N = 5$ の時、 $5 \div 2 = 2 \cdots 1$ 、 $2 \div 2 = 1 \cdots 0$ 、 $1 \div 2 = 0 \cdots 1$ 、となって、 $101$ ということがわかります。
2で割る回数が桁数になっていることがわかります。
$N = 5$ の時、3回2で割ってますけど、求めたいのは桁数 - 1なので、1以下の時は割る必要はりません。
1以下になるまで2で割る回数をカウントして、そのカウントした回数が答えです。

2つ目の実装

N = int(input())
ans = 0
while N > 1:
    ans += 1
    N //= 2
print(ans)

簡単だったのですが、Wrong Answerを出してしまったのが悔しい。。。

2021-08-27

ABC215 C問題 One More aab aba baa を itertools使って解く

ABC215 C問題を解説します。

atcoder.jp

問題

文字列 $S$ の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から $K$ 番目にくる文字列を求めてください。

難しいポイント

文字列の長さが最大で8なので、全パターン列挙しても $8! = 40320$ です。
あまり大きい数ではないので、列挙した後に並べ替えることもできます。
どうやって全パターン列挙するかがポイントなのかなと思います。

解き方の方針

文字列の長さが最大で8なので、全パターン列挙して、並べ替えて、K番目の文字列を取り出します。
全パターン列挙は公式解説のやり方もありますが、色々とあります。
私はpythonで順列列挙してくれるitertools.permutationsを使いました。

サンプルの"aab"の場合、順列列挙すると以下の6パターンが出てきます。

('a', 'a', 'b')
('a', 'b', 'a')
('a', 'a', 'b')
('a', 'b', 'a')
('b', 'a', 'a')
('b', 'a', 'a')

重複した文字があると、パターンにも重複するので、setを使って重複を取り除きます。

('b', 'a', 'a') 
('a', 'a', 'b') 
('a', 'b', 'a')

あとは全部文字列に変換してソートします。

['aab', 'aba', 'baa']

最後に配列の $K$ 番目を出力します。

実装

from itertools import permutations
S, K = input().split()
K = int(K)
S_arr = [s for s in S]
S_arr.sort()
patterns = permutations(S_arr, len(S_arr))
list_pat = list(set(patterns))
pat_str = []
for lp in list_pat:
    pat_str.append("".join(lp))
pat_str.sort()
print(pat_str[K - 1])

実はけっこう無駄な処理してます。。。

文字数が短いのでABC202のD問題 aab aba baa よりは簡単でした。
これを機会に前の問題を復習しようと思います。

ABC202 D問題 aab aba baa をメモして解く - 競技プログラミング悪戦苦闘日記

2021-07-11

ABC209 C問題 Not Equalを解く

ABC209 C問題の解説とふりかえりをします。

問題

atcoder.jp

長さ $N$ の整数列 $C$ が与えられます。以下の条件を全て満たす長さ $N$ の整数列 $A$ の個数を求めてください。
$1 \leq A_i \leq C_i (1 \leq i \leq N)$
$A_i \neq A_j ( 1 \leq i \lt j \leq N)$
ただし、答えは非常に大きくなる可能性があるので、 $(10^9 + 7)$ で割った余りを出力してください。

難しいポイント

おそらく問題を理解するのが難しいのではないかと思います。

解き方

問題文を読みながら具体的な数字を考えていきます。
2つ目のサンプルは $3, 3, 4, 4$ となっています。
愚直に $A_i$ の条件を書き出します。
$1 \leq A_1 \leq 3$ なので選べる数字としては $1, 2, 3$ の3個
$1 \leq A_2 \leq 3$ なので選べる数字としては $1, 2, 3$ の3個
$1 \leq A_3 \leq 4$ なので選べる数字としては $1, 2, 3, 4$ の4個
$1 \leq A_4 \leq 4$ なので選べる数字としては $1, 2, 3, 4$ の4個

ただ同じ数字を選べないという条件があるので、 $1, 2, 3$ から1つ選んだら、
次の $A_2$ は、 $1, 2, 3$ の3個から1つ少ない2個から選べます。
すでに2つの数字を選んでいるので、次の $A_3$ は、 $1, 2, 3, 4$ の4個から2個を引いた2個から選べます。
すでに3つの数字を選んでいるので次の $A_4$ は、 $1, 2, 3, 4$ の4個から3個を引いた1個から選べます。

ということで、整数列のパターンは、 $3 \times 2 \times 2 \times 1 = 12$ となります。

もう少し一般化して表現すると、1から $C_i$ までで選べる個数は $C_i$ 個だけど、それまでに $i - 1$ 個は数を選んでいるので、Nまで $C_i - (i - 1)$ をかけ続けると答えが求められます。

扱う数字が大きくなるとオーバーフローするので、掛け算をするたびに $10^9 + 7$ の余りを求めます。

実装

解き方の方針の通りに実装します。
Cの配列は処理の前にソートしてあげないと、不正解になります。
配列のインデックス $i$ は0から始まるので、見た目は少し異なります。

N = int(input())
c_arr = list(map(int, input().split()))
c_arr.sort()
ans = 1
R = 10**9 + 7
for i in range(N):
    ans = ans * (c_arr[i] - i) % R
print(ans % R)

反省

ans *= (c_arr[i] - i) % R

にするとタイムアウトしました。。。
累積演算子は計算量が思ったよりもかかるんですね。。。勉強になりました。

2021-07-06

ABC208 B問題 Factorial Yen Coin を貪欲に解く

ABC208 B問題を貪欲法で解いた解説です。

問題

atcoder.jp

高橋王国では 1! 円硬貨 ,2! 円硬貨 ,…,10! 円硬貨が流通しています。ここで、
N!=1×2×⋯×N です。
高橋君は全ての種類の硬貨を
100 枚ずつ持っており、P 円の商品をお釣りが出ないようにちょうどの金額を支払って買おうとしています。
問題の制約下で条件を満たす支払い方は必ず存在することが証明できます。
最小で何枚の硬貨を使えば支払うことができますか？

難しいポイント

最小の枚数をどうやって求めるのか、求め方に迷うかもしれません

解き方の方針

Pが最大でも $10^7$ なので、使える貨幣は最大でも $10! = 3628800$ です。
貪欲法の考え方で、大きい貨幣から順番に、貨幣の値を下回るまで使い、最後の $1!$ まで繰り返します。

実装

P = int(input())
fact_list = [1] * 12
# 再帰メモ化で11!まで階乗の値を保存する
for i in range(1, 12):
    fact_list[i] = fact_list[i - 1] * i
j = 10
ans = 0
while P != 0:
    if P >= fact_list[j]:
        P -= fact_list[j]
        ans += 1
    else:
        j -= 1

print(ans)

2021-07-05

ABC208 C問題 Fair Candy Distribution を直感で解く

ABC208 C問題をゆるく解説します。

問題

atcoder.jp

高橋王国には N 人の国民がいます。全ての国民には国民番号が割り振られており、 i 人目の国民の国民番号は $a_i$ です。ここで、 $a_i$ は互いに異なります。
高橋君は K 個のお菓子を持っています。高橋君は次のルールに従って、持っているお菓子が無くなるまで国民にお菓子を配ることにしました。
持っているお菓子が N 個以上ある場合、全員に 1 個ずつお菓子を配る。
そうでない場合、その時点で高橋くんが持っているお菓子の個数を K′ として、国民番号が小さい方から K′ 人に 1 個ずつ配る。より厳密には、 $a_i$ の値が小さい方から K′ 人を選び、選んだ人に 1 個ずつお菓子を配る。
全てのお菓子を配り終えたとき、i 人目の国民は何個のお菓子を持っていますか？

難しいポイント

Nの最大値が $2 \times 10^5$ 、Kの最大値が $10^{18}$ なので、愚直に解けないことがわかります。
一番難しいのは問題を理解することなのかなとも思います。

解き方の方針

サンプル１の入力例を愚直に手で書き出して解法の糸口が見えました。
$N = 2, K = 7, a_1 = 1, a_2 = 8$ の場合を考えると持っているお菓子の数が $N$ を下回るまで、全員にお菓子を1個ずつ配ってます。
お菓子の残りが1個になっているということは、6個のお菓子を2人に等しく配っていることになります。
つまり、 $7 \div 2$ の商の3個は全員に行き渡ります。
一般化すると、 $\lfloor \frac{K}{N} \rfloor$ 、KをNで割った切り捨てた数が少なくとも全員に行き渡ります。
あとはKをNで割った余りをどう分配させるかです。
このサンプルでは余りは1です。
問題文から $a_i$ の値が小さい方から配っていくということなので、小さい方から1つまでは配られることがわかります。
つまりKをNで割った余りの数をrとすると、小さい方からr番目までは全員に行き渡る個数（ $\lfloor \frac{K}{N} \rfloor$ ）より1つ大きい数になります。

実装

公式解説の実装の方が美しいです。
私は最初の順番と $a_i$ の値を組み合わせた配列（1つ目を順番、2つ目を $a_i$ ）を配列に格納して、2次元配列にしました。
まずは、2次元配列の2つ目の要素である $a_i$ の値で小さい順にソートして、
$\frac{K}{N}$ の余りをrとした時に、最初のr番目までは、最低限全員に行き渡る個数 $\lfloor \frac{K}{N} \rfloor$ に1を足した数を格納し、それより後は最低限全員に行き渡る個数を格納しました。
最後に2次元配列の1つ目の要素でソートして、先頭から順番に2つ目の要素の値を出力します。

N, K = map(int, input().split())
a_arr = list(map(int, input().split()))
amap_arr = []
for i, a in enumerate(a_arr):
    amap_arr.append([i, a])
# 2つ目の要素a_iでソート
amap_arr = sorted(amap_arr, key=lambda x: x[1])
# 最低限全員に配られる個数
at_least = K // N
amari = K % N
for i in range(N):
    # 最初のamari個はat_leastに1を足した個数がもらえる
    if i <= amari - 1:
        amap_arr[i][1] = at_least + 1
        continue
    amap_arr[i][1] = at_least

# 最初の順番になるようにソート
amap_arr = sorted(amap_arr, key=lambda x: x[0])
# 答えを出力
for i in range(N):
    print(amap_arr[i][1])

最近はC問題まで楽に解けるようになってきた感じなので、ワーシャルフロイドやUnion Findなどを勉強してD問題を解ける確率を上げていこうとしています。
本質を理解して使いこなせるようになるまでじっくりと取り組む。

2021-06-27

ABC207のC問題 Many Segments をすんなりと解く

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

atcoder.jp

問題の概要

区間が $N$ 個あたえられて、共通部分を含む2つの区間の組み合わせを求める問題です。

難しいポイント

区間といっても、開区間、閉区間の表現があり、2つの区間で共通している区間を含むか含まないかを、どうやって実装するかが難しいところかと思います。
サンプルにある $\left[2, 3\right)$ と $\left(2, 4\right$ ]の共通部分 $\left(2, 3\right)$ をどうやって判定するかです。
$\left(2, 3\right)$ って2も3も含まないのにどういう区間と思ったら、少数の世界をイメージすると2.1、2.2、2.3みたいな区間ということがわかります。

解き方の方針

Nが最大で2000なので全ての組み合わせを考えても、 ${}_{2000} C_2 = 1000 \times 1999 = 1999000$ で全通り調べても問題ないオーダーです。
2つの区間に共通区間があるかないかを判定して、共通区間があればカウントします。
tで条件分岐して、端の数字が含まれない場合は、端の数字に0.1を足したり、引いたりします。

実装

実装は以下のようになりました。
get_rangeなんていうメソッドを作らないで、読み込むときにtで条件分岐して端の数字に0.1を足したり引いたりすれば良いと思います。

from itertools import combinations
N = int(input())
r_list = []
for _ in range(N):
    t, l, r = map(int, input().split())
    r_list.append([t, l, r])


def get_range(r):
    if r[0] == 1:
        return [r[1], r[2]]
    if r[0] == 2:
        return [r[1], r[2] - 0.1]
    if r[0] == 3:
        return [r[1] + 0.1, r[2]]
    return [r[1] + 0.1, r[2] - 0.1]


def hikaku(r1, r2) -> bool:
    r1_range = get_range(r1)
    r2_range = get_range(r2)
    if r1_range[1] >= r2_range[0] and r1_range[0] < r2_range[1]:
        return True
    if r2_range[1] >= r1_range[0] and r2_range[0] < r1_range[1]:
        return True
    return False


c_list = combinations(range(N), 2)
ans = 0
for c in c_list:
    if hikaku(r_list[c[0]], r_list[c[1]]):
        ans += 1
print(ans)

2021-06-20

ABC206 C問題 Swappable をNのオーダーで解く

ABC206のC問題の解いた過程を書きながら解説します。
公式解説がかなり丁寧なので、厳密な解説はそちらを参考にしてください。

問題の概要

N個の整数からなる配列から、2つの異なる値の組み合わせが何個あるか求める問題です。

atcoder.jp

難しいポイント

$N \leq 3 \times 10^5$ なので、愚直にループを回すとタイムオーバーします。
同じ数が配列に含まれるときに重複をどうやって取り除くかがポイントです。

方針

まず全体から2つ選ぶ組み合わせは ${}_N C_2 = \frac{N \times (N - 1)}{2}$ です。
重複を削除する方針を考えるために、愚直に具体例をイメージして書き出してみます。
ここでは、 $[1, 7, 1, 1, 2, 2]$ という配列で表を描いてみます。

1は3個あります。1が重複することによって、黄色の3パターンが条件を満たさないパターンです。
2は2個あります。2が重複することによって、水色の1パターンが条件を満たさないパターンです。
この表を見ると、重複している数字の個数を $v$ としたときに、条件を満たさないパターンの数は ${}_v C_2 = \frac{v \times (v - 1)}{2}$ ということがわかります。
もっと大きい重複数で書き出すともっとイメージがつかめるかもしれません。

実装

collections.Counterを使って、dictionaryに各数字の出現個数を記録しました。
各数字の出現個数から条件を満たさない個数を算出して足していきます。
全体の場合の数から条件を満たさない個数を引いた数を出力します。

from collections import Counter
N = int(input())
a_arr = list(map(int, input().split()))

# 各数字の出現回数を記録する
rui_dict = Counter(a_arr)
minus = 0
for v in rui_dict.values():
    # 重複数を数える
    minus += (v * (v - 1)) // 2
# 全パターンから条件を満たさないパターン数を引いた数が答え
ans = N * (N - 1) // 2 - minus
print(ans)

こんな簡単な問題文なのに、思い込みで問題を読み違えていて時間ロスしました。。。