2020-12-07

Python3で解く AtCoder Regular Contest 110 B - Many 110

きれいに条件分岐ができればいい。

最初'0'にアサインできたら、最後、左から数えて何番目の'0'にアサインできるかを考える問題

概要
解くときに考えた内容
コード
- 全部場合分け
- 最低限
参考になる書籍

概要

問題

文字列 $s$ は'110'が $10^10$ 個連結したものである。
$n$ 文字の文字列 $t$ が与えられる。
$s$ に $t$ が連続する部分文字列としていくつ含まれる？

解くときに考えた内容

$t$ の長さ別に考える。
が1文字の場合
- = '1'の場合
  - $2 \times 10^{10}$ ('110'に2つ'1'があるから)
- = '0'の場合
  - $10^{10}$ ('110'に1つ'1'があるから)
が2文字の場合
- = '11'と'10'の場合
  - $10^{10}$ ('110'に1つ'11'または'11'があるから)
- = '01'の場合
  - $10^{10}-1$ (最後の1つは取れないので-1)
- = '00'の場合
  - $0$ （このパターンはないので）
が3文字以上の場合は0ががあるので、の0のどこまでアサインできるかということになる。
- $t$ の長さを3で割って切り上げる。
- この値は $t$ に含まれる0の個数であり、cntとする。
- ここで、'110'をcnt分連結した文字列に含まれるかどうかで、カウント対象であるかと、その文字列が0で終わっているのか1で終わっているのかを同時に判定する（結構キモ）
- '110'をcnt分連結した文字列にtが含まれるなら、tが0終わりでsに存在ということ。
  - 例えば、
    - 0110とすると、cnt = 2であり、 $s$ の0の最後……11'0110'、 $10^{10} - 1$ 個目まで取れる。
    - 0110110とすると、cnt = 3であり、 $s$ の0の最後……11'0110110'、 $10^{10} - 2$ 個目まで取れる。
  - 一般に、 $10^{10} - (cnt - 1)$ となる。
- '110'をcnt分連結した文字列にtが含まれず、'110'をcnt分+1連結した文字列にtが含まれるなら、tが1終わりでsに存在ということ。
  - 例えば、
    - 011とすると、cnt = 1であり、 $s$ の0の最後……11'011'0、 $10^{10} - 1$ 個目まで取れる。
    - 011011とすると、cnt = 2であり、 $s$ の0の最後……11'011011'0、 $10^{10} - 2$ 個目まで取れる。
  - 一般に、 $10^{10} - cnt$ となる。
  - これらに当てはまらないものは $s$ に $t$ が含まれないので $0$

f:id:black_tank_top:20201206095202j:plain — 部分文字列のカウントイメージ

上図のように、 $t$ が3文字以上で $s$ に含まれるその他のパターンも同じ様に書いてみると、最初'0'にアサインできたあと、最後の左から数えて何番目の'0'にアサインできるかを考える問題であると言うことがわかる。

コードは全場合分けベースで書いたものと、 $t$ が2文字のものも3文字のものと同様に考えて問題ないので、２種類にかき分けた。

コード

全部場合分け

n = int(input())
t = input()
m = 10**10
# 切り上げ
if len(t) % 3 == 0:
    cnt = len(t) // 3
else:
    cnt = len(t) // 3 + 1
# sにｔが存在する出力パターン
# tのサイズが1のとき
if t == '1':
    print(2*m)
elif t == '0':
    print(m)
# tのサイズが2のとき
elif t == '11' or t == '10':
    print(m)
elif t == '01':
    print(m-1)
elif t == '00':
    print(0)       
# tのサイズが3以上のとき
elif len(t) >= 3:
    # この書き方ならt = 0, 11などもここに含めても可能
    # 個数倍復元して含まれているなら、tが0終わりでsに存在
    if t in '110' * cnt:
        print(m-cnt+1)
        exit()
    # 上記でなくて個数倍+1で復元して含まれているなら、tが1終わりでsに存在
    elif t in '110' * (cnt+1):
        print(m-cnt)
        exit()
    # 上記以外はsにｔが存在しない出力パターン  
    else:
        print(0)

最低限

n = int(input())
t = input()
m = 10**10
if len(t) % 3 == 0:
    cnt = len(t) // 3
