くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU

Python3で実装 問題解決力を鍛える!アルゴリズムとデータ構造【第3章】設計技法(1):全探索

「問題解決力を鍛える!アルゴリズムとデータ構造」の章末問題をPython3で実装していくシリーズ。(続くかわからんが)

今回は【第3章】設計技法(1):全探索について扱う

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

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

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)


内容

  • Python3でやっている。
  • 簡単に自分の理解を整理する用。
  • そこまで厳密ではない可能性が高い。
  • 記事を書いたら、書評の方に記事を載せていく。
  • コード等はGitHubにおいた。 github.com

【第3章】設計技法(1):全探索の概要

ここの章で特に大変というか慣れないときついのはbitの考え方。組み合わせ探索のところがちょっと大変。

章末問題

3.1 線形探索で一致する最大のindex探し

こんな入力を想定して

10 7
3 5 8 9 7 10 22 1 2 100
  • 配列{\displaystyle a}を左から見ていって、{\displaystyle v}と一致する値があるか確認する。
  • 一致したら、indexを代入とする。
def main():
    # 入力受け取り
    N, v = map(int, input().split())
    a = [int(x) for x in input().split()]
    # 初期化としてあり得ない数値を代入
    found_id = -1
    for i in range(N):
        if a[i] == v:
            found_id = i
    print(found_id)
if __name__ == '__main__':
    main()
3.2 線形探索で一致する数をカウント

こんな入力を想定して

10 7 
3 5 8 9 7 7 7 7 7 1

3.1を少し変えて、 * 配列{\displaystyle a}を左から見ていって、{\displaystyle v}と一致するか確認する。 * 値が一致したら、カウントをインクリメントする。

def main():
    # 入力受け取り
    N, v = map(int, input().split())
    a = [int(x) for x in input().split()]
    # 線形探索
    cnt = 0
    for i in range(N):
        if a[i] == v:
            cnt += 1
    print(cnt)
if __name__ == '__main__':
    main()
3.3 線形探索で最も小さいとその次に小さい探す

こんな入力を想定して

10 7
3 5 8 9 7 10 22 1 2 100
  • 二番目に小さい値(second_minv)をどうとるかで、配列{\displaystyle a}を左から見ていく時に、最小値(minv)よりも小さい値を見つけたか、2番目に小さい値を見つけたかで場合分けする。
def main():
    # 入力受け取り
    N = int(input())
    a = [int(x) for x in input().split()]
    # 初期化として無限大
    minv = float('inf')
    second_minv = float('inf')
    for i in range(N):
        # 最小値を見つけた場合
        if a[i] < minv:
            # minvを2番目に
            second_minv = minv
            # 探索した値をminvに
            minv = a[i]
        # 2番目に小さい値を見つけた場合
        elif a[i] < second_minv:
            second_minv = a[i]
    print(second_minv)
if __name__ == '__main__':
    main()
3.4 maxとmin

こんな入力を想定して

10 7
3 5 8 9 7 10 22 1 2 100
  • for文で探索するというよりは、関数的にmaxとminを求めて、引き算する。
  • 別の方法として、maxvとminvを保持しながらforで回してもいい。
def main():
    # 入力受け取り
    N = int(input())
    a = [int(x) for x in input().split()]
    # 最大・最小を求めて引き算
    # max, minの計算量はO(n)
    maxv = max(a)
    minv = min(a)
    ans = maxv - minv
    print(ans)
if __name__ == '__main__':
    main()
3.5 半分にし続けられる回数

こんな入力を想定して

6
382253568 723152896 37802240 379425024 404894720 471526144

リスト内包表記で2で割り切れるかどうかでboolを返すようにして、all()ですべてがTrueならカウントをインクリメントして、リストの中身を半分にしたものを再度代入と言うのを繰り返す。配列で扱っている時は、リスト内包表記が便利。

