タムログ

プログラミングについての情報発信をしていきます！

AtCoder Beginner Contest 164 D を Python で

ABC D問題 AtcoderをPythonで

AtCoder Beginner Contest 164 D を Python で解説していきます。
この問題はコンテスト中かなり頭を悩ませたのですが，どうやら ABC 158 E 問題にとても似ている問題だったようですね。とても数学的要素が強い問題かと思いますが，数学が得意でない人や灰コーダー向けに重要な点を抜き出して解説していくので，頑張って理解していきましょう！
それでは，まずは問題文からいきます。

D – Multiple of 2019

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

1 から 9 までの数字のみからなる文字列 S が与えられます。

次のような条件を満たす整数の組 (i,j) (1≤i≤j≤|S|) の総数を求めてください。

条件: S の i 文字目から j 文字目までを 10 進法の整数としてみると、この整数は 2019 の倍数である。

制約

  • 1≤|S|≤200000
  • S は 1 から 9 までの数字のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

条件を満たす整数の組 (i,j) (1≤i≤j≤|S|)の総数を出力せよ。

入力例 1

1817181712114

出力例 1

3

条件を満たすのは (1,5),(5,9),(9,13) の 3 個です。

入力例 2

14282668646

出力例 2

2

入力例 3

2119

出力例 3 

0

条件を満たす整数の組は存在しません。

解説

もちろん，以下のように問題文に沿ってそのまま愚直な二重ループで書くやり方は，O(N^2)で，𝑁≃10^6
 なので，𝑂(10^12) 
    程度のオーダーになって，TLE になります。
(オーダーの感覚は，大体10^8以 下となることを目安にプログラムすれば間に合います。)
また，詳しく言うと，S は最大 200000 桁ですが，コンピュータ内では64 bit の整数ですら 18 桁くらいしか表現できないので（2^(63-1)という数字になります）普通の整数型では表せず，以下のような単純な実装ではかなり重い計算になってしまうようです。(Python では内部処理で無理やり数を出すこと自体はできます)もはやオーダーがどうこうという話ではなくなります。😱

s = input()
n = len(s)

count = 0

for i in range(n-3):
    for j in range(i+3, n):
        number = int(s[i:j+1])
        if number % 2019 == 0:
            count += 1

print(count)

ということで，何らかの工夫が必要になるわけです。

まず，このような区間の数え上げは，片方を固定して，もう片方を高速で列挙するのが定石です。𝑎_i=𝑆[𝑖:𝑁]
 (Sのi番目以降) とします。すると，S の i 番目から j 番目までの数をこれで表そうとすると，(a_i-a_(j+1))/(10^(N-j)) と表すことができます。

具体的に見ていきましょう。入力例１を短くして 181718171 を用いて扱います。このとき，𝑎1=181718171
，𝑎2=81718171
，…, 𝑎𝑁−1=71
，𝑎𝑁=1
になります。ここで，181718171 → 718 を取り出すことを考えると，これは

(718171−171)/1000=718000/1000=718

で得ることができます。
これはつまり、(a_4-a_7)/10^(9-6)を表していることになりますよね。つまり，𝑎𝑖=𝑆[𝑖:𝑁]
 (Sのi番目以降) だけを用いて，全ての考えうる整数をとることができます。 最初のコードだと２変数でループしなければならなかったのが，うまくやることで１変数だけで考えることができるようになります。

さて，ここからが本題です。先ほどの式𝑎𝑖−𝑎𝑗+1/10^(N-j)         から得られた整数に対して，これが 2019 で割り切れるための条件は，(a_i-a_j+1)/(10^(N-j))≡0(𝑚𝑜𝑑2019)⇔𝑎𝑖−𝑎𝑗+1≡0(𝑚𝑜𝑑2019)⇔𝑎𝑖=𝑎𝑗+1(𝑚𝑜𝑑2019)
これはつまり，𝑎𝑖−𝑎𝑗+1/10^(N-j)        を 2019 で割った余りが 0 であるということですが，2019 と 10 が互いに素であるから，これは𝑎𝑖−𝑎𝑗+1を2019で割った余りと同じであるということです。この式の分母の10𝑁−𝑗
は無視して考えられます。よって，𝑎𝑖
と𝑎𝑗+1
はそれぞれ2019で割った余りが同じであるということになります。

以上より，１～N までの全ての 𝑎𝑖 を2019で割った余りを求めてやり，𝑎𝑖=𝑎𝑗+1(𝑚𝑜𝑑2019)となるような，(i, j)の組み合わせの数を出力してあげれば良いということになります。