else:
    cnt = len(t) // 3 + 1
# tが1のとき
if t == '1':
    print(2*m)
    exit()
# それ以外の時（tが0や、2文字以上のときはこの記述で集約できる）
if t in '110' * cnt:
    print(m-cnt+1)
    # 上記でなくて個数倍+1で復元して含まれているなら、tが1終わりでsに存在
elif t in '110' * (cnt+1):
    print(m-cnt)
# 上記以外はsにｔが存在しない出力パターン  
else:
    print(0)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本

７章までは別記事に残してある。 blacktanktop.hatenablog.com

2020-12-06

Python3で解く AtCoder Regular Contest 110 A - Redundant Redundancy

AtCoder 競プロ ARC 300点最小公倍数

問題の制約がゆるすぎて、 $n=30$ のときの答えをprintするだけで終わる。

print(2329089562801)

なので、解説記事としては候補のうち最小という状態で考えるとした場合にする。

概要

問題

整数 $n$ が与えられる。
$2$ から $n$ までのすべての整数で割って余りが $1$ になるような $n$ 以上 $10^{13}$ 以下の値は？

この制約が甘いので、 $n$ がどんな値でも $n=30$ のときの答えを書けば良くなる。

解くときに考えた内容

上記のような事があるとしても、考え方としては、 $n=30$ でも一緒。

文意から、 $2$ から $n$ までのすべての整数で割り切れる数に $1$ を足せば、条件を満たす。

ちなみに記事冒頭の値は、30以内の素数を何回かかけた値のうち30以内のものをかけ合わせた値+1である

# 上記のコードでn=30としたときの値を入れてもACにはなる
print(2329089562801)
# ちなみにこれは、30以内の素数を何回かかけた値のうち30以内のものをかけ合わせた値+1である
# 30以内の素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29
print(2**4 * 3**3 * 5**2 * 7 * 11 * 13 * 17 * 19 * 23 * 29 + 1)
# 2329089562801

コード（候補のうち最小とするならば以下）

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcd(a, b):
    return int(a / gcd(a, b)) * b
def mod_lcd(n, mod):
    ans = 1
    for i in range(2, n+1):
        ans = lcd(ans, i)
    return ans + mod  
n = int(input())
ans = mod_lcd(n, 1)
print(ans)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本

７章までは別記事に残してある。 blacktanktop.hatenablog.com

2020-12-04

Python3で解く AtCoder Beginner Contest 153 D - Caracal vs Monster

AtCoder 競プロ ABC ABC-D パターン発見

愚直に、1~hまでどんな風になるかをリストで残そうとすると、TLEになる様な制約なので、いい感じのパターンを見つける必要がある。
どんな人数になるかがちょっとよくわからないので、とりあえず書き出す。そうするとパターンが見えてくる。

概要

問題

モンスターが1体いて体力は $h$ 。
モンスターを攻撃する。
その時にモンスターの体力が $1$ なら倒せる。
その時にモンスターの体力が $1$ より大きい時は、体力が半分（切り下げ）になって、２体になる。
攻撃回数の最小となるような攻撃回数は？

解くときに考えた内容

サンプルをみると、1, 3, 3, 7となっている。
DPっぽくやるのかなとおもったけどモンスターの体力の制約が $h \leqq 10^{12}$ なので、無理そう。
モンスターの体力が $h$ が1, 3, 7, 15の時は攻撃回数も1, 3, 7, 15。モンスターの体力が $h$ が1, 2, 4, 8の時は攻撃回数も1, 3, 7, 15。つまり、hが $2 ^ i \leq h \leq 2 ^{i+1}-1$ の範囲であれば、必要な攻撃回数は $2 ^{i+1}-1$ ということになる。 (画像に番目って書いてあるけどhの値だったな。。。)
hが2ⁱ~2ⁱ-1のモンスターを倒すのに必要な攻撃数のイメージ
なので、 $2 ^ i \leqq h$ まで調べれば良いので $O(logN)$

コード

h = int(input())
ans = 1
if h >= 1:
    i = 0
    while 2**i <= h:
        ans = 2**(i+1) - 1
        i += 1
print(ans)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本

７章までは別記事に残してある。 blacktanktop.hatenablog.com

2020-11-29

