おじい研究所

主にプログラミングの話題です

「2人組作って!」【解説】

本稿はCodeIQで2014年9月4日~2014年9月16日に出題された プログラミング言語★総選挙 予備選挙「2人組作って!」 という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

「2人組作って!」【解説】

◆解説

欠席者が最大1という制約でペアを作る問題でした。欠席者が0か1であれば、次のようなルールで判別することができます。

f:id:Ozy:20180507150100p:plain

生徒の位置によって、ABのグループに分けると、Aのグループの人数とBのグループの人数が等しくなった場合にペアを作ることができます。

f:id:Ozy:20180507150139p:plain f:id:Ozy:20180507150158p:plain

の場合はAもBも4ずつになり、うまくペアを作ることができますが、

f:id:Ozy:20180507150211p:plain

の場合はAが5でBが3となり、数が等しくなくなりますので、ペアを作ることができません。 この性質を利用すれば、単純に出席者をグループ毎に数えるだけで済みます。

# python3
import sys

# index[x, y]について、x+yが偶数ならa、奇数ならbを増やす
a = b = 0

for i, s in enumerate(sys.stdin):
    for j, c in enumerate(list(s)): # 1文字ずつ処理
        if c == 'O': # 出席者
            if i+j & 1 == 0: # indexの偶奇を調べる
                a += 1
            else:
                b += 1

print("yes" if a == b else "no")

こっちは古い版