そのために，これまで𝑖 は 1から順に N までという順番で考えていましたが，逆に N から 1 までの順番で考えてあげます。この順に，𝑎𝑖の値をリストに入れていくことによって，先ほど考えていた𝑗をこの𝑖で考えていることになり，𝑎𝑖+1 で取得したい場合の数は，𝑖 番目までにリストに入れていたmod(2019) の値と同じものの数を順次考えていくだけで算出することができ，より効率よく数え上げることができます。

では，𝑎𝑖の考え方です。これは，S の N 番目から（後ろから）考えていくと，𝑖≥0
として，𝑎𝑖=10^i×𝑠[−1−𝑖]+10^𝑖−1×𝑠[−1−𝑖−1]+ … +10^0×𝑠[−1]
 です。これは最初に d=1 で，𝑎1=𝑆[−1]×𝑑
 として，この𝑎1
に𝑆[−2]×𝑑×10
を足すことで得ることができます。このように考えると，ループの中で d を毎回 10 倍するような値に設定して，毎回対応する S[-i]×d をその前の値に足していくと，必要な 𝑎𝑖 が得られます。また，d の値が大きくなりすぎると，コンピュータ内部での処理が大変になり，処理速度がかかりすぎてしまうので，毎回 2019 で割った余りにしておきます。最終的に𝑎𝑖×𝑑
 の mod(2019) の値を出せばよいので，先にd を 2019 で割っても (mod 2019) の値は変わりません。
ここまでは以下のようなコードで表せます。

# a_iはこのnumber*dで表していく
number = 0
d = 1

for i in s:
    # a_iを表現
    number += int(i)*d
    # numberで次の桁にしたいから，dを10倍
    d *= 10
    # numberが大きすぎない値になるようにd自体を先にmod2019の値でとる
    d %= 2019

次に，mod(2019) の値の数え方についてです。これは まず０ が 2019 個入ったリスト（名前をcountとする) を用意します。そして各𝑎𝑖の mod(2019) の値に対応するインデックス番号にあたる値 count[𝑎𝑖% 2019] に１を足していくことで，最終的にこのリストの値の数が，各𝑎𝑖のmod(2019) の値の総数に一致します。
また，最初の段階で，便宜上何もとらないという意味として𝑎0≡0(𝑚𝑜𝑑2019)
 を導入したいので，count[0] = 1 としておきます。 こうすることで，例えば先ほどの例で 181718171 をとるには，𝑎5 で表現できますが，これが 2019 の約数なら，𝑎5≡0(𝑚𝑜𝑑2019)
 という条件から，便宜上用いた𝑎0 を用いて，𝑎5=𝑎0として，場合の数を計算できます。

ここまでを書くと，以下のようになります。

s = input()
# sを逆にする
s = s[::-1]
n = len(s)

# 各インデックス番号にmod2019の値が格納されるリストを設定
count = [0]*2019
# a_0の分を入れておく
count[0] = 1
# a_iはこのnumber*dで表していく
number = 0
d = 1

for i in s:
    # a_iを表現
    number += int(i)*d
    # a_iのmod2019の値をcountに格納
    count[number%2019] += 1
    # numberで次の桁にしたいから，dを10倍
    d *= 10
    # numberが大きすぎない値になるようにd自体を先にmod2019の値でとる
    d %= 2019

後はこの count の中に格納された値について，取りうる場合の数の和を出します。これは，count のそれぞれのインデックス番号に対する値について，異なる２つをとる場合の数なので，𝑐𝑜𝑢𝑛𝑡[𝑖]𝐶2=𝑐𝑜𝑢𝑛𝑡[𝑖]×(𝑐𝑜𝑢𝑛𝑡[𝑖]−1)/2を，count 内の全ての値について取った和を出して，その値を出力します。

以上，詳しく説明しすぎて逆によく分かりにくくなってしまった感がありますが，いかがだったでしょうか。😅
それでは，解答例に移ります。

解答例

s = input()
s = s[::-1]
n = len(s)

