種類以上の素因数を持つものの個数を求めます。方法としては2からNまで全探索していき、素数を見つける度にその素数で割り切れるN以下の全ての整数の素因数の種類数を+1します。競プロに親しみがある方だとこの問題を見たときにナップサック問題と似ている→動的計画法で解ける!と思われるかもしれません。残念ながらこの問題を動的計画法で解くことはできないのです・・・。a,b,cの候補を全探索していきますが、実直に全てのパターンを試すとTLEとなってしまいます。そこで、問題文から得られるaは√k以下、bはa以上という制約を利用して全探索の範囲を絞ることで時間内に探索を終えることができます。全ての行と列の組み合わせを全探索すると一見TLEとなってしまいそうですが、行が8行しかないためビット全探索を使用することでTLEとならずに全探索することが可能です。ボタンAを押した場合の処理は関数で用意するとして、愚直にK回その処理を行うとTLEとなってしまいます。そこで、ボタンAの処理を何回か行った際、1度出てきた数字に戻ってきた場合を考えます。図にするとこんな感じです。進法で表したときの各桁の数字の和も9の倍数となります。与えられたKが9の倍数でない場合、条件を満たすXの数は0通りとなります。このような問題にはしゃくとり法が有効です。※しゃくとり法については下記記事が参考になります。この問題で与えられているデータは木構造をしています。※木構造のデータについて、詳細を知りたい方は下記記事が参考になると思います。Paper(★4)」解法2022年4月14日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。Chokudai(★3)」解法2022年4月12日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。問題の状況を図にしてみました。上にあるのでy軸とz軸だけ考えれば良さそうです。Tree(★4)」解法2022年4月10日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。隣り合わない頂点とは、辺で結ばれていない頂点を指します。AtCounter(★4)」解法2022年4月8日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。この問題は動的計画法を使って解くとスムーズです。動的計画法については下記記事の解説が分かりやすいと思います。Party(★4)」解法2022年4月6日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。個のピースのうち最も短いものの長さをXcmと置いて考えます。characters(★3)」解法2022年4月4日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。両方が含まれる選び方を考えていくと時間がかかりそうなので、余事象の考え方を使うことにします。Two(★3)」解法2022年4月2日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。Numbers(★3)」解法2022年3月31日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。1度、各桁ごとに書かれる文字の個数を整理してみましょう。1桁の数字は1~9まであり黒板に書かれる文字の総数は下記の式で求めることができます。Cut(★3)」解法2022年3月29日このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。この問題は累積和を使って解くとスムーズです。本問題に限らず、連続する~個のといった言葉が出てきたら累積和を使えないか考えてみるといいでしょう。3ProfileTheLogicalBear論理パズルとアルゴリズムが大好きな機械学習エンジニアです。