問題へのリンク 問題概要 整数 があたえられる。 進法で有理数 p/q を小数で表したときに有限小数となるような最小の 2 以上の整数 を求めよ。 制約 < < 考えたこと とりあえず p/q を約分しておく。 そして、q を素因数分解したときの、指数部を全部 1 にし…

貪欲でも、実家 DP でも、ソシャゲ DP 的な DP でも解けるみたいなのんな。これ、実装がややこしくて、苦手なんて言葉ではいい表せないほどの超絶苦手系なのん。。。 Gerrymandering 問題へのリンク 問題概要 N 個の街が一直線上に並んでいて、各街は 2 種類…

包除原理勉強会の一環。なんか最初、0〜N-1 を 2K で割った余りで類別したところで鎖を作って、そこでのサイズ i のマッチングの個数を数えたりしたのだけど、それをマージするのに NTT を使うとか血迷った^^; https://beta.atcoder.jp/contests/agc005/subm…

ラグランジュ緩和か、、、 しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白い。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最小全域木を求…

本番、最後には綺麗な解法になったけど、何度も WA を出して大変だったん。 問題へのリンク 問題概要 要素の数列 が与えられる。この数列に以下の操作を好きな回数だけ繰り返して数列 にできるかどうかを判定せよ。 【操作】 を xor に置き換えるか、 を xor…

超定番の「対応がとれている」カッコ列を題材にした問題なん。色んな出題がやり尽くされてそうな中、まだこんなのが残っていたのんな！！ ある文字列が与えられたときにそれが正しいカッコ列かどうか判定するのは、AGC 005 A - STring の方法でできるん。 今…

lower_bound() や upper_bound() を無思考で使えるとよさそう 問題へのリンク 問題概要 個の整数 が与えられる。 個のクエリ があって、以下のようなクエリに答えよ: として、各 に対して を合算した値を答える 制約 解法 個の各クエリごとに 個の を個別に…