count = [0]*2019
count[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    count[number%2019] += 1
    d *= 10
    d %= 2019

ans = 0

for i in count:
    ans += i*(i-1)//2

print(ans)

個人的に，今までで一番説明が難しく，冗長になってしまったような気がしますが，どうしょうか。ABC 158 E とほぼ同じだったようで，自分もこの回のコンテストには参加していたので，解けなかったのが悔しかったです。もし分からないところや，間違っているところがあれば，twitter やここのコメントでお伝えください。
それでは！

AtCoder Beginner Contest 163 D を Python で

ABC D問題 AtcoderをPythonで

AtCoder Beginner Contest 163 D を Python で解説していきたいと思います。
結構数学的な問題なのかな？と思ったのですがどうだったでしょうか。
それでは，まずは問題文から。
https://atcoder.jp/contests/abc163/tasks/abc163_d

D – Sum of Large Numbers

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

10^100, 10^100+1, …, 10^100+N の N+1 個の数があります。

この中から K 個以上の数を選ぶとき、その和としてあり得るものの個数を mod(10^9+7) で求めてください。

制約

  • 1≤N≤2×10^5
  • 1≤K≤N+1
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

和としてあり得るものの個数を mod(10^9+7)で出力せよ。

入力例 1

3 2

出力例 1

10

以下の 10 通りが考えられます。

  • (10^100)+(10^100+1)=2×10^100+1
  • (10^100)+(10^100+2)=2×10^100+2
  • (10^100)+(10^100+3)=(10^100+1)+(10^100+2)=2×10^100+3
  • (10^100+1)+(10^100+3)=2×10^100+4
  • (10^100+2)+(10^100+3)=2×10^100+5
  • (10^100)+(10^100+1)+(10^100+2)=3×10^100+3
  • (10^100)+(10^100+1)+(10^100+3)=3×10^100+4
  • (10^100)+(10^100+2)+(10^100+3)=3×10^100+5
  • (10^100+1)+(10^100+2)+(10^100+3)=3×10^100+6
  • (10^100)+(10^100+1)+(10^100+2)+(10^100+3)=4×10^100+6

入力例 2

200000 200001

出力例 2

1

全てを選ぶしかないので 1 通りです。

入力例 3

141421 35623

出力例 3

220280457

解説

10^100, 10^100+1, …, 10^100+N の N+1 個の数があり，この中から K 個以上の数を選ぶとき、その和としてあり得るものの個数を mod(10^9+7) で求めるというものです。

ただし，ここで 10^100 は見掛け倒しです。（笑）
ただの和を考えればいいので，例えば 10^100 + 10^100+1 = 2 × 10^100 + 1 は，結局１に対応します。

つまり，０～N の数があり，この中から K 個以上の数を選ぶときの和のありうるものの個数に帰着されます。ただし，K は 10^100 の個数に対応するので，
（先ほどの例では10^100 + 10^100+1 = 2 × 10^100 + 1 = K × 10^100 + 1)
ここでは０～N の数の和自体が同じでも， K の値が異なれば異なる和と考えます。
以上より，以下が導けます。

K ≦ i ≦ N+1 における i において，０～N の数から i 個の数を選ぶときの和のありうるものの個数を，すべての i に対して足し合わせたものを出力する。

ここで問題となるのは，各 i における i 個の数を選ぶときの和のありうるものの個数をどう出すかですが，この０～Nの値の和は，i 個の数の和の最小値から最大値まで全ての値を取ることができます。
これは数学的に証明できますが，ここでは省略します。
よって，このときの和の個数は，（最大値　ー　最小値　＋１）で出すことができます。

最大値は，N から i 個取った数の和ですし，最小値は ０から i 個取った数の和です。
ここで，１～N までの数の和は，N(N+1)/2 で与えられるので，これを使います。

まず最小値は，０から i 個取った数の和，すなわち０から i-1 までの数の和なので，上の式から
min = (i-1)×i/ 2
で得られます。
次に最大値ですが，これは N から i 個取った数の和，すなわち N-i+1 から N までの和になります。色々な計算の仕方がありますが，一番やりやすいのが，1からN までの和から，１からN-i までの和を引けばいいです。
max = N×(N+1)/2 – (N – i)×(N – i + 1)/2
になります。よって，あとは以上から得られた max – min + 1 を，K ≦ i ≦ N+1 なる全ての i において足し合わせた結果を出力してやります。これでO(n)で解くことができました。
それでは以下に解答例を載せておきます。
mod(10^9+7)で出力するので，最後の結果を 10^9+7 で割った余りを出力することに注意してください。

解答例

n,k = map(int, input().split())
 
ans = 0
mod = 10**9+7
 
for i in range(k,n+2):
    ans += int((n*(n+1)/2 - (n-i)*(n-i+1)/2 - (i-1)*i/2 +1))
 
print(ans%mod)

いかがだったでしょうか。
コード自体はかなり簡潔に書けますが，考え方がかなり数学チックでややこしい問題でしたね。
もし分からないところがあればコメントしてくださいね！
他の問題も解説しているので，ぜひご覧ください。
それでは！

