xxxasdfghjk999のブログ

iroiro

ABC 097 C - K-th Substring

問題

Submission #3184163 - AtCoder Beginner Contest 097

解法

連続している部分文字列の中で辞書順 $K$ 番目のものを求める問題です.
制約 $1 \leq K \leq 5$ と, 『連続している部分文字列』というのがポイントで, 連続している $i$ 文字( $i \in [1,2,3,4,5]$ )をすべて列挙し,ソートして重複を取り除いた $K$ 番目の要素を見ると答えです.
今回はvectorに突っ込んでsortし, v.erase(unique(v.begin(),v.end()),v.end())で重複を取り除く実装をしましたが, setにinsertしてsets.begin()+K-1番目の要素を取得するでもいい気がします.

提出

Submission #3184163 - AtCoder Beginner Contest 097

感想

実質全列挙のような形となりました. $K$ が大きかったらどう解くんでしょう...

ABC 098 D - Xor Sum 2

最近しゃくとり方を実装していなかったので解き直しました.

問題

解法

問題を見るに, いかにもなしゃくとり法です.
この問題を解くうえで, xor演算の重要な性質を用います.
xor演算において以下の性質が成り立ちます.

$A \space xor \space A = 0$
$A \space xor \space B = B \space xor \space A$
$(A \space xor \space B) \space xor \space C = A \space xor \space (B \space xor \space C)$

1の性質は, この演算においては自身が逆元となることを示しています. (自明に0が単位元となっています.)
2の性質は, 可換な演算であることを示しています.
3の性質は, 結合法則が成り立つことを示しています.
これを利用すると, しゃくとり法を実装することができます.
具体的には, 以下のアルゴリズムを適用することができます.
入力の配列を $A$ , サイズを $N$ とします.

初期化 : $l:=0 , r:=0 , res := 0, now = 0$
$r > N$ ならば $res$ を出力して終了する.
$(A[r] + now) == (A[r] \space xor \space now)$ ならば4へ, そうでなければ5へ
$now := now \space xor \space A[r]$ , $r := r + 1$ , $res := res + r - l$ , 2へ
$now := now \space xor \space A[l]$ , $l := l + 1$ , 2へ

しゃくとりの右端を右に進めるときに答えを加算するようにしています.
計算量は $O(n)$ で済みます.

提出

Submission #3184217 - AtCoder Beginner Contest 098

感想

しゃくとり法は本番でバグらせやすいので演習を積んでいきたいです.

ABC 109 反省

久々にコンテスト中に全完できました. しかし, B問題でWAを連発してしまったため, 大きくペナルティを食らってしまったのは反省事項です.

A問題

問題

解法

$C$ を1~3まで試します.

提出

Submission #3151567 - AtCoder Beginner Contest 109

感想

素直に実装しましたが, $A* B$ が奇数だったら"Yes", そうでなければ"No"です.

B問題

問題

解法

次の文字の先頭と今みている文字の尻が一致しているかをみるついでに, mapを用いて初出の文字かチェックをしていたのですが, 最後の文字が初出であるかどうかということを確認しておらず, それに気づかずに論理式に（）をつけたり的はずれな修正をして3WA. それを修正したつもりで出すも, 分岐先でreturnしておらず1WA. 計4WAをかましました.

提出

Submission #3153980 - AtCoder Beginner Contest 109

感想

yukicoder解いてるときにWAが出るとすぐテストケースをのぞいてしまう癖があるので, こういう不測のWAに弱いとこがありました. 反省します.

C問題

問題

解法

すべての $x_i$ に対して $X$ の差分を取り, これら $|X-x_i|$ すべての最大公約数が答えとなります.
各 $x_i , x_{i+1}$ の間の距離が $D$ の倍数であり, さらに $X$ から距離 $D$ でステップしてどれかの $x_i$ に到達することができれば, $D$ で数列間を移動することができます. その中での最大の $D$ は, 各 $i$ に対して $|X-x_i|$ すべての最大公約数となります.

提出

Submission #3155097 - AtCoder Beginner Contest 109

感想

解法はなんとなく思いついたのですが, 説明がなんとなく難しいです.

D問題

問題

D - Make Them Even

解法

