けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

論理パズル

AtCoder ABC 056 A - HonestOrDishonest (灰色, 100 点)

bool 型をうまく考える問題 問題へのリンク 問題概要 入力 が与えられる。 = 'H' のとき:AtCodeer 君は正直者である = 'D' のとき:AtCodeer 君は嘘つきである ここで、 = 'H' のとき:「TopCoDeer 君は正直者だ」と AtCodeer 君は発言した = 'D' のとき:…

JOI 予選 2007 E - 品質検査 (AOJ 0514, 難易度 5)

この辺りから難しくなって来てる。「 で合格・不合格」という条件をどのように適切に言い換えるかが問われている。 問題へのリンク 問題概要 電源が 個、モーターが 個、ケーブルが 個ある。電源は と番号づけられていて、モーターは と番号づけられていて、…

AtCoder Library Practice Contest H - Two SAT

2-SAT は強連結成分分解の典型的な応用例! 問題へのリンク 問題概要 旗 を数直線上に設置したい。旗 は、座標 または座標 に設置可能である。 ただし、どの 2 つの旗も、その距離が 以上となるようにする必要がある。 本の旗を設置することが可能かどうかを…

JOI 二次予選 2021 E - スパイ 2 (難易度 10)

面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…

AtCoder ABC 147 C - HonestOrUnkind2 (緑色, 300 点)

とても教育的な問題でしたね!!! ここにまとめました! drken1215.hatenablog.com 以下のような問題です。bit 全探索とよばれているもので、 通りの選択肢をすべて調べ上げる手法を用います。 問題概要 人がいて、それぞれ「正直者」であるか、「不親切な…