結構単純な、数え上げ。 ソートして考えることにきづければ簡単。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 問題概要は省略。 解くときに考えた内容 すべてのパターンは でも制約的に、線形で考えなくてはいけないので二重のfo…

階乗の約数のカウント、七五数のカウント。愚直に約数を列挙して数え上げるとだめで数え上げに組み合わせのを考えながら工夫が必要な、いい問題 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 が与えられる。 の約数の中に七五数は…

結構単純な、数え上げするだけ。 問題を把握するのに、少しだけ苦戦したがよく読んだらDにしては結構単純だった。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 問題概要は省略。 解くときに考えた内容 最初と最後を同等に考えられ…

愚直に、1~hまでどんな風になるかをリストで残そうとすると、TLEになる様な制約なので、いい感じのパターンを見つける必要がある。 どんな人数になるかがちょっとよくわからないので、とりあえず書き出す。そうするとパターンが見えてくる。 目次 目次 概要 …

単純な確率問題でラッキーと思ったら、しっかりDPとの組み合わせだった。（そりゃそうだDだもの） 目次 目次 概要 解くときに考えた内容 コード リストでメモ化 lru_cache（超便利） 参考になる書籍 概要 問題 金貨が枚、銀貨が枚、銅貨が枚袋に入ってる。 …

単純に与えられた開始タイミングと終了タイミングで使う量をうまく記録して、頭から順番にを超えないかどうかっていうこと 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 時間あたりのお湯の供給量の限界は 人いる 番目の人は以上未…

制約上、愚直にやるとTLE。 累積和を２つ持つ必要がある。イメージさえできれば、コードはすっきりできる。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 整数列が与えられる。 以下のように座標を進む。()が正なら右へ負なら左へ…

条件を検討すると、増えるか増えるかで小さい方を選びたいってことに気付ければなんとかなる。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 初期の強さは、経験値は カコモンジムに通う：強さが倍になり、経験値は増える。 AtCode…

数値そのもので考えるというより、その数値の先頭とお尻の数値の組と逆にしたお尻と先頭の数値の組みがそれぞれ幾つ存在するのかっていうことを考える問題。こういう時はdefaultdict（というか常にdefaultdictでいいと思うけど）で行う。 dictでやる場合とde…

じゃんけんにおいて、事前に相手が出す手がわかっていて、何を出して勝ったかで得点が異なる時に、何回かじゃんけんして特典の最大値を求める問題（ほぼ概要だな）。 目次 目次 概要 解くときに考えた内容 コード 書籍 アルゴリズムの参考書籍 最近ポチった…

グラフの連結 目次 目次 概要 解くときに考えた内容 BFS Union-Find コード BFS Union-Find 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人いる。 1. 個の友人関係情報が与えられる。 1. 直接友人でなくても、友人の友人は友人であるとする…

かなりシンプルな問題。砕いて残ったものが1, 2, 3...という風に並んでる状態を目指す。左から順番に砕くか判定していく。 目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 個のレンガが並んで…

startとgoalを自分で決める迷路で最長の手数のstartとgoalはなにかっていう問題。久しぶりに迷路問題解いた。普通はスタートとゴールを設定するんだけど、ゴールまで設定するとTLEになるので、スタートだけ設定して、BFSでやって最大手数の場所を結果的にゴ…

上下左右の移動だけでなく、制限があるワープができる条件で、最低限のワープ数で迷路にゴールできるかを問う問題。結論から言うと、計算量的にきつかった。自分にはこれ以上は思いつかなかったが、ともかく、普通の移動→そこをスタート地点してワープ→そこ…

当たり前だが、制約が大きいので、一つ一つ移動させてスコアの和の最大値を求めようとするとTLEになる。そこを工夫する必要があり、の和で考えて対応した。最初に選んだマスがある意味運命を左右することになるので（止まるという選択肢はあるものの）そこを…

問題を把握するには、連続したシグマが何を意味しているのか、XORの特性を理解することがポイント。それさえできれば結構単純。自分は桁ごとに考えた。制約としてギリなのでローカル化しないとTLE。もっと工夫できるのかもしれないけど。 目次 目次 概要 制…

個存在する状態をを目指すようにして、それぞれの状態における最小の手数を数えて、全状態の中で最小値をみつければいい。状態をどう考えるか、その時の最小の手数はどう考えればいいかというのがポイント。 概要 解くときに考えた内容 反省点 コード 概要 …

木グラフにおける辺彩色の問題。色分けに必要な最小な色数とその例をだす必要があるので、色分けの仕方をきちんと書き上げる必要がある。 DFSとBFSの違いを理解した状態で取り組んだので形式的だが、どちらもdequeを使ってやってみた。 目次 目次 概要 解く…

ナイトのコマがある動きをするときに、目的の場所にたどり着けるかどうかという問題。連立方程式も使うし、高速にを計算する必要もある。結構内容としては盛りだくさんで難しい。久しぶりにモジュラ逆数について考えたので軽くまとめた。 概要 解くときに考…

半公倍数って初めて聞いた。 まぁ定義に従って計算する。 ぱっと見、複数の値に対する最小公倍数を使うんだろうな。 結果的に、最小公倍数を計算しきってから大きさの判定をしていたせいで、一部REが発生していて、そこが原因と気付かず、ひたすら原因究明の…

公約数と互いに素の問題 概要 解くときに考えた内容 素因数分解 コード 概要 問題 1以上の2つの整数を与えるので、公約数からいくつか選ぶ。 ただし、選んだもののどの2組も互いに素である必要がある。 最大いくつ選ぶことができる？ 解くときに考えた内容 …

リスト内のmaxの値が必要なパターン。 これをそのままやらずに、優先度付キューを使う。 Pythonのheapqは最小値をpopするので注意。 概要 解くときに考えた内容 コード 概要 問題 個商品がある。 枚商品券がある。 円の商品に商品券を枚使うと商品の値段が（…

いい感じに約数の個数を数える必要がある。 概要 解くときに考えた内容 N基準の約数表を考える 約数基準の約数表を考える（定数倍の考え方） 定数倍であることから等差数列の和と考える コード 概要 問題 正整数が与えられる。 の約数の個数をとする。 を か…