追記

０～Nの値の和は，i 個の数の和の最小値から最大値まで全ての値を取ることができます。
これは数学的に証明できますが，ここでは省略します。

上記のこの証明の部分を知りたいと言う方がおられたので，追記しておきたいと思います。
i の値を固定して考えます。i は K ≦ i ≦ N+1，K は1≤K≤N+1 なる数です。
まず上記の説明からmin と max が与えられます。
min + 1 の値をとれるかについてですが，i は高々 N+1 であり，０からN までの N+1 個の数の値について考えているので，i = N+1 なら min と max が一致します。
i が N 以下である時は，０からN までで選んだ i 個の数のうち，その数のうちで最大となるもの(m_1とする)より１大きい数(m_2とする)が必ず選べるので，m_1とm_2を入れ替えることでとmin+1 の値は取れます。
次の min + 2 は，先ほどの m_1 – 1 なる数字と m_2 を入れ替えることで作れます。
以下，帰納的に，min + j = max となるような j が得られるまで，min + 2 , min + 3 … min + j の値は得られることが分かります。
以上より，厳密ではありませんが，０～Nの値の和は，i 個の数の和の最小値から最大値まで全ての値を取ることができることが帰納的に示すことができました。

AtCoder Beginner Contest 160 D を Python で

ABC D問題 AtcoderをPythonで

AtCoder Beginner Contest 160 D を Python で解説していこうと思います。自分が初めてコンテスト開催中に解けた D 問題で，なかなか感慨深い問題です。（笑）
それではさっそく，まずは問題文から。
https://atcoder.jp/contests/abc160/tasks/abc160_d

D – Line++

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

1 から N までの番号がつけられた N 個の頂点を持つ無向グラフ G があります。 G には、以下のように合計 N 本の辺があります。

  • i=1,2,…,N−1 について、頂点 i と頂点 i+1 の間に辺があります
  • 頂点 X と頂点 Y の間に辺があります

k=1,2,…,N−1 について、以下の問題を解いてください。

  • 整数の組 (i,j)(1≤i<j≤N) であって、 G において頂点 i と頂点 j の最短距離が k であるようなものの数を求めてください

制約

  • 3≤N≤2×10^3
  • 1≤X,Y≤N
  • X+1<Y
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N X Y

出力

k=1,2,…,N−1 に対する問題の答えを、順番に一行に出力せよ。

解説

無向グラフ G において，２頂点間の最短距離が k (1≦k≦N-1) であるようなものの個数を出せといった問題です。G は頂点 i と i+1 の間に辺があり，これが合計 N-1 本，そして入力される値 X，Y に応じてその X と Y との間に１つの辺が作られるので，全部で合計 N 本の辺ができます。

さて，最短経路の考え方についてです。これは X と Y の間に作られる辺を通るかどうかの２パターンが考えられますよね。X と Y の間の辺を通った方が距離が短くなる場合と，逆に距離が長くなる場合が考えられるので，その２パターンの距離を出し，そのうちの距離が短い方を最短経路と考えればいいです。
以下，頂点 i と 頂点 j （ i < j ) の２点間の距離について考えることとします。

まずは X と Y の間の辺を通らない場合です。これは単純に j – i で求めることができます。

次に X と Y の間の辺を通る場合です。これは，次の３つの経路を通ると考えればいいです。

  • 頂点 i から頂点 X へ向かう（距離は | X – i | ）
  • 頂点 X から頂点 Y へ向かう （距離は１）
  • 頂点 Y から頂点 j へ向かう （距離は | j – Y |）

これより，合計距離が（| X – i | + 1 + | j – Y |) になります。これと j – i との距離の小さいほうが最短距離になります。
Python では絶対値を出力しようとするときは abs 関数を用いればいいです。
ex.) abs(-2) -> 2

続いて，実装方法です。まずは距離 k の数を要素とするリスト dis を生成します。
dis[1] が距離 1 の個数，dis[2] が距離２の個数・・・といった具合です。
初期段階ではすべての距離の数を 0 としておきます。

その後，for ループで i < j なるような i と j の全てにおいて，上記の方法で最短距離を求め，その距離に対応する dis のリストの要素の数を +1 します。
最終的に dis の１～Nの要素を出力すればよいです。
これで計算量はO(n^2)で解くことができました。
では，以下に解答例を載せます。

解答例

n,x,y = map(int, input().split())
 
dis = [0]*n
 