Python3で解く AtCoder Regular Contest 109 B - log

AtCoder 競プロ 400点 ARC

長さ $n+1$ の丸太を買って、短い方から丸太を作れるだけ作って、残りは買う。 $n$ -（作れるだけ作った数）+ 1が答え。作れるだけ作った数をどうかんがえるかがポイント

概要

問題

長さ $1$ から $n$ の $n$ 種類の丸太がほしい。
長さ $1$ から $n+1$ が各 $1$ ずつ、各1円で売ってる。
自由に切ってよい。例えば長さ $5$ の丸太を長さ $2$ と長さ $3$ としていい。
余ったものは捨ててよい。
このとき、 $n$ が与えられたときに、長さ $1$ から $n$ の $n$ 種類の丸太を用意する最小の金額は？

解くときに考えた内容

長さ $n+1$ の丸太を買って、短い方から丸太を作れるだけ作って、残りは買う方針でいく。これが最小なのは自明ではないが、証明はしない。
$n+1$ から作れるだけ作るときに長さ $1, 2, ... k$ の $k$ の最大値を求める必要がある。
$1, 1+2, 1+2+3, ... 1+2+3+..+k$ のような数列と $n+1$ を比較して、最大の $k$ を求めたい。
等差数列の和の数列なので、 $\frac{k(k+1)}{2}$ のリストを制約分作ってもいいけど、作ると終わらない。
bisectはリストが無いとできないので、ここでは使えない。
ここでは、リストがない状態での二分探索を行う必要がある。（これまで、なぜわざわざこのような実装しているのかわからないときがあったが、このような状況のときに有効ということがわかった。）

普通の二分探索の実装で、 $n+1$ とmidの値と比較するべきところを $n+1$ と等差数列の和として $\frac{mid(mid+1)}{2}$ を比較するようにして、探索していくようにする。

コード

def log_cut(n):
    l = 0
    r = n
    while r - l > 1:
        mid = (l+r) // 2
        # ここの比較がポイント
        # リストも与える二分探索だとlist[mid]とn+1を比較するが
        # 今回はリストではなく、mid自体の値を使って、等差数列の和と比較する。
        if mid * (mid+1) // 2 <= (n+1):
            l = mid
        else:
            r = mid 
    return l
    n = int(input())
# これが作れる分のkの最大値
max_log = log_cut(n)
# n - max_log（買う分）+ （1, 2, ... , kは１本）
ans = n - max_log + 1
print(ans)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本

７章までは別記事に残してある。 blacktanktop.hatenablog.com

2020-11-29

Python3で解く AtCoder Regular Contest 109 A - Hands

AtCoder 競プロ 300点 ARC 条件分岐

状態を把握するのに、ちょっと時間はかかったが、イメージはできた。しかし場合分けが多く、そこにハマったのでまとめる

概要

問題

100階建ての建物 $A, B$ がある。
$A_i$ と $B_i$ は廊下でつながっていて、 $x$ 分かかる。
$A_{i+1}$ と $B_i$ は廊下でつながっていて、 $x$ 分かかる。
$A_i$ と $A_{i+1}$ および $B_i$ と $B_{i+1}$ は階段でつながっていて、 $y$ 分かかる。
与えられた、 $A$ 階から $B$ 階へ最短時間で移動したときの時間は？

解くときに考えた内容

まずイメージ図

f:id:black_tank_top:20201129095551j:plain — 全体のイメージ

文意から、１００階建ての建物 $A, B$ は上の一番左のようになっている。
$y, 2x$ の大小で降りる手段として、廊下か階段かを選択すべきかがわかり、最後は $B$ へ移動するのに $x$ という構図。降りるときと登るときとでことなるのは降りるときしか $B$ へ移動できないので、そこで場合分けが必要。
まずは、が同じフロアの場合、もしくはからが１階降りる場合。
- $x$ が最短。
  （なぜなら、 $1 \leq x, y \leq 100$ なので、 $x \lt x + y$ は自明）
次に２階以上降りる場合。
- $B - A$ を $step$ とすると
- ということ。
  - １階おりるのに $y \geq 2x$ のとき、廊下を選んで $2x$ で $step-1$ 階降りて、最後に $x$ で $B$ へ行く
  - １階おりるのに $y \lt 2x$ のとき、階段を選んで $y$ で $step-1$ 階降りて、最後に $x$ で $B$ へ行く
