LoginSignup
2
1

More than 3 years have passed since last update.

@tagtagtag(test accounts)

[やってみた]　AtCoder 版！蟻本 (初級編) [2-1 すべての基本 "全探索"]

Last updated at Posted at 2019-12-05

はじめに

筆者について

筆者はAtCoderを取り組み始めたアラフォー・ザコーダである（本職は非software職だがザコーダと名乗ってみたかった。unコーダと呼んでいただいても良い）。

軽い気持ちで初めて見たが、とにかく難しい。何度となく心が折れた。

諸兄（姉）からみると、突っ込みどころ満載な回答かもしれないが、これが筆者の実力である。

遠慮なしに指摘していただきたい。

問題について

AtCoder 版！蟻本 (初級編)に蟻本記載例題の類似問題が記載されている。

AtCoderを利用してジャッジできるアルゴリズムの良問が選別されているので、初学者にうってつけである。

上記記事著者である、けんちょん (Otsuki)@drken氏に感謝。

筆者はAtCoder 版！蟻本 (初級編)を頼りにスキルアップを図っている途中である。

目的

  • 筆者の競技プログラミング成績向上を図る。
  • AtCoder 版！蟻本 (初級編)に記載の問題を解説しながら記述することで、アルゴリズムの基礎を身に着ける。
  • コードと解説を掲載し、諸兄（姉）からの指摘を受けることで見落としていた課題を補完する。

今後

  • 2-2 猪突猛進！ "貪欲法"に挑戦する。

解答

問題のタイトルは、けんちょん (Otsuki)@drken氏の記事を借用致します。

例題 2-1-1　部分和問題

  • AtCoder

  • 方針

    • 数字の間に＋を入れよう。
    • 入れらる位置が文字数-1個あり、それぞれの場所で入れるか入れないかの二択だから、$2^{N-1}$通りの数式が出来上がる。
    • 入れる入れない・・・を考えると二分木の末端を拾って行けばよい。
    • 再帰関数を使えば入れる（+）、入れない（0）として簡単に組み合わせを表現できる。
    • 数式の計算はeval()を使えば、文字列から直で計算できるので簡単。
    • えっ！bit全探索？？？？？？
      • if ((i >> j) & 1):あ～これね、うっかりJavaでも参照しちゃったかな。てへぺろ・・・
      • ええええ、pythonでもこんな書き方あるの？！？！
      • (i >> j)←の意味は、整数iを2bitに変換して（0b0100111みたいな）、下j桁を切り捨てる。
      • ((i >> j) & 1) ←の意味は、2bitで&の左側と右側を比較し（右の桁数に合わせるのでこの場合は左の下一桁と右の一桁1）、お互いに1なら、1を返す（ビット演算子＆[理論積]）。
      • 再帰関数使わなくても楽に求まるのね。。。
    • Python ビット演算 超入門を参考にさせていただきました

  • 実装

    • 再帰関数版
      • 再帰関数で数字の間に+をいれるか（+）、入れないか（0）の組み合わせをリストアップする。ただしこの方法は、全ての文字を使っていない場合も含まれてしまう。
      • 今回の問題では全ての数字を使った式なので、組み合わせの要素数は数字の文字数-1で、組み合わせの数は$2^{数字の文字数-1}$個である。
      • よって、組み合わせの要素数でフィルタリングする。
      • あとはfor文でも回して間に＋を入れて文字列を作る。
      • 文字列はeval()評価する。ベンリー
      • 合計とって出力
S = input()

res_list = []
def my_recursion(res):
    if len(res) >= len(S):
        return ''

    my_recursion(res + '0')
    my_recursion(res + '+')
    if len(res) == len(S)-1:
        res_list.append(res)

    return res_list
# print(my_recursion(''))
# print(len(my_recursion('')))
res_list = my_recursion('')

temp_S_list = []

for item in res_list:
    temp_S = ''
    for i, j in enumerate(item):
        temp_S += S[i]+j
    temp_S += S[-1]
    S_done_eval = eval(temp_S.replace('0', ''))
    temp_S_list.append(S_done_eval)

