くろたんく雑記帳

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

MENU

Python3で解く AtCoder Beginner Contest 147 C - HonestOrUnkind2

問題文をみて瞬間に、ムムッとなる。データの読み込みに慣れていればさほどでもないが、いきなり嫌な感じがした。 結局、全探索っていう感じだが結構その探索も結構面倒。なるだけ詳細を書きながらまとめる。

目次

概要

問題

  1. {\displaystyle n}の人がいる。
  2. 正直者と不親切な人がいる。
  3. 正直者は本当のことしか言わない。
  4. 不親切な人は、本当のことかそうじゃないか不明。
  5. 全員の証言を与えられる。
  6. 矛盾が生じない正直者が最大になるような人数は?

解くときに考えた内容

  • 全部つじつまが合うかどうかを確認しないといけなそうだ。
  • まずは、この入力を適切に持つ。
    • {\displaystyle i}番目の人が{\displaystyle a}個の証言をする。
    • {\displaystyle x, y}のうち{\displaystyle x}はindexに合わすので{\displaystyle x-1}とする。({\displaystyle x = 1}の人はindex的には0番目の人だから)
  • 次はbitだけど、itertools.product()で全パターンの正直者仮定リストを持つ。
  • 正直者仮定リストはインデックス{\displaystyle i}番目が{\displaystyle 1}なら{\displaystyle i}番目の人は正直者であるという仮定であるとする。
  • 正直者と仮定した人の情報の全てに矛盾が生じなければ正直者仮定リストの合計が正直者の人数。
    • 何番目の人が正直者と仮定したかのリストを用意
      • {\displaystyle n = 7}のとき
      • 正直者仮定リストが[1, 0, 1, 0, 0, 0, 6]なら
      • [0, 2, 6]のような感じ
      • 上記の正直者の証言{\displaystyle x, y}全てが正直者仮定リストと矛盾がなけれ1の数を数えるということ。
  • 全パターン試して、最大の正直者の人数を出す。
  • ごちゃついてるなぁ(・・。)

コード

from itertools import product 

n = int(input())
# 全員分の証言を入れる
XY = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        # indexを合わせるためにx-1
        # 一人当たり複数かつバラバラの数証言があるため            
        XY[i].append((x-1,y))
ans = 0
# 01で全員分の不親切・正直のパターン作る
bits = list(product([0,1],repeat=n))
# 全員分の不親切・正直のパターンを一つずつ矛盾がないか確認
for honest_list in bits:
    # 正直者とした人のindexを入れる
    honest_idx = []
    flag = True
    # 仮定の話
    for who, h in enumerate(honest_list):
        if h == 1:
            honest_idx.append(who)
    # 実際と突き合わせる
    for idx in honest_idx:
        for x, y in XY[idx]:
            if honest_list[x] != y:
                flag = False
                break
    # 矛盾が生じなかったら
    # 正直者と仮定した人の人数を
    if flag:
        ans = max(ans, len(honest_idx))
print(ans)

書籍

アルゴリズムの参考書籍

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

最近ポチった書籍

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。(というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので)
投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

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

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

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

drken1215.hatenablog.com