2020-12-06

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

問題の制約がゆるすぎて、 $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)

参考になる書籍

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

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

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

問題解決力を鍛える!アルゴリズムとデータ構造 (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日

2020-11-23

Python3で解く AtCoder Beginner Contest 184 D - increment of coins

AtCoder 競プロ ABC-D 確率DP DP メモ化再帰

単純な確率問題でラッキーと思ったら、しっかりDPとの組み合わせだった。（そりゃそうだDだもの）

概要

問題

金貨が $a$ 枚、銀貨が $b$ 枚、銅貨が $c$ 枚袋に入ってる。
袋の中にあるいずれかの種類の硬貨が枚になるまで以下の操作を繰り返す。
- ランダムに袋から $1$ 枚取る。
- 取ったものと同じ種類の硬貨を $2$ 枚袋に戻す。（要するに取ったものが $1$ 枚増える）
  （この意味が最初わからかなかった。どこから硬貨が湧いて出てくるのかとかを不必要に考えてしまった。）
操作回数の期待値は？

解くときに考えた内容

金貨を引く確率×金貨を引いた時の操作回数の期待値＋銀貨を引く確率×銀貨を引いた時の操作回数の期待値＋銅貨を引く確率×銅貨を引いた時の操作回数の期待値というのをDPで解く。
上記は、再帰で解く必要がある。関数の中身は、
- いずれかが100枚だったら、0を返すようにしておく。
  - 99枚のときに引いた時の操作回数の期待値が0になるイメージ。
  - すべての硬貨が99枚のときはどれを引いてもあと1回で終了。
  - つまり、再帰の一番の元はmemo[99][99][99] = 1ってこと。
あとは、メモ化をきちんとしておけばよい。
普段DPは0, 1, 2などを初期値を規定して所定の値の結果を求めるイメージだが、今回は再帰ですべてが99の状態を起点に元に逆流して答えが求まるイメージで組み立てる。
今回この問題を解くにあたり、functools.lru_cacheという便利な関数があることを知った。
docs.python.org 再帰の関数を@lru_cacheとデコレータするだけで、自動的にメモ化してくれる。実装例を見るとmemoのところをすべてすっ飛ばして良くなるので超楽ちん。

コード

リストでメモ化

テストのhand_03.txtの結果。 f:id:black_tank_top:20201124054353p:plain

def memo_exp(a, b, c):
    exp = memo[a][b][c]
    if exp != None:
        return exp
    if a == 100 or b == 100 or c == 100:
        return 0
    sum_all = a + b + c
    memo[a][b][c] = 1 + a / sum_all * memo_exp(a + 1, b, c) + \
        b / sum_all * memo_exp(a, b + 1, c) + \
        c / sum_all * memo_exp(a, b, c + 1)
    return memo[a][b][c]

a, b, c = map(int, input().split())
memo = [[[None] * 101 for _ in range(101)] for _ in range(101)]
print(memo_exp(a, b, c))

テストのhand_03.txtの結果。

lru_cache（超便利）

テストのhand_03.txtの結果。 f:id:black_tank_top:20201124054820p:plain memo化と比べると、時間もメモリも食うのがわかる。
（今回は1例だけ上げていているがほとんどのサンプルで同じ傾向）なので、メモリと時間的制約の余裕があればこちらで良さそう。

from functools import lru_cache
@lru_cache(None)
def lru_exp(a, b, c):
    if a == 100 or b == 100 or c == 100:
        return 0
    sum_all = a + b + c
    return 1 + a / sum_all * lru_exp(a + 1, b, c) + \
        b / sum_all * lru_exp(a, b + 1, c) + \
        c / sum_all * lru_exp(a, b, c + 1)
a, b, c = map(int, input().split())
print(lru_exp(a, b, c))

参考になる書籍

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

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

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

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

目次

概要

解くときに考えた内容

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

参考になる書籍

目次

概要

解くときに考えた内容

コード

参考になる書籍

目次

概要

解くときに考えた内容

コード

参考になる書籍

目次

概要

解くときに考えた内容

コード

終わりに

参考になる書籍

内容

結果

どう考えたか + α

A - Hands

B - log

おわりに

参考になる書籍

目次

概要

解くときに考えた内容

コード

リストでメモ化

lru_cache（超便利）

参考になる書籍