print(sum(temp_S_list))
  • bit演算子版
    • 与えられた数字の桁数をnとすると
    • $2^{n-1}$通り組み合わせがある。これをbit表現するとどの隙間に+が入るを表すことができる
    • 例0b01010111と表現できると1の位置に+が入る
    • 2^{n-1}$通り組み合わせの全探索for i in range(2**(n-1))を行う
    • bit演算でどの桁に₊を入れるか条件分けを行う。if ((i >> j) & 1)
    • jで全桁なめている
    • めっちゃさっぱりなコード！
S = input()

res_list = []

for i in range(2**(len(S)-1)):
    temp_s = ''
    for j in range(len(S)):
        temp_s += S[j]
        if ((i >> j) & 1):
            temp_s += '+'
    # print(temp_s)
    res_list.append(temp_s)

temp_S_list = [eval(item) for item in res_list]

print(sum(temp_S_list))

ABC 079 C - Train Ticket

  • 方針

    • 数字の間に＋か-を入れよう。
    • 上記ABC045Cと同じくbit全探索する

  • 実装

    • 再帰関数版
    • 再帰関数で数字の間に+をいれるか、-を入れるかの組み合わせをリストUP
    • eval()で計算した結果と7を比較して見つかったら回答する
ABCD = input()

N = len(ABCD)


for i in range(2**(N-1)):
    temp_res = ''
    for j in range(N-1):
        temp_res += ABCD[j]
        if ((i >> j) & 1):
            temp_res += '+'
        else:
            temp_res += '-'
    temp_res += ABCD[-1]

    if eval(temp_res) == 7:
        res = temp_res + '=7'
        break

print(res)

ABC104 C - All Green

  • 方針

    • コンプボーナス以上はその問題を解くことはできないので、コンプする問題をどれにするか選ぶ組み合わせを考える。
    • 上記ののコンプ＋コンプしてない最も高い点数の問題、もしくはどれもコンプしないときの最高得点問題を最悪コンプ-1まで解く事を考える（それ以上解いたらコンプしちゃうので条件が別）。
    • 上記二つのうち手数が最短で目標を超えられたものを答えにする。
    • 最短手数探索するために以下を行う
    • コンプボーナスのみの組み合わせで、ターゲットを超えたものについてはその中の手数最小を検索することで求まる。
    • コンプボーナスの組み合わせだけでは、ターゲットを超えない組み合わせでは、コンプしてない問題の内最大得点のものをターゲット超えるまで解く（最大コンプ-1まで）。

  • 実装

    • コンプする組み合わせはbit全探索で求める
    • ポイントと手数もリストで管理すれば検索が分かりやすくなる
    • ネストしたリストのsortやminやmaxは、引数でkey=lambda x:x[1]を指定する
    • 逆からfor loop回すにはreversed()関数を使う
D, G = [int(item) for item in input().split()]

comp_bounas_list = [[int(item) for item in input().split()] for _ in range(D)]

comp_all = []

for i in range(2**D):
    temp = []
    for j in range(D):
        if ((i >> j) & 1) == 1:
            temp.append(1)
        else:
            temp.append(0)
    comp_all.append(temp)

# print(comp_bounas_list)
# print(comp_all)

full_num_list = [item[0] for item in comp_bounas_list]

each_comp_point = []
for i, item in enumerate(comp_bounas_list):
    each_comp_point.append((i+1)*100*item[0]+item[1])

# print(full_num_list)
# print(each_comp_point)


temp_point_list = []

for each_pattern in comp_all:
    temp_num = 0
    temp_point = 0
    for j, item in enumerate(each_pattern):
            if item:
                temp_num += full_num_list[j]
                temp_point += each_comp_point[j]

    temp_point_list.append([temp_num, temp_point, each_pattern]) 

# print(temp_point_list)
# overの物を解候補にリスト化する
over_list = [item for item in temp_point_list if item[1] >= G]

# print(over_list)
# 全bitが立っている最大値はターゲットを超えているため必ず値を持つ
over_combo = min(over_list, key = lambda x:x[0])
# print(over_combo)

# underのものを解候補にリスト化する
under_combo = [item for item in temp_point_list if item[1] < G]

# print(over_combo)
# print(under_combo)


temp_res_list = []
is_search = True

