0.はじめに
初出社した途端5連休となりペースがつかめない今日この頃。
ABは順調にいくもCで躓き。
それでも持ち直しましたが、結局Dは解けず3完。
CでのTLEによる-5分が響いたのか
レートは-20と大幅ダウンし、775となりました。
1. A - Dice
サイコロの問題。
割合でもなく、単純な合計の問題なので、3つのサイコロで
発生する可能性のある範囲（3～18）にXが収まるかを判断し
Yes or Noを出力して終了としました。
https://atcoder.jp/contests/abc456/submissions/75410016
2.B - 456
こちらもサイコロの問題。
スマートに解きたかったのですが、力技で解きました。
それぞれのサイコロ(以下a,b,cとする)の値の全組み合わせに対し、
a=4＆b=5＆c=6、またはa=4＆b=6＆c=5、または・・・
と、456になる全組み合わせを列挙して数え、最後に
出力して終了としました。
解説見たら同じような解き方していたのでまぁそんなもんみたいです。
https://atcoder.jp/contests/abc456/submissions/75417532
3.C - Not Adjacent
部分文字列の問題
各文字を先頭とした文字列を考え、それぞれに対し
次にくる文字が連続する位置までの部分文字列が作成可能であるため
その個数を数えて合計して出力しました。
と、簡単に考えましたが、文字が連続する事がない
長いSのケースでTLEとなるため工夫が必要となりました・・・。
【実装】
1.定数MODに998244353をセット
2.Sをインプット
3.LにSの長さをセット
4.X(現在参照している位置以降最初の連続位置をセット、初期値や連続が無い時は-1)に-1をセット
5.ans(文字列の連続が発生しない部分文字列の数)に0をセット
6.ac(現在参照している位置以降に文字列の連続があるかのフラグ。0がある、1が無し)に0をセット
→TLEになったため追加した変数。このフラグが立っていればそれ以降の部分文字列はすべて連続がない
7.以下、iを0からL-1まで繰り返し
-1.Xがi以下かつ、acが0(S[i]以降の始めの連続文字列の位置があるかどうかも含めて不明)の場合
-1.Xに-1をセット
-2.pre(現在参照している文字列の前の文字)に"ｄ"をセット
-3.bf(以下のループがブレイクした(連続があった)場合は１していない場合は0)に0をセット
-4.以下jをiからL-1まで繰り返し
-1.S[j]がpreと同じ場合(連続文字列発生)
-1.xにjをセット
-2.bfに1をセット
-3.7-1-4ループをブレイク
-2.S[j]がpreと異なる場合
-1.preにS[j]をセット
-2.ansに1を加算
-5.bfが0（ブレイクが発生していない（i以降文字列の末尾まで連続文字列が無い））の時acに1をセット
-2.Xがiより大きく、acが0(S[i]以降の始めの連続文字列の位置が判明している)の場合
→iから始まる部分列の数がループを回さず、計算(iからXまで)で求まる
-1.ansにX-iを加算
-3.acが1(S[i]以降連続文字列が存在しない)の場合
→iから始まる部分列の数がループを回さず、計算(iからLまで)で求まる
-1.ansにL-iを加算
8.ansをMODで割った余りを出力
https://atcoder.jp/contests/abc456/submissions/75443136
4.D - Not Adjacent 2
Cの発展問題。
dpを使うであろうことはわかるも組み方が分からず
1時間悩んで時間切れ。
解説を見るとなるほど意外と短いプログラムで解けることが分かり
理解できたものの、実戦でこのレベルのひらめきが出てくる
自信はありません・・・。
https://atcoder.jp/contests/abc456/submissions/75483441
以上