def main():
    # 入力受け取り
    N = int(input())
    a = [int(x) for x in input().split()]
    cnt = 0
    # aがすべて2で割り切れている(全部Trueなら回り続ける)
    while all([True if i % 2 == 0 else False for i in a]):
        cnt += 1
        a = [i / 2 for i in a]
    print(cnt)
if __name__ == '__main__':
    main()
3.6 2重for文で3つ変数の全探索

こんな入力を想定して

2 2

{\displaystyle O(n^2)}で実装しろってことなので、{\displaystyle x, y, z}の3重のfor文はできない。そこで、{\displaystyle z = n - x - y}であることを用いて、zが{\displaystyle 0 \leq z \leq}を満たすものをカウントすればいい。そうすれば2重のfor文で済むので{\displaystyle O(n^2)}で実装できた。

def main():
    k, n = map(int, input().split())
    cnt = 0
    # 0-kまで探索 
    for x in range(k+1):
        # 0-kまで探索
        for y in range(k+1):
            # z = n - x - yなので0以上k以下ならカウントする
            if 0 <= n - x - y <= k:
                cnt += 1
    print(cnt)
if __name__ == '__main__':
    main()
3.7 bitで全探索

こんな入力を想定して

125

いったんの目標として、以下のような式を作って評価して、その合計を足し合わせればいい。
{\displaystyle 125}
{\displaystyle 1 + 25}
{\displaystyle 12 + 5}
{\displaystyle 1+ 2 + 5}
どのように作るかと言うと、数字の文字の間に'+'を入れ込むと考える。数字の文字数を{\displaystyle n}とすると{\displaystyle n-1}個間があって、そこに'+'が入るかどうかの2通りだから{\displaystyle 2^{n-1}}パターンあることになる。
そして、そのパターンを作る時に色々やり方はあるが、書籍に倣うと、bitを用いることで全パターンを生み出す。上記の例だと、文字の間が2つなので、 [0, 0] → {\displaystyle 125}
[1, 0] → {\displaystyle 1 + 25}
[0, 1] → {\displaystyle 12 + 5}
[1, 1] → {\displaystyle 1+ 2 + 5}
の4パターンで、1が立っているところに'+'が入っている状態が、目標とする状態であることがわかる。それで、どう作るかと言うと、bit演算子を使いながら実装する。

  • 最初のfor文の範囲は{\displaystyle 2^{n-1}}でいいんだけど、あえてbit演算子で書く以下のようになる。 1 << (n-1) これはなんぞってなるんだけど、砕くと、

1 << i の意味は
2進数表現で右からi番目(一番右は0番目として)のみ1がである値を10進数表現に戻した値。

なので例えば、今回だと、{\displaystyle n-1 = 2}なので、右から2番目のみが1である値(一番右は0番目として)は、'0b100' なので、これを10進数表現に戻すと{\displaystyle 2^2 = 4}である。

  • 肝心の全パターンのbitを立たせる方法は以下である。
for bit in range(1 << (n-1)):
    for i in range(n-1):
        if ((bit>>i)&1) == 1:
        ~~~

ここで、(bit>>i)&1って言う初心者泣かせの演算が出てくるんだけど。砕くと、

(bit>>i) の意味は
bit >> i はbitを2進数表現でi個右にずらした(右からi個削った)値を10進数表現に戻した値

例えば、
4 >> 1は '0b100'→'0b10'っていうことで10進数表現に戻されて、2となる。
3 >> 1は '0b11'→'0b1'っていうこと10進数表現に戻されて、1となる。 これは実際にコンソールで叩いてみながらやると良い。確認で2進数表現にしたければbin()でできるので。

ほんでもう一つ、(bit>>i)&1&1ってなんぞっていうことなんだけど、砕くと、

a & bは、
aとbを2進数表現でみた時に、同じ桁がどちらも1の時に1を返しその他の場合は0をかえした値を10進数表現に戻した値