for i in range(n):
    for j in range(i+1, n):
        kyori = min(j-i, abs(x - (i+1)) + 1 + abs(y - (j+1)))
        dis[kyori] += 1
 
for k in range(1, n):
    print(dis[k])

いかがだったでしょうか。
もし分かりにくいところなどがあれば，気軽にコメントしてくださいね！
それでは！

AtCoder Beginner Contest 161 D

ABC D問題 AtcoderをPythonで

AtCoder Beginner Contest 161 D 問題 を Python で解説していきます。私はルンルン数の作り方の仕組み自体は分かったのですが，それを解くプログラムが思いつかずにタイムアップしてしまいました。(´;ω;｀)
後の解説を見てキューを使えば上手くできることを知り，自分でプログラムを書いたので，それで解説していきたいと思います。
まずは問題から。

D – Lunlun Number

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

正の整数 X が以下の条件を満たすとき、 X はルンルン数であると言います。

  • X を(leading zeroなしで)十進数表記した際に、隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下

例えば、 1234 , 1 , 334 などはルンルン数ですが、 31415 , 119 , 13579 などはルンルン数ではありません。

正の整数 K が与えられます。小さい方から K 番目のルンルン数を求めてください。

制約

  • 1≤K≤105
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

K

出力

答えを出力せよ。

解説

実際に2桁までのルンルン数を列挙してみます。まずは一桁の整数である1~9まではルンルン数です。そして２桁のルンルン数は

10 11 | 21 22 23 | 32 33 34 | 43 44 45 | 54 55 56 | 65 66 67 | 76 77 78 | 87 88 89 | 98 99

のようになります。この二桁のルンルン数を一桁のルンルン数と紐づけて考えてみると，次のような法則性があることに気付くことができるのではないでしょうか。

  1. N 桁のルンルン数 A の一の位が0の時
    N+1桁のルンルン数を作ろうとすると，A*10 と A*10 + 1 が作れる
    ex.) 1 -> 10 と 11
  2. N 桁のルンルン数 X の一の位が1~8の時，一の位の数を B として
    N+1桁のルンルン数を作ろうとすると，A*10 + (B-1) と A*10 + B と A*10 + (B+1) が作れる
    ex.) 3 -> 32 と 33 と 34
  3. N 桁のルンルン数 A の一の位が9の時
    N+1桁のルンルン数を作ろうとすると，A*10 + 8 と A*10 + 9 が作れる
    ex.)9 -> 98 と 99

この法則を三桁のルンルン数と二桁のルンルン数との間にも試してみてください。実際に成り立つことが分かると思います。このように，N 桁のルンルン数から N+1 桁のルンルン数が作れるわけです。
問題はこれをどのようにコードにするかです。

ここで，データ構造のキューを使えば，上手いことコードが書けます。(キューとは？というかたはこちらをご覧ください)要は，ルンルン数のデータを収納するようなリストを作成して，そのリストの一番下の値を取り出し，その値に応じた N+1 桁のルンルン数をリストの一番上に積んでいけば，ルンルン数を小さい順にリストに格納することができるわけです。

実際の動き　
L = [1, 2, 3, 4, 5, 6, 7, 8, 9] (ルンルン数のリスト)
L から 1 を取り出す。先ほどの法則1よりルンルン数10 と 11が作れる。リスト L にこの値を積む。
L = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

この操作をどんどん繰り返していって，K 番目のルンルン数が得られたときに操作をやめて出力すればいいです。

さて，最後は細かい動きの実装です。K 番目のルンルン数というのをどう表現するかですが，まず K が1~9までの時は，そのまま整数 1~9 に対応しますので，上記の操作をする必要はなく，K に対応する1~9の数字を出力します。

K が10以上の時を考えます。上記の操作をして，ルンルン数を１つ追加するごとに K の値を 1 小さくして，K の値が 0 以下になった段階で操作をとりやめ，K 番目のルンルン数を出力することを考えます。

まずはキューに1~9の数字を入れます。この時点でキューには 9 個の数字が入っているので，K から 9 を引きます。後は実際に K の値を具体的に考えて，操作を考えてみましょう。

例えば K = 13 の時
K -= 9 (K = 4 になる)
1 から 10，11 を作成。ルンルン数が二つできたので K -= 2 (K = 2 になる)
2 から 21，22，23 を作成。ルンルン数が三つできたので K -= 3 (K = -1 になる)
K < 0 なので操作を終了。この時点でルンルン数のリスト L に格納されているルンルン数は
L = [3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 22, 23]
出力したい 13 番目は 22 なので，L[-2]を出力

