ベイン さんはインスタンス qiitadon.com のユーザーです。アカウントさえ持っていればフォローしたり会話したりできます。 もしお持ちでないなら こちら からサインアップできます。

A 英字列の各文字を前後に1ずらして回文にできるか判定する問題

左右の対応する各文字について、片方がa/zなら完全一致、そうでなければ差が 0 か 2 ならOK、だと思ったけどWA

BCD完。DがぎりぎりだったからAのWAが直せなかった / [Dashboard - Educational Codeforces Round 49 (Rated for Div. 2) - Codeforces](codeforces.com/contest/1027)

何が悪かったかというと、普通に区間の除去ができてなかった。自作テストケースが間違ってたから気づかなかったけど

今日ABCだから明日にすればよかった

なんか Idle limit exceeded 出てたけどちゃんとデバッグ出力消えてるよね

昨日は配列と next[i] = (要素 i の次の要素) の組み合わせにしたけどちゃんと動いてる自身ない

インデックスアクセスでの要素の参照と更新、区間の削除が高速なデータ構造について考えてる

Rust力が低くてツリーを作れなかった

D (WA解法) すべて0ならQで埋める。aの最左の出現位置をL[a]とする。q=Q..1 につき、L[q]から始まる 0,q だけからなる最長の区間を求めて除去する。除去した数のうち左端のものの左側にある0を除去する。全区間が除去できたらOK

(ただし q=QのときQの出現がなければ最左の0をQにする、できなければ失敗)

たぶん考慮漏れがある。あるいはもっとエレガントに解ける?

A ~~正規表現が標準ライブラリにないので~~ *の前後で切ってTの前後をみる
B x+y のyとしてありえる範囲を計算
C カッコ式Xから長さ |X| - 2n の部分式が必ずとれる。だから連接 XY から部分列を選ぶとき、左辺から可能なかぎり大きい部分式を選んで、残りをYから選ぶ

Cコンパイラのセルフホスティングやってみたい

単純な正規表現ではパターンが長すぎてつらく、手書き再帰下降ではめんどく、パーサコンビネータやパーサジェネレータを持ち出すほどではない、みたいな絶妙な言語カモン

ある種の構文解析は、字句解析してから各字句を1文字で表す文字列にして、正規表現で構文解析する、みたいな手法が有効なこともありそう。やったことないけど

テキストの一部を隠すやつ使ったほうがいいかも

解けた

問題:文字列のペア (e.g. S=codeforces, T=for) が与えられたとき、部分文字列 S[l..r] に T が何回出現するかを高速で数えよ、という問題。

解法:累積和。S[0..r] 中のTの出現回数と、Tの出現の最初の文字の個数 (つまり r の位置でぶち切られてしまっている出現の個数) を数えておけば求まる / "Codeforces 1016 B - Segment Occurrences" #41654931 codeforces.com/contest/1016/su

解けた。問題文(長い)を読むほうが難しいやつ…… / [Submission #41653679 - Codeforces](codeforces.com/contest/1016/su)