発想が必要になる問題です.
まず, $H,W$ の制約から, $O(HW)$ の解法が求められます.
これがちょっとしたヒントで, 何度もバックトラックして計算するようなことはなさそうであることがわかります.
操作について考察します.
できるだけ偶数マスを増やしたいときは, 奇数マスのコインをどこかに動かせばよいのですが, ここで動かす方向を下方向に固定してみます.
まず1行目を左から右に見て奇数マスのコインを下に動かし,
次に2行目を...として,最後から2番目の行まで繰り返します.
すると, 最後の1行以外のマスをすべて偶数マスにすることができます.
最後の1行については, 奇数マスのコインを順次右側に動かしていくと, 一番右下のマス以外すべて偶数のマスにすることができます.
コインの総数が奇数だった場合, どうしても奇数のマスは1つできます.
コインの総数が偶数だった場合, すべて偶数のマスにできます. このとき, 右下のマスが奇数で他のマスが偶数ということはありえないので, これが最適解であることがわかります.
あとはpairとvectorなどで移動元と移動先を管理し, 丁寧に実装しましょう.
0-indexedで出力してしまい1-WA.

提出

Submission #3157253 - AtCoder Beginner Contest 109

感想

0-indexedで出力してしまったのはちょっとした悔いですが, 解けてよかったです.

総括

最近難しいABCが続いてましたが, 今回は易しかったように思います. ただ, こういうときにWA量産して順位落としちゃうのはよくないですね.

yukicoder No.420 mod2漸化式

最近はyukicoderの低難易度埋めてます.
その中でもおもしろいと思ったものを書き留めます.

問題

No.420 mod2漸化式 - yukicoder

解法

まず漸化式
$f(0) = 1$
$f(n) = f(\frac{n}{2}) + (n \space mod \space 2)$
がそもそも何を表しているか考えます.
ためしにいろいろ入れてみると,
$f(1) = 1$
$f(2) = 1$
$f(3) = 2$
$f(4) = 1$
$f(5) = 2$
$f(6) = 2$
$f(7) = 3$
$f(8) = 1$ ...
となります. $2$ のべきが $1$ となっているところや, 数字の増え方をみると, この漸化式は（というより関数としてみると）ある $n$ を $2$ 進数表現したときの立つ1の数, または各桁の和であると推測することができます. その観点を持って漸化式を見ると, たしかにそれらしいことがわかります.
問題に戻ります. 問題では, ある $x$ が与えられ,

$f(n) = x$ となるような $n$ の数
それを満たす $n$ の和

の2つを求める必要があります. 上の考察より, 前者は31ビット分の中に1を $x$ 個立てる場合の数を求めればよいです. これは, $_{31}C_x$ で求まります.
後者は少し考察が必要です. 上で求めた $_{31}C_x$ の中で, $k$ 番目のビットに $1$ が立つ場合の数はいくらか？を考えます. この数は, $k$ ビット目に1を立てておいて他の場所に $x-1$ 個1を立てたときの場合の数に対応するので, $_{30}C_{x-1}$ に対応します.
よって, $k$ ビット目に1が立つものは $_{30}C_{x-1}$ 個あり, この $k$ を1から30について計算するので,
$Ans = \sum_{k=0}^{30} 2^k_{30}C_{x-1}$
となります. コンビネーションの部分は外に出せ,
$Ans = _{30}C_{x-1} \sum_{k=0}^{30} 2^k$
となり, さらに簡略化すると,
$Ans = _{30}C_{x-1}(2^{31} - 1)$
となり, これが和の方の答えです.
しかし, $x$ が0のときだけ場合分けが必要なので注意です.

提出

#282657 No.420 mod2漸化式 - yukicoder

感想

漸化式の意味を理解すると大きく計算量を減らすことができる面白い問題だと思いました.

ARC 102 C - Triangular Relationship

問題

C - Triangular Relationship

解法

コンテスト中は, ひたすら $a$ を固定して $b,c$ の数を数える方法を探していた.
まず, 問題文を式に表してみると,
$a + b = n_1K$
$b + c = n_2K$
$c + a = n_3K$
$a$ を固定してみたときとりあえず $b,c$ は
$b = n_1K-a$
$c = n_3K-a$
表すことができる. また,
$b + c = n_1K-a + n_3K-a$ より
$2a = n_1K-n_2K + n_3K$ が成り立ちます.
また, 条件から各 $a,b,c$ について
$1 \leq a,b,c \leq N$ より
$b$ について
$1 \leq n_1K - a \leq N$
が成り立ち, $c$ についても対称性から同じものが成り立ちます. これを変形すると, $n_1$ について
$\frac{a+1}{K} \leq n_1 \leq \frac{N+a}{K}$
となり, $n_3$ についても
$\frac{a+1}{K} \leq n_3 \leq \frac{N+a}{K}$
が成り立つ必要があります.
いま, $a$ を固定しているため, 不等式から $n_1$ と $n_3$ が取りうる値の数を求め, 掛けあわせれば場合の数を求めることができます(同じ式の形なので, 片方を求めて二乗すればよい).
しかし, 式
$b = n_1K-a$
$c = n_3K-a$
は $a$ を固定することにより得ているので正しいが,
$2a = n_1K-n_2K + n_3K = (n_1-n_2+n_3)K$
は, $a$ と $K$ の値によっては成り立たない場合があります.
$2a$ が $K$ の倍数でないときはこの式を満たすことはできません. 逆に, $2a$ が $K$ の倍数のときは, 両辺を $K$ で割り, $n_2$ を導出することができるため, $2a$ が $K$ で割り切れることは, この式を満たす必要十分条件となっています.
よってその場合のみ数を数えないことにします.
これを $1 \leq a \leq N$ について行い, すべての場合の数を足しこむと答えが得られます.