K = 14 の時
K -= 9 (K = 5 になる)
1 から 10，11 を作成。ルンルン数が二つできたので K -= 2 (K = 3 になる)
2 から 21，22，23 を作成。ルンルン数が三つできたので K -= 3 (K = 0 になる)
K < 0 なので操作を終了。この時点でルンルン数のリスト L に格納されているルンルン数は
L = [3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 22, 23]
出力したい 14 番目は 23 なので，L[-1]を出力

K = 15 の時
K -= 9 (K = 6 になる)
1 から 10，11 を作成。ルンルン数が二つできたので K -= 2 (K = 4 になる)
2 から 21，22，23 を作成。ルンルン数が三つできたので K -= 3 (K = 1 になる)
3 から 32，33，34 を作成。ルンルン数が三つできたので K -= 3 (K = -2 になる)
K < 0 なので操作を終了。この時点でルンルン数のリスト L に格納されているルンルン数は
L = [4, 5, 6, 7, 8, 9, 10, 11, 21, 22, 23, 32, 33, 34]
出力したい 15 番目は 32 なので，L[-3]を出力

以上が場合分けです。結局，最終的な K の値に応じて 3 パターンの場合分けを考えたらよいわけです。この場合分けが一般的に通じることを他の場合においても確かめてみてください。よって，実装すべき K の値による場合分けは以下のようになります。

  • 最終的な K の値が -1 の時：L[-2] を出力
  • 最終的な K の値が 0 の時：L[-1] を出力
  • 最終的な K の値が -2 の時：L[-3] を出力

長くなりましたが，以上が解説になります。あとはこれをコーディングする作業ですね。
では，解答例を載せておきます。

解答例

from collections import deque
k = int(input())

q = deque([i for i in range(1, 10)])

# kが9以下ならその値を出力して終了
if k <= 9:
    print(k)
    quit()

k -= 9

# ルンルン数の法則から操作を行う
while k > 0:
    # aがキューから取り出した値
    a = q.popleft()
    # bがaの一の位の値
    b = a % 10
    if b == 0:
        q.append(10*a)
        q.append(10*a + 1)
        k -= 2
    elif b != 0 and b != 9:
        q.append(10*a + (b - 1))
        q.append(10*a + b)
        q.append(10*a + (b + 1))
        k -= 3
    else:
        q.append(10*a + 8)
        q.append(10*a + 9)
        k -= 2

if k == -1:
    print(q[-2])
elif k == 0:
    print(q[-1])
elif k == -2:
    print(q[-3])

かなり詳しく掘り下げて解説してみました。
法則性はなんとなく分かるんですが，それをコーディングするというのはちょっと難しかったですね。
キューを使うという発想が出れば簡単だったのかなと思います。
まだまだ精進しなければ！😔

もし分からないところがあったり，もっとこうした方がいいというものがあれば，ぜひコメントお願いします！
それでは！

AtCoder Beginner Contest 170 C を Python で

ABC C問題 AtcoderをPythonで

AtCoder Beginner Contest 170 C を Python で解説していきたいと思います。twitter 界隈ではこの問題の解説が煽ってるなどなどと色々話題になっていましたが，どうなんでしょうか。確かに言っていることは間違っていないと思いますが，個人的にはもうちょっと配慮のある書き方をしても良かったのではないかと思います。
まぁそれは置いておいて，まずはいつも通り問題文から行きます。

C – Forbidden List

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

整数 X と、長さ N の整数列 p1,…,pN が与えられます。

整数列 p1,…,pN に含まれない整数 (正とは限らない) のうち X に最も近いもの、つまり X との差の絶対値が最小のものを求めてください。そのような整数が複数存在する場合は、そのうち最も小さいものを答えてください。

制約

  • 1≤X≤100
  • 0≤N≤100
  • 1≤pi≤100
  • p1,…,pN はすべて異なる。
  • 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

X N
p1 … pN

出力

答えを出力せよ。

入力例 1

6 5
4 7 10 6 5

出力例 1

8

整数列 4,7,10,6,5 に含まれない整数のうち、最も 6 に近いものは 8 です。

入力例 2

10 5
4 7 10 6 5

出力例 2

9

整数列 4,7,10,6,5 に含まれない整数のうち、最も 10 に近いものは 9 と 11 です。このうち小さい方である 9 を出力します。

入力例 3

100 0

出力例 3

100

N=0 の場合、入力の 2 行目は空行となります。また、この場合のように、X 自身も答えとなりえます。

解説