for temp_combo in under_combo:
    temp_bit_list = temp_combo[2]
    temp_res_point = temp_combo[1]
    temp_res_num = temp_combo[0]
    # print(temp_combo)

    # print(temp_bit_list)
    for j, item in reversed(list(enumerate(temp_bit_list))):
        for _ in range(1, comp_bounas_list[j][0]):
            # print(temp_res_point)
            if item==0:
                temp_res_point += (j+1)*100
                temp_res_num += 1

            if temp_res_point >= G:
                temp_res_list.append([temp_res_num, temp_res_point])
                break

# print(temp_res_list)
# きっかりコンプすれば必ずターゲットを超える場合、値を持たない場合がある。
# ダミーでres_candiに全bitの立った値を入れておく
if temp_res_list != []:
    res_candi = min(temp_res_list, key=lambda x:x[0])
else:
    res_candi = temp_point_list[-1]

if over_combo[0] <= res_candi[0]:
    print(over_combo[0])
else:
    print(res_candi[0])

ARC029 A - 高橋君とお肉

  • 方針

    • N個の肉をコンロ0とコンロ1に振り分けた全ての場合を考える。
    • 0グリルの焼き時間と1グリルの焼き時間をそれぞれ計算して、長いほうの時間が最小になったときの時間を答える。

  • 実装

    • bitで01に振り分けて計算しただけ。
 N = int(input())

meat_list = [int(input()) for _ in range(N)]
print(meat_list)


pattern_list = []

for i in range(2**N):
    first_grill = []
    second_grill = []
    for j in range(N):
        if ((i >> j) & 1 == 1):
            first_grill.append(meat_list[j])
        else:
            second_grill.append(meat_list[j])

    if first_grill != []:
        sum_first_grill = sum(first_grill)
    else:
        sum_first_grill = 0

    if second_grill != []:
        sum_second_grill = sum(second_grill)
    else:
        sum_second_grill = 0

    pattern_list.append([sum_first_grill, sum_second_grill])

res = min([max(item) for item in pattern_list])

print(res)

ABC002D - 派閥

  • 方針

    • くっそむずい。一週間考えて色々解答例みたけどグラフ理論？？隣接行列？？爆発した。
    • 考慮すべき事が多いのでとにかく分解して、愚直に全探索する分かりやすい方法はないか考えてみた。
    • まず派閥の人の組み合わせをbit全探索で書き出す
    • 11100は１と２と３の人が派閥を組みます的な。
    • 派閥の組みあわせを問題で与えられた人間関係の表現に書き換えた
    • 11100は[1,2] [2,3] [1,3] みたいに表す
    • 全部の組み合わせ書くのは結構大変
    • 上記の派閥組み合わせ表現が、与えられた人間関係の中に全てあればその派閥組み合わせは存在するとしてリストに入れる（本当の派閥の一部を言っているだけかもしれない）。
    • 全ての派閥組み合わせについて上記処理を行ったのち、その派閥の人数の最大値を答えれば解となる。

  • 実装

    • 派閥の人数はbitが立っていいる数なのでbit文字列の1を数える。
    • 2**Nをbit文字列にするには、format(2**N, 'b')。
    • bin()すると二進数の整数になるだけ
N, M = [int(item) for item in input().split()]
relation_list = [[int(item) for item in input().split()] for _ in range(M)]

# print(N,M)
# print(relation_list)

combo_list = []

for i in range(2**N):
    # print(format(i, 'b').zfill(N))

    temp_combo_list = []
    # 各人について関係がある人をリスト化していく
    # まだできていない
    for k in range(N):
        temp_combo = []
        for j in range(k,N):
            if ((i >> j) & 1) == 1 and ((i >> k) & 1) == 1:
                temp_combo.append([k+1, j+1])
        if temp_combo != []:
            # print(temp_combo[1:])
            temp_combo_list += temp_combo[1:]
    combo_list.append([temp_combo_list, format(i, 'b').count('1')])
# print('ans check -------------------------------')
# print(combo_list)

res_list = []

for candi_item_combo, candi_item_num in combo_list:
    is_found = True
    for item in candi_item_combo:
        if item in relation_list:
            pass
        else:
            is_found = False
    if is_found:
        # print(candi_item_combo)
        res_list.append(candi_item_num)

if res_list == []:
    print(1)
else:
    print(max(res_list))
2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1