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にすることができる。 しかし…

atcoder.jp 問題 N個の要素からなる集合A の2つの異なる部分集合で和の mod 200 の値が等しいものが存在するかを判定し、存在する場合はその2つの集合を出力せよ。 制約 公式解説 公式解説は、鳩ノ巣原理により の場合は必ず解が存在することから、 の範囲に…

問題 atcoder.jp 公式解説 atcoder.jp 解説にある通り、青白赤を0,1,2に対応させることで各ブロックは二項係数を使って最下段のブロックのから（二項係数の計算量は無視して）O(N)で求めることができるという問題。 この問題には更に 二項係数の計算において…

制約から座標圧縮をすべきであることは想像しやすいが、この問題はかなり難しいと思った。 atcoder.jp 前提 座標圧縮 pione.hatenablog.com 解説 座標圧縮を行う問題でよく見かけるパターンは以下の2つである。 いくつかの長方形が与えられて、長方形が重な…

問題 atcoder.jp 前提 最長共通部分列問題（Longest Common Subsequence） 解説 最長共通部分列問題（Longest Common Subsequence）が解法の基盤になっていると思った。 LCSのDPでは、複数の列における部分列の長さの最大値を管理するが、この問題では不一致…

一次合同式についての教育的な良問だったので、考えたことを書き残しておく。 問題 atcoder.jp 考えたこと この問題は言い換えると、初期値がsの状態からkを何度か足すことで、nの倍数を作れるか、という問題になる。 つまり、(kx+s)%n==0となる最小のxを求…

atcoder.jp 解説 想定解は包除原理だが、Nが小さいので動的計画法でも間に合う。 dp[i][j][k] := i桁目まで確定していて、0を使ったかがj、9を使ったかがkである状態のときの通り数 dpテーブルをこのように定義すると、テーブル更新にかかる計算量は、O(N * …

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>…

atcoder.jp 期待値DPの問題 難しかったので、要復習としてメモ． 実装は以下の記事を参考にほぼ写経させていただきました． www.hamayanhamayan.com qiita.com 実装 #include <bits/stdc++.h> using namespace std; #define rep(i, m, n) for (int i = (int)(m); i < (int)(</bits/stdc++.h>…

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 考えたこ…