なので、x & 1っていうのはxを2進数表現でみた時に一番右が1なら1そうでないなら0って言うことになる。これらを全て使うと、全パターンのbitをたてられる。 実装上はフラグの立ち方をわかりやすい形でにみることはできないので、あえて配列に残るように書いておいた。(bitsっていうリスト)

  • あとは出来上がった式をeval()で評価していけばいい。
  • もしくは、'+'でsplitして配列にして足せばいい。(この場合は'+'っていう文字はただの飾りにはなる)
def main():
    # 入力受け取り
    s = input()
    n = len(s)
    ans = 0
    # 1 << i は2進数表現で右からi番目(一番右は0番目)のみ1がである値のことなので
    # 2**iと同義
    # 数文字の間に'+'を入れるかどうかなので2**(n-1)パターンある
    for bit in range(1 << (n-1)):
        formula = s[0]
        # bitの立ち方確認用
        bits = []
        for i in range(n-1):
            bits.append((bit>>i)&1)
            if ((bit>>i)&1) == 1:
                formula += '+'
            formula += s[i+1]
        # 状況確認用
        # print(bits)
        # print(formula)
        # split sum方式
        # ans += sum(map(int, formula.split('+')))
        # eval方式
        ans += eval(formula)
    print(ans)
if __name__ == '__main__':
    main()

まとめ

  • 全探索は計算量が多くなることがあるので制約に注意。
  • maxvとかminvで一時的にそこまでで最大とか最小っていう値をとっておいて比較しながらforを回すように使うことが多い。
  • bit演算は覚えることたくさんだけど、使えるようになると便利っぽい。(わかんなくなって、itertoolsで代用しちゃうけど)

終わりに

結構ちゃんと書くと大変。まとめる方が時間かかるなぁ。続けるか未定。

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

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

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)


AtCoder Regular Contest 105 参加ログ・感想

普段は、AtCoder Beginner Contestにでているが、とりあえず挑戦という事で、Bまで解ければ良いと思ってAtCoder Regular Contestに初参加してみた。


内容

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

結果

A完。Bは愚直解しか思い付かず、TLE連発(そもそもあってるのかも謎。)Bの問題文を読んで最大公約数って言うところに気づけず悶絶し続け終了。


どう考えたか + α

A - Fourtune Cookies

問題タイプ:全探索

1つ以上をお菓子を選ぶ必要があるので、A, B, C, Dから * 1つ選ぶパターン → 残り3つと比較 * 2つ選ぶパターン → 残り2つと比較 の場合を考えれば良いだろうと考えた。これらが満たされるなら、矢印が逆の場合は考える必要がないので。

  1. A, B, C, Dを別々に持たず、リストでもつ。
  2. A, B, C, Dの合計を計算する(abcd_sum)。
  3. まずは、1つ選ぶパターンの探索をする。
    1. abcd_sumから1つ選んだものを引いてそれと1つ選んだものが一致するかを見る。
  4. 上記で一致しなければ、2つ選ぶパターンの探索をする。
    1. abcd_sumから1つ選んで引く。(i)
    2. さらにindexを進めながら引く。 (j:i以降のindex全部)
    3. abcd_sumから2つ選んだもの引いてそれと2つ選んだ合計が一致するかを見る。
  5. ここまでで一致がなければ'No'である。

今書いてて、もう少し効率よくできそうな気もする。

abcd = [int(x) for x in input().split()]
abcd_sum = sum(abcd)
for i in range(4):
    if abcd_sum - abcd[i] == abcd[i]:
        print('Yes')
        exit()
for i in range(4):
    for j in range(i, 4):
        if abcd_sum - abcd[i] - abcd[j] == abcd[i] + abcd[j]:
            print('Yes')
            exit()
print('No')

B -

問題タイプ:最大公約数を使う問題

