問題 030 - K Factors（★5） ポイント 2以上N以下の整数の素因数の種類を全て求め、最後にK 種類以上の素因数を持つものの個数を求めます。 方法としては2からNまで全探索していき、素数を見つける度にその素数で割り切れるN以下の全ての整数の素因数の種類数を+1します。 以上を踏まえ、実装したコードがこちら...

問題 051 - Typical Shop（★5） ポイント 競プロに親しみがある方だとこの問題を見たときにナップサック問題と似ている→動的計画法で解ける！と思われるかもしれません。 ただ、残念ながらこの問題を動的計画法で解くことはできないのです・・・。理由は値段の合計Pと、各商品の値段Aiの上限が大きい（10の18乗...

問題 085 - Multiplication 085（★4） ポイント a,b,cの候補を全探索していきますが、実直に全てのパターンを試すとTLEとなってしまいます。 そこで、問題文から得られるaは√k以下、bはa以上という制約を利用して全探索の範囲を絞ることで時間内に探索を終えることができます。 以上を踏まえ、実装...

問題 070 - Plant Planning（★4） ポイント 「マンハッタン距離って何？」という方は下記記事が参考になります！マンハッタン距離（Taxicab distance）／ユークリッド距離（Euclidean distance） 各工場から発電所へのマンハッタン距離を最小にすることが本問題のゴールですが、マ...

問題 063 - Monochromatic Subgrid（★4） ポイント 全ての行と列の組み合わせを全探索すると一見TLEとなってしまいそうですが、行が8行しかないためビット全探索を使用することでTLEとならずに全探索することが可能です。 「ビット全探索って何？」という方は下記記事が分かりやすいです！Python...

問題 058 - Original Calculator（★4） ポイント ボタンAを押した場合の処理は関数で用意するとして、愚直にK回その処理を行うとTLEとなってしまいます。 そこで、ボタンAの処理を何回か行った際、1度出てきた数字に戻ってきた場合を考えます。図にするとこんな感じです。※青丸がボタンAを押した後の数...

問題 042 - Multiple of 9（★4） ポイント 前提として、ある数Xが9の倍数である時、Xを10 進法で表したときの各桁の数字の和も9の倍数となります。すなわち、与えられたKが9の倍数でない場合、条件を満たすXの数は0通りとなります。 Kが9の倍数の場合、動的計画法を使って各桁の値の合計が0~KになるX...

問題 034 - There are few types of elements（★4） ポイント ・〇〇を満たす区間 (連続する部分列) のうち、最小or最大の長さを求めよ・〇〇を満たす区間 (連続する部分列) を数え上げよ このような問題にはしゃくとり法が有効です。※しゃくとり法については下記記事が参考になります。...

問題 003 - Longest Circular Road（★4） ポイント この問題で与えられているデータは木構造をしています。※木構造のデータについて、詳細を知りたい方は下記記事が参考になると思います。ITの基礎知識｜ITパスポート・基本情報 - 木構造 「同じ道を2度通らずにある都市から同じ都市に戻ってくる経路...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 028 - Cluttered Paper（★4） ポイント 実直に解くのならば、はじめに1000x1000のマス目を用意し、紙の情報が与えられる度に重なっている全てのマスを+1していけば良いですが、残念ながらそれ...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 018 - Statue of Chokudai（★3） ポイント 一旦問題の状況を図にしてみました。 観覧車ですが、平面 x=0 上にあるのでy軸とz軸だけ考えれば良さそうです。 Ei分後の観覧車から見た高橋直大...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 026 - Independent Set on a Tree（★4） ポイント 隣り合わない頂点とは、辺で結ばれていない頂点を指します。そのような頂点を選ぶには、深さが全て偶数、または奇数の頂点から選ぶと良いです...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 008 - AtCounter（★4） ポイント この問題は動的計画法を使って解くとスムーズです。動的計画法については下記記事の解説が分かりやすいと思います。※いずれこのブログでも解説記事書きますのでお待ちを！ う...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 001 - Yokan Party（★4） ポイント K+1 個のピースのうち最も短いものの長さをXcmと置いて考えます。 この問題では最大のX（=スコア）を求めたいのですが、ここでXの候補は1cmからLcmまでの...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 084 - There are two types of characters（★3） ポイント o と x 両方が含まれる選び方を考えていくと時間がかかりそうなので、余事象の考え方を使うことにします。 すなわち（...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 079 - Two by Two（★3） ポイント ある二次元配列Aを、ある二次元配列Bに一致させる方法があるかを探せば良いので、単純にAの左上から値をBに合わせていって、最終的にAがBに一致するかを判断すればOK...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 082 - Counting Numbers（★3） ポイント 1度、各桁ごとに書かれる文字の個数を整理してみましょう。例えば、1桁の数字は1~9まであり黒板に書かれる文字の総数は下記の式で求めることができます。 ...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 076 - Cake Cut（★3） ポイント この問題は累積和を使って解くとスムーズです。本問題に限らず、連続する~個のといった言葉が出てきたら累積和を使えないか考えてみるといいでしょう。 まず、N個のピースそれ...