与えられた整数列 p にない数のうち，X に最も近い最小の整数を出力せよという問題です。X 自身が答えになる場合にも注意しましょう。

ここでは，言われたとおりに X に最も近い数から順にその数が p にないかどうかを判定していけばよいでしょう。つまり
X，X-1，X+1，X-2，X+2，…
とこのような順で判定していけばよいのではないでしょうか。

ここでは変数 i を用いて，while ループ内でこの操作を行っていきます。毎回の while ループで行う処理は次のものです。最初に i は０で初期化しておきます。

  1. X-i が p にあるか判定し，なければ ans にその値を格納して break
  2. X+i が p にあるか判定し，なければ ans にその値を格納して break
  3. i に１を足す

この while 内の処理で先ほど述べた順々の判定が行えます。それでは，解答例に移ります。

解答例

x,n = map(int, input().split())
p = list(map(int, input().split()))

ans = -1
i = 0

while True:
    temp = x -i
    if temp not in p:
        ans = temp
        break
    temp = x + i
    if temp not in p:
        ans = temp
        break
    i += 1

print(ans)

いかがだったでしょうか。
愚直な処理で解ける問題でしたね。
もし何かあれば twitter で気軽にご連絡ください。
それでは！

AtCoder Beginner Contest 169 C を Python で

ABC C問題 AtcoderをPythonで

こんにちは，タムログです。今回は結構問題になった昨日の ABC169C の問題の解説をしていきたいと思います。自分もただ掛け算を出力するだけなのに全然 AC にならなくて，発狂しかけました。先に言っておくと小数の演算には要注意ということですね。勉強になりました。
それでは，早速行きましょう。まずは問題文から。

C – Multiplication 3

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

A×B の小数点以下を切り捨て、結果を整数として出力してください。

制約

  • 0≤A≤10^15
  • 0≤B<10
  • A は整数
  • B は小数第 2 位まで与えられる

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

答えを整数として出力せよ。

入力例 1

198 1.10

出力例 1

217

198×1.10=217.8 なので、小数点以下を切り捨てて答えは 217 となります。

入力例 2

1 0.01

出力例 2

0

入力例 3

1000000000000000 9.99

出力例 3 

9990000000000000

解説

はい，この問題「やるだけ」じゃないんですよね。ただ単純に積の値を出力してしまうと，WA 連発してしまいます。
なぜこのようなことになってしまうかというと，コンピュータの数の表現の仕方に原因があります。

私たちは普段１０進数で数を表現していますが，コンピュータでは2進数で数を表現しています。これが原因で丸め誤差と言うものが生じてしまいます。簡単に言うと，普段使っている数をコンピュータ内部で正確に表現することができないわけです。例を挙げてみましょう。パソコンにもよるかもしれませんが，1.1 + 2.2 の計算結果を出力してみましょう。

>>> 1.1 + 2.2
3.3000000000000003

このように，本来 1.1 + 2.2 = 3.3 であるはずなのに，上記の結果は微小な誤差が生じていますよね？
こういう小さな誤差のせいで得たい出力結果が得られなくなっているのです。

この問題を解消するための手法の一つは，整数に直して計算することです。整数であれば2進数で正確に表現することができますから，このような誤差を考えなくてすみます。今回の問題設定では，b は小数第二位まで与えられるとありますので，十進数的考え方なら１００倍してやれば整数になります。

ただ，ここにも罠があります。十進数では小数第二位までであっても，二進数で表すと無限小数になってしまうことがよくあり，このせいで丸め誤差が生じるということを説明しました。これより，ただ１００倍してやるだけでは，十進数では整数に見えても二進数ではまだ小数部分が残っている場合があります。この時，この小数部分が悪さをして，結果的におかしな値になってしまうことがあるのです。これは非常に稀なケースだと思うのですが，この問題ではちゃんとこのケースをはじくようなテストケースが与えられているようです。
つまり，整数の計算なら丸め誤差が生じないから，整数に直して計算しようとするが，コンピュータ内部で入力値が既に誤差を持っている場合，単純に１００倍したところで整数に戻らないわけです。

例えば，0.6 という数字を考えましょう。これは2進数では扱えない数ですから，コンピュータ内部では 0.5976・・・という値になっています。これをただ100倍しただけでは597.6・・・と，やはり小数部分が残ってしまいますよね。

この問題を解決する方法は色々あると思いますが，ここでは2種類紹介します。

解法１