正直、問題を見て愚直にしか考えられず、優先度付きキューかなと思ってやってみたがTLE。最大値 - 最小の値を戻すっていうのを繰り返すが、この処理がどのくらいの処理数になるのかを見積もれなかったのが失敗。今考えると{\displaystyle O(n^9)}から{\displaystyle O(n^10)}くらいはありそう。 なんとなくだけど(全てが、最小値になる状態なので、{\displaystyle \frac{10^5 \times 10^5}{2}}

で、結局これは全部の最大公約数と一致するって言うのが答えで、gcd(x, y) = gcd(x, y - x)と言うのが理由だから。これは今回の手続きと同じである。(自分で証明はしてない)

def gcd(a, b):
    if b == 0:
       return a
    else:
        return gcd(b, a%b)
n = int(input())
A = [int(x) for x in input().split()]
ans = A[0]
for i in range(1, n):
    ans = gcd(ans, A[i])
print(ans)

おわりに

Aはできたが、Bは数学の感覚が悪すぎた。制約が気持ち少なければそこまで悪くないと思ったんだけど。 ARCはBまでを早く解けるように続けてみる。


参考になる書籍

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

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

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

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

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)

Python3で解く HHKB プログラミングコンテスト 2020 C - Neq Min

順番に与えられる、{\displaystyle p}を集合で管理して、その中に前回出力した値が含まれるかどうかを判定してあげるっていうこと。

目次

概要

問題

  • 長さ{\displaystyle n}の数列{\displaystyle p_1, p_2, ... , p_{n-1}, p_n}が与えられる。
  • {\displaystyle i (1, 2, ..., n)} について、 0以上の整数で {\displaystyle p_1, p_2, ... , p_i}のいずれとも等しくない値のうち最小値は?

解くときに考えた内容

出力したい値をsetとリストで管理する(TLE)

出力する値は0~nまでの値なので、{\displaystyle p_i}と一致しないように、{\displaystyle p_i}の「値を削除」してその時の一番小さい左側の値を出力する。

  1. {\displaystyle 0, 1, 2, ..., n}という集合(n_set)とリスト(n_list)を作る。
  2. n_setに{\displaystyle p_i}があったら、n_setとn_listから{\displaystyle p_i}を取り除く。
  3. n_listのindexが0を出力する。

ただこれでは、すべての{\displaystyle i}をforで処理することで{\displaystyle O(n)}でその中で「値を削除」する処理が{\displaystyle O(n)}(さらにそれを2回)なので {\displaystyle O(n^2)}になってしまう

既出のpをsetか配列かで管理する

出力予定の値(ans)ではなく、{\displaystyle i}番目ごとの{\displaystyle p_i}までの値を集合(p_set)で管理して、p_setにansが「含まれない状態になる」までansをインクリメントする。

  1. 出力用の変数(ans)を0とする
  2. forで{\displaystyle p_i}を回すたびに集合(p_set)に加える。
  3. p_setにansがなくなるまで、ansをインクリメントする。
  4. ansを出力する。

ちなみにリストで管理する方法もある。コードは載せておく。(集合の方がわかりやすいとは思う。)

全体的なイメージだと{\displaystyle p_i}を回すたびにp_setに加えられて、ansのインクリメントは多くても{\displaystyle n}回しか行われないっていうところに気付けるかがポイント。

# ansがどんどこ伸びていく感じ
# だけど、一度増えたらそこからまた増やすから
# インクリメントは最大でもn回
0 ... ... ... ... ... .. n
--->->--->----------->->

しゃくとりっぽい感じ。 このように平均的にクエリの計算量が{\displaystyle O(1)}になるようなもの(もしくは計算量が平均的にならされるものってことだと思うんだけど)をならし計算量というそうだ。

詳細は、けんちょんさんのブログを見るといい。

drken1215.hatenablog.com


コード

