JavaScriptでABC411(A-D)
A - Required Length
「Pの長さ ≧ L」かどうかでYes/Noの出力を変えれればそれでOK。
私は三項演算子を使っていますが、初心者向け想定解法はたぶんif-else文
0分56秒 AC!
B - Distance Table
- 駅1の座標を0としたときの駅iの座標を
pos[i]とかで取れるようにします - 二重forで出力します。内側のループの初期値に注意
D(与えられたデータ)とpos(累積和にしたほう)がごっちゃになって時間かかっちゃいました、なにしてるんですか
追記 : Bって累積和出るんだって思いながら解いてたんですけど、これ50駅しかないんで普通に3重ループ書けばいいですね へへへ
7分30秒 AC!
C - Black Intervals
反転はisBlack[a] = !isBlack[a]みたいな感じでやればいいとして、今何区間あるかを数えると時間がかかって間に合わなさそうなのでなんとかしないといけません。
で、反転した場所とその両隣だけ見れば、反転による区間の増減数はわかりそうだなとなります。
|
|
左隣 | 右隣 | 区間の増減数 |
|---|---|---|---|
| 黒→白 | 白 | 白 | -1[1] |
| 黒→白 | 白 | 黒 | ±0[2] |
| 黒→白 | 黒 | 白 | ±0[2:1] |
| 黒→白 | 黒 | 黒 | +1[3] |
| 白→黒 | 白 | 白 | +1[4] |
| 白→黒 | 白 | 黒 | ±0[5] |
| 白→黒 | 黒 | 白 | ±0[5:1] |
| 白→黒 | 黒 | 黒 | -1[6] |
ということで、最初に「現在の黒区間の数」のカウンターをletで持っておいて、1操作ごとに区間が増減する条件を満たしたらカウンターを操作したあとにカウンターの値を出力すればOKです。
17分05秒 AC!
D - Conflict 2
なにがむずいんだ……？って顔をしながら愚直に書いたらTLEしました、D問題がそんな簡単なわけ無いだろう
解説を見ました 文字列のコピーってO(文字数)なんですね
「N個目のクエリの後のサーバーの値」と、「N個目のクエリの後のPCPの値」を求める関数は、それぞれお互いを使う形で書けます。
// - N個目のクエリのあとの鯖の値 = (N以下でtype=3な最大のindex)個目のあとのPC[p]の値
// - N個目のクエリのあとのPC[p]の値
// = (N以下でtype=1かつp=pな最大index)個目のあとの鯖の値
// + ↑以降N未満type=2かつp=pなそれぞれのindexについて、index個目のsの値
// - ただし、(0未満)個目のあとはどちらも空文字列
ってやったら通りました。なんで早くなったのかもわからん……！
56分11秒 AC! (1ペナ)
E-G
なんの検討もつきません……なんですかこれは
やけに制限時間が長いやつが多いですね今回
Perfomance
- perf : 1180
- レート変化 : 795 → 841 (+46)
感想
大勝ちじゃないですか〜！そして入緑も達成！
B問題でこんがらがって時間食らったのがもったいないですが、350点のC問題と425点のD問題を解けたので許します。
グラフもDPもちゃんと勉強してないし、なんならBFSとDFSもちゃんと書けた試しがない状態でも緑まで行けるものなんですね……。早解きは大事。
一旦区切りはつきますが、ひとまず水コーダー(1200)は目指していこうと思います。いい加減グラフと二次元グリッドを倒せるようになろうね……！
過去のABCも似たような記事を書いています。よければそちらもどうぞ。
- ABC410 (A-C)
- ABC409 (A-D)
- ABC408 (A-C)
- ABC407 (A-C)
- ABC406 (A-D)
- ABC405 (A-D)
- ABC404 (A-D)
- ABC403 (A-C)
- ABC402 (A-D)
Discussion