Codeforces Round 776 (Div. 3) A – Deletions of Two Adjacent Letters / B – DIV + MOD を解いた記録
A – Deletions of Two Adjacent Letters
問題の概要
英小文字からなる奇数長の文字列 \(s\) が与えられる．
隣接する2文字を削除するという操作を文字列の長さが1になるまで繰り返したとき，最後に文字 \(c\) を残せるか？
制約
- \(s\) は英小文字からなる文字列
- \(s\) の長さは49以下
- \(s\) の長さは奇数
解法
文字列 \(s\) の中に文字 \(c\) があるとき， \(c\) の前と後ろにそれぞれ偶数個の文字があれば良いです．
実装例
B – DIV + MOD
問題の概要
\(t\) 個のテストケースについて，以下の問に答えよ．
正の整数 \(a\) が与えられたとき， 関数 \(f(x)\) を
\[f(x) = \lfloor \frac{x}{a} \rfloor + (x \bmod a)\]
とする． \(x\) を \(l\) 以上 \(r\) 以下の任意の正の整数とするとき， \(f(x)\) の最大値を求めよ．
制約
- \(1 \leq t \leq 10^{4}\)
- \(1 \leq a \leq 10^{9}\)
- \(1 \leq l \leq r \leq 10^{9}\)
- 入力はすべて整数
解法
\(\lfloor \frac{x}{a} \rfloor\) は明らかに \(x = r\) のとき最大となります．
\(x \bmod a\) は， \(x\) がある整数 \(k\) を用いて \(x = ka-1\) と表せるときに最大となります．
そこで， ある整数 \(k\) を用いて \(m = ka-1\) と表わせ，かつ \(m \leq r\) を満たすような整数 \(m\) を頑張って探し出し，
\(f(m), f(r)\) のうち大きい方を最大値として採用すると通ります．