次に１階以上登る場合。
- これ上記の $step-1$ を $step$ と考えればいい。

コード

a, b, x, y = map(int, input().split())
step = b - a
if step == 0 or step == -1:
    ans = x
# 下に-1を含めても良い。結果xになるから
elif step <= -2:
    if y >= 2 * x:
        ans = (abs(step)-1) * 2 * x + x
    else:
        ans = (abs(step)-1) * y + x
elif step >= 1:
    if y >= 2 * x:
        ans = step * 2 * x + x
    else:
        ans = step * y + x
print(ans)

終わりに

結構きれいに場合分けしないと、うまく行かない。絵に書けばだいたい分かるが、時間かかりすぎた。

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本

７章までは別記事に残してある。 blacktanktop.hatenablog.com

2020-11-29

AtCoder Regular Contest 109 参加ログ・感想

参加ログ AtCoder 競プロ ARC

内容
結果
どう考えたか + α
- A - Hands
- B - log
おわりに
参考になる書籍

内容

Python3でやっている。
参加ログ。
所感。
コンテスト中に何を考えたか。
コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
問題の詳細で細かく書こうと思うものは別記事とする。

結果

Aをなんとか完。Bはどうやるのが最小になるのかを探ってる間に終了。解説みて、この二分探索は書けなかっただろうなぁと思った。

どう考えたか + α

問題

A - Hands

問題タイプ：条件分岐階段のステップ差の符号、２フロア以上かどうかで場合分けする必要がある。あと、ポイント $y$ , $2x$ の大小でどう進むかを決める。別記事にする。

追記：別記事書いた。

blacktanktop.hatenablog.com

B - log

問題タイプ：二分探索

長さ $n+1$ の丸太を買って、短い方から丸太を作れるだけ作って、残りは買う。

$n$ - （作れるだけ作った数） + $1$ が答え。作れるだけ作った数をどうかんがえるかは別記事にする。

追記：別記事書いた

blacktanktop.hatenablog.com

おわりに

Aは、上りと下りで条件が違うのと、2フロア以上の移動かどうかで違うところで、上りと下りの条件を分け忘れててWAを連発・・・
Bは、二分探索はリストがある状態のものばかりやってたので、リストがない状態でやるいい例になった。

先週結構上がった分がそのまま落ちて、なんだかなーってなった。まぁこれも実力。

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本

7章まで、Pythonで章末問題をこなした。

blacktanktop.hatenablog.com

2020-11-26

ガーデニング

日常

たまには日常。

特に趣味じゃないが、庭に花を植えてみた。

庭を掘って花を植えた。
掘って出てきた大きい石は縁にしてレンガ代せつやくでいい気がしてきた。ちょっと見た目悪いけど
1週間くらい経つけど新しい芽というか蕾も伸びてきて普通に育つな pic.twitter.com/aiaVecJFzD
— くろたんく@激しく多忙 (@black_tank_top) 2020年11月8日

1ヶ月もしないうちに、ラベンダーも成長を遂げていい感じになったり、

庭に植えたラベンダーがいい感じに成長してる pic.twitter.com/DnFLNAZEK5
— くろたんく@激しく多忙 (@black_tank_top) 2020年11月21日

スイートアリッサムも最初よりも花が開いてる。土買ったり、水上げたりそこそこ面倒だけどまぁいい感じ。

植えてから、天気がいいせいかスイートアリッサムの花がたくさん開いてモリモリになってきた

新たに植えたチョコレートコスモスとコスモスも蕾が開いた pic.twitter.com/mBDicQIm85
— くろたんく@激しく多忙 (@black_tank_top) 2020年11月25日

概要

解くときに考えた内容

コード

全部場合分け

最低限

参考になる書籍

目次

概要

解くときに考えた内容

コード（候補のうち最小とするならば以下）

参考になる書籍

目次

概要

解くときに考えた内容

コード

参考になる書籍

目次

概要

解くときに考えた内容

コード

参考になる書籍

目次

概要

解くときに考えた内容

コード

終わりに

参考になる書籍

内容

結果

どう考えたか + α

A - Hands

B - log

おわりに

参考になる書籍