Codeforces Round #86 (Div. 1 Only)

びみょーん

418(1WA) / (WA) / - / - / -
137位 1834 -> 1873

Petya語は以下のような言語である。

与えられた単語の連続が、文か単語1語であるならYESを、そうでないならNOを出力せよ

実装する。語尾が〜ってC++だと判定めんどいので関数にする。
書いた。送信。

WA.単語一語でYESを出力するってのを見落としてた。
訂正して再送信。Pretest Passed.

長さ2000以下の文字列が与えられる。文字列の連続する部分文字列で、Sbeginで始まりSendで終わるようなものはいくつあるか求めよ。

Sbeginの位置を全部列挙して、Sendの位置を全部列挙して、
Sbegin以降のSendの数を足していくだけなのでは。

書いてみる。サンプル合わない。
あ、位置が違っても文字列自体が同じなら一つと数えるのか。

じゃあ今までに出てきた文字列を覚えておかないとダメだ。
え、そんなん間に合うの？部分文字列n^2個あるぞ。
set使って書いてみる。aが2000個のケースとか余裕で間に合わない。

うーん。じゃあrolling hashでも使おう。
するとO(1)で部分文字列かの判定ができる。
書いてみる。送信。

WA.
なんだろう。rolling hashの計算間違えたか？直して何回か送ってみるけどWA.

うーん。
何気なくa2000個のケースを実行してみると、答えが1になってる。
a,aa,aaa,aaaa,....が全部同一の文字列に見えてるようだ。
あ、rolling hashがin[i]-'a'だもんそらそうだ。in[i]-'a'+1とかにしてみる。

Pretest Passed.

l以上r以下の素数で、a^2+b^2の形で書けるものの数を求めよ。
l,r≦3*10^8

3億とかでかすぎる。そもそも3億までの素数が篩では作れない。
a^2+b^2の形で書ける数も数億あってループじゃ無理。

何か数学的な性質を使うのだろうか。

とりあえず、4で割って1余る素数は必ず平方数二つの和となることを調べた。
うーん、だから何だ。
メモリ節約して篩ができたりするのか？いや無理だろ……

埋め込み？手元で3億まで篩ってみると素数ありすぎて埋め込みもきつそう。
お手上げなのでDを読んでみる。

美術館はn個の部屋がm本の通路でつながった形をしている。
二人が最初a,bの部屋にいて、次のように動く。

このとき、i番目の部屋で二人が初めて出会う確率を求めよ。

n≦22, 0.01≦p[i]≦0.99

いかにもDPっぽい感じの問題。
連立方程式が立って解けるんだろうか。

ターン無限の極限を考える。両辺=0になってなにも出てこない。
うーん。

収束するまでまわせばなんか答え出そうな気がする。サイズ小さいし。
コード書いてみる。サンプルすら合わないで時間終了。

Bが落ちた。
SbeginにSendが完全に含まれる場合を考慮してなかった。

実はそれでもダメで、setを使うったこと自体でTLEになってた。
setの代わりに自作のハッシュテーブルを使うと通った。