80:10 + 1ペナ 6完でなんとも
Gの方針は立ったけど、無駄なことしすぎた...
A A to Z String 2
割り算でできるけど、境界を考えるのがめんどくさいので愚直に文字列を構築！
(AC 1:51)
B 1D Pawn
ちょっと問題文難しいかも？
1つのコマが右のコマを追い越すことはないので、それぞれのコマの位置を記憶させておいて、隣にないなら+1することを繰り返します
まあ普通のBかな
(AC 5:43)
C Robot Takahashi
ド典型
Xは実数値と書いてありますが、f(X)が変わるところだけ調べればいいので、X = Wiを調べればよいです
ただし、全員大人・全員子供とする場合もチェックしないといけないので注意
(AC 12:31)
D Jumping Takahashi
これもド典型なんだけど、Dにしては難しいかも？
Sを決め打って二分探索ができるので、到達判定はN頂点からそれぞれBFSを回すことで行います
これGCJでやられたんですが、この制約だとマンハッタン距離の最大値が4x10^9になるので、いい感じに値を決めないとすぐにオーバーフローします
怖かったので、
2
-1000000000 -1000000000 1
1000000000 1000000000 1
がちゃんと動くことを確認してから提出した、えらい！！！
(AC 23:03)
E Addition and Multiplication 2
個人的にはDより簡単かなと思っていたんですが、そこまで通されてなかった
まず、桁数最大化が重要なので、最も安い数字を選んで仮の答えをつくります
その後は、上の桁から大きくできるならしたほうがよいです
これは、「今残っているお金」と「変えたときに余分にかかるお金」を比較すればよいです
あんまりコーナーとかもないような？？でもこういうのsubmitするとき怖いよね
(AC 32:10)
F Teleporter Setting
おもしろかったです！
そもそもグラフを有向だと誤読していてWAが大変なことに...サンプルも合っちゃうんですよね
集約される点をTとして、Tを使うかどうかで場合分けをします
もしTを使わないなら、単純に1~Nの最短距離が答えになります
Tを使う時をもう少し考えてみます
基本的に1からはTに早く到達したいので、行き先が変わるテレポーターがある場所のうち、1からの距離が最も近いところに行くのが最善です
TからNについても同様で、行き先が変わるテレポーターがある場所のうち、Nからの距離が最も近いところに行くのが最善です
ただし、「最も近いところ」がそもそもTだった場合を考慮しないといけないので、その場合分けを忘れないようにしましょう
(AC 65:10)
G Prefix Concatenation
みると方針としては結構あっさりたちます
Sの接頭辞がどうこう、っていう場合にはSとTをくっつけてZ-algoを適用すると、Tの文字それぞれについてSの接頭辞と何文字共通しているかわかって嬉しくなりやすいです
で、その配列を構築するとDPになります
具体的には dp[i] = Tのi番目まで埋めるための最小個数
と定義します
すると、DPの遷移は Z-algoで求まった値をzとして、dp[i+1] ~ dp[i+z]をdp[i] + 1と比較して小さい方に置き換えるというものになります
これは... Segment Tree Beatsだ！！！
まあ、正しいんですがあまり適切ではないです
区間chmin、1点取得は通常の遅延セグメント木でも対応できます
しらないSegment Tree Beatsを何とか使おうとした結果、対応できずに間に合いませんでした...
区間chmin, chmaxは遅延セグメント木でできる、覚えました
(AC コンテスト後)
総括
Eまではよかったんだけど、後がもったいなさすぎた