答えをリストで管理する場合(TLE)
n = int(input())
P = [int(x) for x in input().split()]
n_list = list(range(n))
n_set = set(n_list)
for p in P:
    if p in n_set:
        # この処理はO(n)
        n_set.remove(p)
        n_list.remove(p)
    print(n_list[0])
pをsetで管理する場合(AC)
n = int(input())
P = [int(x) for x in input().split()]
p_set = set()
ans = 0
for p in P:
    p_set.add(p)
    # ansが含まれなくなるまで+1する
    while ans in p_set:
        ans += 1
    print(ans)
pをリストで管理する場合(AC)
n = int(input())
P = [int(x) for x in input().split()]
u = [False for _ in range(200001)]
ans = 0
for p in P:
    u[p] = True
    while u[ans]:
        ans += 1
    print(ans)

書籍

アルゴリズムの参考書籍

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

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

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

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

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。(AtCoderもそんな感じのリスト作って欲しい) ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。(AOJも解いているので、記事にしていこうかなぁ)

最近ポチった書籍

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク強化学習教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。

blacktanktop.hatenablog.com

書評は書いてある。本家にはnotebookがなかったので、一番簡易的に試せるJupyter notebookも以下のrepositoryに置いたのですぐ試せる。

github.com

HHKB プログラミングコンテスト 2020 参加ログ・感想

久しぶりの企業のコンテスト。 最近諸事情により全然精進していないので結果的にはいまいちだったが、久しぶりだったので楽しかった。


内容

  • Python3でやっている。
  • 参加ログ。
  • 所感。
  • コンテスト中に何を考えたか。
  • コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
  • 問題の詳細で細かく書こうと思うものは別記事とする。
  • E以上はとりあえず現状自力では無理なのでやってもDまで。解けるようになってきたら更新するかも

結果

AB完。 Cはもうちょい柔軟に考えないとだった。元のリストの[0, 1, 2, ... n-1, n]に着目しすぎた。何方かと言えば、既出のPに着目するように考えないとだめ。


どう考えたか + α

A - Keyboard

問題タイプ:条件分岐・文字列操作 Sの値が'Y'ならYを大文字に Sの値が'N'ならYをそのままに

s = input()
y = input()
if s == 'Y':
    print(y.upper())
else:
    print(y)

B - Futon

問題タイプ:隣合わせの条件

要するに、以下をカウント 1. 行方向に見たときに'.'が連続しているかどうか。 1. 列方向に見たときに'.'が連続しているかどうか。 入力から読み込んだ時は行方向にlistになるので、まずは行方向からカウント、終わったら転置して(trans(x)が転置の自作関数)、同じやり方で列方向をカウント。

# 多重リストの転置関数
def trans(x):
    return ([list(i) for i in zip(*x)])

h, w = map(int, input().split())
S = [[v for v in input()] for _ in range(h)]
cnt = 0
# まずは行方向の'.'の連続
for s in S:
    for i in range(1, w):
        if s[i-1] == '.' and s[i] == '.':
            cnt += 1
# 次に列方向の'.'の連続
ST = trans(S)
for s in ST:
    for i in range(1, h):
        if s[i-1] == '.' and s[i] == '.':
            cnt += 1
print(cnt)

C - Neq Min

問題タイプ:集合

{\displaystyle P}を一つずつ取り出して、set()して、その集合に前の時に答えた値(最初は0)が含まれるなら+1するをしてから値をprint()すればいい。 リストをremoveとかでやろうとすると{\displaystyle O(N^2)}でアウト

別記事にする。


おすすめの書籍

アルゴリズムの参考書籍

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

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

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

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。(AtCoderもそんな感じのリスト作って欲しい) ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。(AOJも解いているので、記事にしていこうかなぁ)

最近ポチった書籍

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク強化学習教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。

blacktanktop.hatenablog.com

書評は書いてある。本家にはnotebookがなかったので、一番簡易的に試せるJupyter notebookも以下のrepositoryに置いたのですぐ試せる。

github.com

