解説
atcoder.jp 問題 消費税T%のとき課税後の整数値として現れないN番目のものを出力せよ。 制約 解説 ある自然数Aがあって、T*A の結果、100の位へ繰り上げがあるなら、(100+T)*A/100-1 は登場しない整数値である。 なぜなら、T*A で100の位への繰り上げが生じ…
atcoder.jp 問題 以下の条件を満たす長さNの数列Aを構築せよ。 数列のどの2つの要素も互いに素ではない 解説 まず、どの2つの要素も互いに素ではなく、一方で全体のgcd は1である、という点に着眼し、数列の要素を3つのグループに分けることを考える。 グル…
atcoder.jp 問題 Nが のようにK分割されている。Mが与えられるので同様にK分割し、その結果を整数列Bとしたとき、 が最小となるようなものを1つ出力せよ。 制約 解説 数列Bの要素として実数を許すなら、 とすることで、 を全て0にすることができる。 しかし…
問題 yukicoder.me 2-SATについての前提 2-SAT問題の解き方 論理和を論理包含に変換 1を元にimplication graphを作る 2のimplication graphを強連結成分分解する 3の結果、ある要素Xとその否定￢Xが強連結成分であるなら、その2-SATを満たす解は存在しない …
制約から座標圧縮をすべきであることは想像しやすいが、この問題はかなり難しいと思った。 atcoder.jp 前提 座標圧縮 pione.hatenablog.com 解説 座標圧縮を行う問題でよく見かけるパターンは以下の2つである。 いくつかの長方形が与えられて、長方形が重な…
問題 onlinejudge.u-aizu.ac.jp 前提 ダイクストラ法 クラスカル法 最近共通祖先（Lowest Common Ancestor） 解説 ダイクストラ法、クラスカル法（的な発想）、Lowest Common Ancestor、3つ基本アルゴリズムの合わせ技で解ける良問。 ざっと他の人の解説を見…
問題 atcoder.jp 前提 最長共通部分列問題（Longest Common Subsequence） 解説 最長共通部分列問題（Longest Common Subsequence）が解法の基盤になっていると思った。 LCSのDPでは、複数の列における部分列の長さの最大値を管理するが、この問題では不一致…
yukicoder.me 問題 1～nからn-1個を選んで作れる最小公倍数のうち、その最小値を求め、998244353で割った余りを求めよ。 前提 エラトステネスの篩 pione.hatenablog.com 解説 まず除外すべき1つの数は自明に、1～nの中の最大の素数である。 次にn-1個の数の…
一次合同式についての教育的な良問だったので、考えたことを書き残しておく。 問題 atcoder.jp 考えたこと この問題は言い換えると、初期値がsの状態からkを何度か足すことで、nの倍数を作れるか、という問題になる。 つまり、(kx+s)%n==0となる最小のxを求…
atcoder.jp bit全探索について、まさに典型と思える問題だったのでメモとして残す。 前回のABC146 Cは二分探索で、今回はbit全探索。まさに入門アルゴリズムの典型がCに配置されてると感じた。 #include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T</class></bits/stdc++.h>…
codeforces.com DPに関して学びになる問題だったので、メモとして残す． 漸化式 dp[i] := s[i]まででn or uが連続する区間においていたずらできる回数 この問題で漸化式を上記の様に定義すると、dpテーブルの遷移はフィボナッチ数列と同じになることに気付く…
atcoder.jp DPについて学びになる問題だったので、メモとして残す． 考えたこと DPで解く 実装 参考にさせていただいた実装 考えたこと 最初考えたのは、各拠点のモンスターは、自身が攻撃できる街の中で勇者の撃退可能数が最も少ない街を貪欲的に選んでいけ…
atcoder.jp 制約 考えたこと 実装 制約 1 ≤ | S | ≤ 100 1 ≤ K ≤ 109 考えたこと SとKの制約から、文字列を連結させてから操作回数を数えようとすると、O( | S | * K ) となり間に合いません． そのため、Sに対して、どの隣り合う2文字も相異なるような操作…
atcoder.jp 題意 制約 考えたこと 実装 感想 題意 2つの正整数A、Bが与えられるので、その公約数のうちいくつかを選ぶ。 このとき選んだ値は、それぞれが互いに素である必要がある。 選べる公約数の最大の個数はいくつか？ 制約 1 <= A, B <= 1012 考えたこ…
