📖

アルゴリズム勉強の反省日記 4/17-4/24

2021/04/17に公開

初心者

tech

4/17 第二回日本最強プログラマー学生選手権

https://atcoder.jp/contests/jsc2021

全体として

A-Cの問題を完答するのに90分ほど費やした。しかし解法自体はもっと早く気づいていた。実装力が足りていない。Dの問題も初見は難しく感じたが、高校数学レベルの数列の問題だった。

今後

実装力の強化
正解できればよいではなく、よりよい回答を研究する
計算量への意識

その他tips

set型を用いて、重複する要素を除去する問題

狭義単調増加な整数列A=(A1,A2,…,AN),B=(B1,B2,…,BM)があります。A,Bのどちらか片方にだけ出現する整数を全て求め、昇順に出力してください。

input()
A = set(map(int, input().split()))
B = set(map(int, input().split()))
print(*sorted(A ^ B))

参照

計算量が大きくなる数列

数列は手計算でわかっていたが、そのまま実装するとタイムアウトに…
計算量の意識をもたないといけないと反省。

公式回答例より引用

MOD = 1000000007
N, P = map(int, input().split())
ans = (P - 1) * pow(P - 2, N - 1, MOD) % MOD
print(ans)

powってなによ？

**は演算子、pow()は関数という違いあり、（当たり前？）通常の計算はおなじ。
ただ三番目の引数としてmodを指定することができる。
競プロで剰余を意識するような大きな計算の時は使えるかも。

参考

4/18 hackerrank/Hash Tables: Ransom Note

端的にいうと、リストよりも辞書をつかった方が高速にできる。

解説メモ

まずはmagazineの単語を辞書に登録。複数回登場している場合はキーに記憶。
その後、ransomの単語が辞書に登録されているか否か、いるとして複数回登場していないか確認。
おkならキーを-1する。

def ransom_note(magazine, rasom):
    d = dict()
    for word in magazine:
        if word in d:
            d[word] += 1
        else:
            d[word] = 1
    
    for word in ransom:
        if not word in d:
            return False
        if d[word] == 0:
            return False
        d[word] -=1
    return True

反省

何でもかんでもリストにするのよくない。意識的に辞書も使うように。

4/19 hackerrank/Sherlock and Anagrams アナグラム

アナグラムを求める問題。初見殺しかと思ったけど、そうでもないかも（？）
特に全ての組み合わせを調べる部分はまた復習する。

from collections import Counter

def sorted_str(s):
    return ''.join(sorted(list(s)))

def solve(s):
    ret = 0
    for l in range(1, len(s) + 1):
        a = [sorted_str(s[i : i + l]) for i in range(len(s) - l + 1)]
        b = Counter(a)
        for _, v in b.items():
            ret += v * (v - 1) // 2
    return ret

t = int(input())
for _ in range(t):
    print(solve(input()))

4/19 paiza 辞書の扱い

辞書の数値の扱い。キーと値の取り出し方など、もっと慣れていきたい。
（参考）リストの値のとりだしかたなど

M,N,K = map(int, input().split())
speaker_list = [input() for i in range(K)]

kouhosya = dict()
for i in range(M):
    kouhosya[i+1] = 0
kouhosya[-1] = N


for speaker in speaker_list:
    count = 0
    for k, v in kouhosya.items():
        if k != speaker and kouhosya[k] > 0:
            kouhosya[int(k)] -= 1
            count += 1
    kouhosya[int(speaker)] += count
            
    
del kouhosya[-1]

max_k_list = [kv[0] for kv in kouhosya.items() if kv[1] == max(kouhosya.values())]
for i in range(len(max_k_list)):
    print(max_k_list[i])

4/19 HackerRank Sort : Bubble Sort と　Quick Sort

-バブルソートは、以下の手順を繰り返すことでデータを整理する手法。計算量が大きくなりがち

先頭から順番にデータをチェック
左右の並びがおかしい箇所があれば入れ替える
データの最後までたどり着いたら再び先頭から順序をチェックする
データの先頭から最後まで1度も入れ替えが発生しなければ整理完了