ACL Beginner Contest 参加ログ・感想

本番は時間が合わず参加しなかったが、いつも通りメモを残しておく


内容

  • Python3でやっている。
  • 参加ログ。
  • 所感。
  • コンテスト中に何を考えたか。
  • コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
  • 問題の詳細で細かく書こうと思うものは別記事とする。
  • E以上はとりあえず現状自力では無理なのでDまで。解けるようになってきたら更新するかも

結果

ABC完。参加すればよかったと後悔。 Pythonを使っている人は、基本ACLを使いながらやるわけではないのであまり関係ないが使えないわけでもないらしい(Cython使いの方々が頑張ってくれている。)

twitter.com

仕様が変わるたびにやり方が変わりそうな気はしている。


どう考えたか + α

A - Repeat ACL

問題タイプ:文字列操作

同じ文字列を複数回繰り返すだけなので 文字列 * 回数 で繰り返せばいいだけ。

k = int(input())
s = 'ACL'
ans = s * k
print(ans)

B - Integer Preference

問題タイプ:範囲の包括条件

要するに、 a ... c ... b (dとbの大小はどちらでもいい) a ... d ... b (aとcの大小はどちらでもいい) c ... a ... d (dとbの大小はどちらでもいい) c ... b ... d (aとcの大小はどちらでもいい) となっているパターンはYesでありそれ以外はNoなので 愚直に書けば

a, b, c, d = map(int, input().split())
if a <= c <= b or \
    a <= d <= b or \
    c <= a <= d or \
    c <= b <= d:
    print('Yes')
else:
    print('No')

もしくは aかcの大きい方とbかdの小さい方の大小関係で決まっているので、そのように書く

a, b, c, d = map(int, input().split())
if max(a, c) <= min(b, d):
    print('Yes')
else:
    print('No')

C - Connect Cities

問題タイプ:Union-Find

この問題と似ていると考えた。

blacktanktop.hatenablog.com

つまり、Union-Findでグループ分けするイメージである。なので、rootの数を数えて、その間を結べば良いのでrootの数 - 1となる。(今回は最小の繋がりで良いので直接つながっている必要がないから) 例えば GroupA GroupB GroupCとなる時に

GroupA…GroupB...GroupCとつながれば十分なので(どういう組み合わせでもよい)

def find(target):
    if parent[target] < 0:
        return target
    else:
        parent[target] = find(parent[target])
        return parent[target]
def is_same(x, y):
    return find(x) == find(y)
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x
def members(n, x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]
def get_size(x):
    return -parent[find(x)]
def get_root():
    return [i for i, root in enumerate(parent) if root < 0]

n, m = map(int, input().split())
parent = [-1 for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
ans = len(get_root()) - 1
print(ans)

Union-Findわからんっていう場合は、以下の書籍をおすすめする。具体的には11章 データ構造(4):Union-Findに詳しく書かれている。

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

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

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

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)


その他のおすすめの書籍

アルゴリズムの参考書籍

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。(AtCoderもそんな感じのリスト作って欲しい) ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。(AOJも解いているので、記事にしていこうかなぁ)

最近ポチった書籍

アルゴリズムとは関係ないが、一応機械学習も生業としているので、関連書籍は目を通すようにしている。 強いていうならば、第3章の数学のおさらいの最適化・確率あたりは関連がある。その他、回帰分析・分類・ニューラルネットワーク強化学習教師なし学習とかなり幅広く、初学者が一通り学ぶには良さそうである。

blacktanktop.hatenablog.com

書評は書いてある。本家にはnotebookがなかったので、一番簡易的に試せるJupyter notebookも以下のrepositoryに置いたのですぐ試せる。

github.com

Python3で解く AtCoder Beginner Contest 152 D - Handstand 2