一つ目は，数字を文字列として受け取った後に，小数を表す " . " を消すことで，10進法的に100倍するという考え方です。先ほどの 0.6 の例で行くと，

  • 0.60 を文字列として受け取る → b = “0.60"
  • " . " を消す → b = " 060 “
  • int 型に直す → b = 60 ※百倍になっている

このようにすれば，十進数的に100倍したことになります。

Pythonでの実装方法は，まず a,b を文字列として受け取った後に，a はそのまま int 型にして，b は replace(“.", " “)の作業をした後に int 型にします。これは b の文字列の中の “." を，何もないという意味の " " に置き換えている（"."を削除している) ということになります。これで a*b をした後に 100 で割った商を出してあげれば，得たい出力が得られます。これが解答例１です。

解答例１

a, b = input().split()

a = int(a)
b = int(b.replace(".", ""))

c = a*b // 100

print(c)

解法２

2つ目の解法は，Python ならではのものです。それは decimal モジュールを用いるというものです。これは，先ほどから述べている2進数表現による丸め誤差を無くすためのもので，10進数表現で厳密な計算ができるというものです。10進数の厳密な計算を行いたい場合にはこれを用いればいいので，これからこういう系統の問題を解く時にはこの Decimal モジュールを使えばいいのではないでしょうか。こちらのほうが解法1よりも汎用性が高くてお勧めです。使い方は次の通りです。

from decimal import Decimal

これでインポートした後に，文字列を使って十進数表現にします。具体的には，例えば 412 と 3.14 の計算を厳密に行いたい場合には，

a = "412" //文字列
b = "3.14" //文字列
dec_a = Decimal(a)
dec_b = Decimal(b)

print(a*b)

このように記述します。

上記のように10進数表現ができるので，あとは丸め誤差を恐れずに入力値 a と b の積を計算してやり，結果を int 型に直して出力してやりましょう。int 型に直すときには小数点以下は全て切り捨ててくれるので，今回の問題設定では単純に積を int 型に直して出力してやるだけで大丈夫です。

これが，次の解答例２です。

解答例２

from decimal import Decimal
a, b = input().split()

dec_a = Decimal(a)
dec_b = Decimal(b)

print(int(a*b))

いかがだったでしょうか。
小数の計算が怖いものだととても実感させてくれた非常に良い問題だったかと思います。これからは Python では decimal モジュールを使えばよさそうですね。何か悪い点があるのでしょうか。詳しい方，ぜひ twitter で教えてください。

少しでも参考になれば，twitter のフォロー，RT よろしくお願いします。
それでは！

AtCoder Beginner Contest 164 C を Python で

ABC C問題 AtcoderをPythonで

AtCoder Beginner Contest 164 C を Python で解説していきたいと思います。
それでは，早速解説していきます。
まずは問題文から。

C – gacha

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

くじ引きを N 回行い，i 回目には種類が文字列 Si で表される景品を手に入れました。

何種類の景品を手に入れましたか？

制約

  • 1≤N≤2×10^5
  • Si は英小文字のみからなり、長さは 1 以上 10 以下

入力

入力は以下の形式で標準入力から与えられる。

N
S1
:
SN

出力

何種類の景品を手に入れたか出力せよ。

入力例 1

3
apple
orange
apple

出力例 1

2

apple と orange の 2 種類の景品を手に入れました。

入力例 2

5
grape
grape
grape
grape
grape

出力例 2

1

入力例 3 

4
aaaa
a
aaa
aa

出力例 3

4

解説

文字列 S が N 個与えられ，その中で被りを無しで何種類のものがあるかを出力せよという問題です。
まずは S をリスト型で受け取ります。

Python では，重複しない要素の型である set 型というものがあります。これを使えば簡単に解けます。
set(S) で，S を重複のない型である set 型に変えることができるので，これの要素の数を出力します。
入力例１でこの関数がどう動くのか見てみます。

 

n = 3
S = ['apple’, 'orange’, 'apple’]
この状態で，
set_S = set(S)
# set (S) には 'apple’, 'orange’ が入っている。しかし順番はごちゃごちゃになってしまう。つまり
print(set_S)
# この出力が ['apple’, 'orange’] になるとは限らず， ['orange’, 'apple’] にもなりうる。

大変便利な型なので，ここで覚えておきましょう！
また，リストの長さは len を用いれば得ることができます。それでは，解答例に移ります。

解答例

n = int(input())
s =[]
for i in range(n):
    s.append(input())
 
print(len(set(s)))

いかがだったでしょうか。
もしよろしければ，twitter のフォロー，いいね，RT よろしくお願いします！
こちらの励みになります😁
それでは！