Educational Codeforces Round 70 (Rated for Div. 2)
参加しました。
A You Are Given Two Binary Strings...
問題：1と0のみの2進数の文字列ｘとｙが与えられる。yをk個左にずらしてｘと足したとき、最大で下何ケタに0を連続できるか。kで答えよ
考察：
xが0ならyを無限にずらせばよいです
それ以外のときは、xの一番下の1を繰り上げたいです
この操作ができるかは、yの1の位置で変わります。
繰り上がりが行えるのは、yの一番下の1より左側です。
なのでその範囲で一番下になるようなｘの1を探します。この差がkで答えです。
B You Are Given a Decimal String...
問題：1桁の整数x,yがあり、zが0から始まり以下の操作を行う。
操作：zにxかyを足す。zの下1桁を出力する
いま、出力結果だけわかっているとき、x,yの全ての組み合わせでこの出力が行えるか調べよ。もし任意の箇所に任意の数字を挿入することで実現可能なら、挿入する必要のある数字の最小個数を求めよ
考察：
あるx,yについて考えます。
このx,yで0~9を表現する必要があります。
高々xを10個、yを10個使う場合の100通り程度で、表現する整数ｋが10通りなので10＾3の全探索で求まります。
また、与えられた出力結果で、隣り合う数字の差をカウントしておきます。
カウントしたk*表現するための最小個数を足せばよいです。
もし表現できないkが出力結果にあったら不可能です。
C You Are Given a WASD-string...
問題：グリッド上をWASDで与えられた入力通りに動く。任意の箇所でWASDのどれかを最大1つ挿入することで、移動範囲を含む長方形を最小化せよ。
解けなかったのでやった範囲の考察を書いておきます。
考察：
横と縦で分割して考えます
ある方向に動く範囲を1減らせるかどうか判定すればよいです
ほとんどの状況で1減らせるように思えますが、最大値に到達したあと0に戻る場合はできません。
例えば横方向に[0,R]の範囲を動くとして、Rに到達した後、0に来るとします。
Rに到達するまえにAを挿入し、最大値をR-1とすると、最後には[-1,R]となります。
したがって、そうなるかどうか調べてやればよいです。だったんですけど弾かれたので違いました。
※解けたので追記
上とほとんど同じです
L→R→Lなど、逆側の端を更新した後、ちょうど端を通っていると減らせません。
実装：
Rの端を更新：R_cnt=1、yoko_flag=true
Lの端を更新、または通る：R_cnt++;
Rの端に到達：もしR_cnt>1ならyoko_flag=false。
この3つの操作を4方向で行います。
yoko_flagは横方向に移動範囲を狭められるかのbool変数で、RとL方向で共通です。
最後に、縦横で縮まさるなら小さい方、どちらかならその方向に縮める。どちらもできないなら移動範囲を出力。といった操作をすれば完了です。
感想：
大変苦労しました…。
考察手順としてはそこまで突飛ではないですが、実装全体が見えずバグりやすくてしんどかったです。
累積するやり方があるらしいので気が向いたらやりたいと思います。しばらくは見たくない…
D Print a 1337-string...
問題：1と3と7のみで10＾5以下の文字列を構築せよ。この文字列に含まれる1337という文字列がnになるようにせよ
考察：
まず簡単に11...1133....337...7のように、137が順番に並んでいる文字列を考えます
このときそれぞれの個数をx,y,zとします。1337はx*y*(y-1)/2*z個あります
n<=10^5-3のとき：1がn個、337とすればよいです
nが大きいとき：3の数を増やす必要があります。nが上の式のように表せないとき(例えば素数)、1337を1ループではダメそうです
では2ループさせてみましょう。このとき複雑にすると式を解けそうにないのでどうにか簡単にしてみます
1(3*y)7(1*x)337
このとき1337の数は
yC2 + (y+2)C2 + x
になります(１と７に着目すると数えやすいです）
yの項がnを超えないように、できるだけ増やします。
nに足りな分xで補完すればよいです
大きくても大体y=3.3*10^4、x=6.6*10^4程度で、ぎりぎり足りると思います。Hackされたらやだなあ。
E You Are Given Some Strings...
問題：文字列tと、N個の文字列sが与えられます。全てのi、jについてtの中の連続する部分文字列にsi+sjが現れる数を合計して求めよ。
考察：
誤読してsi+sjの中にtにして書いたところで気付いてやめました。
文字列系のアルゴリズムがZ algorithmしかないのでうーん
もしそれぞれでやると計算量壊れるからうーん
ツイッター見た感じエイホーコラシック法とローリングハッシュっていう単語が見えたんで、そこらへん勉強したら良さそう。そのうちやります。
感想
ABDの3完でした。1時間ちょいで3つ通せたので結構調子良かったと思います。そこまでは。
そのあと40分くらいCが通らず頭抱えてました。もうだめだと思って順位表見たら260位くらいでびっくり。みんなCで事故ってたみたいですね。ラッキー(？)
predictorでは+83とかなりおいしいです。ぐんと紫近づきますね。
Hackされなければですけど。わーい。
次回のDiv2で紫は無理そうだけど近いうちに慣れたらいいなと思います。じゃ