数値そのもので考えるというより、その数値の先頭とお尻の数値の組と逆にしたお尻と先頭の数値の組みがそれぞれ幾つ存在するのかっていうことを考える問題。こういう時はdefaultdict(というか常にdefaultdictでいいと思うけど)で行う。 dictでやる場合とdefaultdictでやる場合で何が違うのかを示してみる。

目次

概要

問題

  1. {\displaystyle n}が与えられる。
  2. {\displaystyle n}以下の正の整数の組{\displaystyle a, b}について以下の条件を満たすものはいくつある?
    1. {\displaystyle a}の一番右の桁の値が{\displaystyle b}の一番左の桁の値と一致する。
    2. {\displaystyle a}の一番左の桁の値が{\displaystyle b}の一番右の桁の値と一致する。
    3. 例えば{\displaystyle n=25}のとき、(1, 11)や(12, 21)は条件を満たしている。順列なので(11, 1)や(21, 12)は別カウントとして考える。

解くときに考えた内容

  • 一緒になる数値がどのパターンがあるかというのを考えると煩雑になりすぎる。
    • 例えば1, 11, 101・・・など。
  • {\displaystyle 1}以上{\displaystyle n}以下の正の整数の組{\displaystyle a, b}をすべてカウントする。
  • その組の中に、入れ替えた{\displaystyle n}以下の正の整数の組{\displaystyle b, a}がいくつあるかを探索する。
  • この時の{\displaystyle 1}以上{\displaystyle n}以下における、{\displaystyle a, b}の個数 {\displaystyle \times b, a}の個数の和は?
  • 実装上は数字を文字列として扱う方が一番右と一番左の値を取得するのが簡単。

keyの存在の有無によるdictとdefaultdictの違い

  • コードを見が方がわかりやすいが、dictではkeyが存在しない時に処理しようとするとエラーになるため、if文でkeyがない時の処理を書く必要がある。
  • defaultdictではその処理を書く必要がない。
    • 初期化としてvalueがどういったものなのかという型指定をする必要はある。
      例えばd = defaultdict(int)の様な形。
      リストをvalueとして用いたい場合はd = defaultdict(list)などとすると
      d.append(1)の様にすることも可能。

コード

defaultdictを用いた場合
from collections import defaultdict
n = int(input())
d = defaultdict(int)
for i in range(1, n+1):
    s = str(i)
    # 一番左の数字
    a = s[0]
    # 一番右の数字
    b = s[-1]
    d[a, b] += 1
ans = 0
d_items = list(d.items())
for (a, b), v in d_items:
    ans += v * d[b,a]
print(ans)
dictを用いた場合
n = int(input())
d = dict()
for i in range(1, n+1):
    s = str(i)
    # 一番左の数字
    a = s[0]
    # 一番右の数字
    b = s[-1]
    # keyない時の処理が必須
    if (a, b) not in d:
        d[(a, b)] = 0
    d[(a, b)] += 1
ans = 0
d_items = list(d.items())
for (a, b), v in d_items:
    if (b, a) not in d:
        d[(b, a)] = 0
    ans += v * d[(b, a)]
print(ans)

Python3で解く AtCoder Beginner Contest 152 C - Low Elements

問題を理解するのに戸惑った。が内容的にはfor文一発でいける。

目次

概要

問題

  1. 要するに数列{\displaystyle P}{\displaystyle i}番目が{\displaystyle 0}番目から{\displaystyle i}番目で一番小さい数になっているかどうかを判定する。
  2. 数列全てのindexにおいて条件が満たされているindexの数は?(ということ。。。わかりづらい)

解くときに考えた内容

  • 左から見てって、自分がこれまでの数値の最小値かどうかを判定していくだけ
  • 最初は制約より+1大きいものとしている(1つ目は必ずカウントされる)

コード

n = int(input())
P = [int(x) for x in input().split()]
minv = 2 * 10 ** 5 + 1
cnt = 0
for i in range(n):
    if minv > P[i]:
        minv = P[i]
        cnt += 1
print(cnt)