# coding: UTF-8
import time
import random


def bubble_sort(list):
    # リストの要素数が1より大きくなければソートの必要なし
    if len(list) <= 1:
        return list

    # 入れ替えループを抜けるフラグ
    exchange_flg = True
    while exchange_flg:
        exchange_flg = False
        for i in range(len(list) - 1):
            if list[i] > list[i + 1]:
                # 左右の値を入れ替える
                list[i], list[i + 1] = list[i + 1], list[i]
                exchange_flg = True
    return list


if __name__ == "__main__":
    list = list(range(1000000))
    src = random.sample(list, len(list))

    start_time = time.time()
    sorted_list = bubble_sort(list)
    elapsed_time = time.time() - start_time

    print("elapsed_time: {0}[sec]".format(elapsed_time))

一方、クイックソートは「ある特定の値よりも大きいか小さいか」という観点で全体を一気に処理していくという手法。でもこれでは、最悪バブルソートと同じ効率になってしまう。

import random


def quick_sort(list):
    # リストの要素数が1より大きくなければソートの必要なし
    if len(list) <= 1:
        return list

    left_list = []
    right_list = []

    # クイックソートする際の基準をランダムに選択
    pivot = random.choice(list)
    pivot_count = 0

    for num in list:
        if num < pivot:
            left_list.append(num)
        elif num > pivot:
            right_list.append(num)
        else:
            pivot_count += 1

    # 左右2つにリストを分割し、quick_sort()関数を再帰的に呼び出す
    left_list = quick_sort(left_list)
    right_list = quick_sort(right_list)

    return left_list + [pivot] * pivot_count + right_list


if __name__ == "__main__":
    list = list(range(1000000))
    src = random.sample(list, len(list))

    start_time = time.time()
    sorted_list = quick_sort(list)
    elapsed_time = time.time() - start_time

    print("elapsed_time: {0}[sec]".format(elapsed_time))

マージソートなるものが存在するらしい。

（参考）pythonでソート

4/21 HackerRank Strings: Making Anagrams

二つの文字列が与えられる。その二つから文字を消去して、最短でアナグラムを作成するには何文字削除すればよいか?
それぞれの文字の集合から、一方のみに含まれるものを数え上げる。

import collections

a = raw_input()
b = raw_input()

a = collections.Counter(a)
b = collections.Counter(b)


c = a - b #aにあってbにないもの
d = b - a　#bにあってaにないもの
e = c + d
print(a,b)
print(c,d)
print(e)
print(len(list(e.elements())))

4/22 Hash Tables: Ice Cream Parlor

アイスクリームの値段のリストが渡され、そのうち合計がちょうどmoneyとなるような二つを選ぶ問題。
リストでforを回すとruntime error なるので、辞書を使う。tryとexceptをうまく使えるように。

for _ in range(int(input())):
    m = int(input())
    input() #ここは使わない
    seen = {}
    for i, a in enumerate(map(int, input().split()), 1):
        try:
            print(seen[m - a], i)　#money-iがあればそのindexを出力、
            break
        except KeyError:
            seen[a] = i

4/22 HackerRank:Max Array Sum

数字のリストが渡されて、隣接しない数字の和の最大値を出力する問題。
手順は以下

辞書の一番目はリストの一番目。二番目はリストの一番目、二番目のうち大きい方。
2.辞書のi番目(i>3)は,{d[i-1], d[i-2], dp[i-2]+num, num}
(num = list(i))
を比較し、最大のものを代入する。

arr = [2,1,5,8,4] #入力

dp = {} # key : max index of subarray, value = sum
dp[0], dp[1] = arr[0], max(arr[0], arr[1])
for i, num in enumerate(arr[2:], start=2):
    dp[i] = max(dp[i-1], dp[i-2]+num, dp[i-2], num)
    # print(dp[i],dp[i-1], dp[i-2]+num, dp[i-2], num)
    # print(dp)
    # print('------')
print(dp[len(arr)-1])