提出

Submission #3118170 - AtCoder Regular Contest 102

感想

早ときしたかったが, 頭が足りなかった. 想定解法ではさらに踏み込んだ数学をして数えるものを単純化している. Twitterでも想定解法の人が多く, 自分がみている限り, この解き方をしている人は少なかった. 想定解法では $O(1)$ だが, 自分の解法では $O(N)$ かかる. 制約がもう少し厳しければ想定解法に近づけたかもしれないが, 負け惜しみである.

SoundHound Programming Contest 2018 Masters Tournament 本線 B - Neutralize

問題

解法

貪欲ができないか考えます.
ある薬品 $K$ を0にしたいときはK個を巻き込む必要があります. また, $K$ 個以上の区間を0にしたいときはこれを繰り返すことで実現することができます.
しかし, サンプルケースを見てみるとこれは厳しそうであることがわかります.
最適解が貪欲に求まりそうにないので, 最適解を仮定してDPをすることになります.
DPをするにあたって必要な保持状態は、まず

見ている薬の番号(1からN)

が必要です. 他に必要なものは,

見ているインデックスを右端としてK個選び, ０にしたかどうか(True or False)

です.
この２つを規定すると,
$dp[i][j] := (i番目までの薬品においての問題の最大値(j==0のとき右端から0にしている.))$

基底

$dp[0][0] = 0$
$dp[0][1] = 0$

帰納

$dp[i+1][0] =\max_{0 \leq j \leq i-K+1 , \space 0 \leq p \leq 1} dp[j][p]$
$dp[i+1][1] = \max ( dp[i][0] + b[i] , dp[i][1] + b[i] )$

帰納の上の式は, 右側から $K$ 個0にする必要があるために添字がK個小さいものまででの最大値に遷移します. ものものしい式となっており, いちいちこの最大値を探査していると時間が足りません. よって, dpを更新するたびに配列maxを用意しておき, 最大値を更新しておくと, 高速に計算することができます.
また, $i-K+1$ が0より小さいとき, $dp[i+1][0]$ は, 定義できません. このときは, maxに影響しないようにとても小さな数を入れておきます.
計算量は $O(N)$ です.

提出

Submission #3067414 - SoundHound Programming Contest 2018 Masters Tournament 本戦

感想

なかなかに大きい制約なので DPはなかなか発想できません.

No.672 最長AB列

問題

No.672 最長AB列 - yukicoder

解法

まず愚直解を考えます.
左端を決めて左から文字列を見ていき, A, B,の数を数えながら右に行き, AとBの数が同一になったら最大値を更新します.
この解法は $O(N^2)$ でTLEです. この解法を詰めていきましょう.
まず,ABの数が同一ということはAを1, Bを-1とすると和が0となるということです. これの累積和をとっておき, 区間が与えられたら $O(1)$ でその区間のABの数が同一かどうかを答えられるようにしておきます.
ある２つの区間の端を選ぶと, 対応する累積和があります. その累積和の差が0であると, その区間のABの数は同一ということになります.
上の考察から, ある区間の左側を決めたときに, それに対応する累積和と同一のものが右側に存在するか？を考えればいいことがわかります.
このときに選ぶ右端は, できる限り右側のものを選ぶと, 区間が大きくなります.
よって, 累積和をとるときにある累積和の数値をとったもので最大の添字を持つものを一緒に保存しておけばいいことがわかります.
mapで上を実装すると, 計算量は $O(N \log N)$ で抑えられます.

提出

#279467 No.672 最長AB列 - yukicoder

感想

はじめは累積和をとって二分探索するものかと思いましたが, 単調性の反例が見つかり断念.
こういった問題は愚直解から詰めていかないと考察が難しいですね...
類題としてAGCのZero Sum Rangeなんかが挙げられます.
区間の左側を決めた時に最適な右側を高速で導出するのは結構典型ですね.