コンテストへのリンク
B. Just Eat It!
「全ての連続部分列の和が、全体の和より小さい」かどうかを判定する問題
・連続部分列は、元の列から左右を削ったもの
→左右の連続する何個かの列の和が0以下になっていれば良い。
→が、和が負になるためには、片方0以下でなくてはいけないし、片方が負ならそれ以外の部分列をとれば良いので、左右からの累積和を見て０以下の部分があるか調べればOK
C. Fadi and LCM
整数$X$が与えられるので、$LCM(a,b)=X$なる$a, b$のうち、$max(a,b)$が最小になるものを求める
・たとえば、8が$X$の約数のとき、$a$か$b$のどちらかは8の倍数になる。LCMを考えているので、片方に2、片方に4のように振り分けることはできない。ならば、中途半端にせず、片方に8を割り振るのがベスト
・なので、どの素因数を$a$に割り振るか調べれば$a, b$の値は定まる。
→bit全探索
そもそも、
・上位bitから0か1かを決めていく
はXORの問題では重要ですね。
D. Dr. Evil Underscores
yukicoderにそのままの問題があったらしいけど、自分はそれは解いてなかった。ただ、別のyukicoderの問題「No.911 ラッキーソート」に近いと感じた。そもそも、
・上位bitから0か1かを決めていく
はXORの問題では重要ですね。
E. Delete a Segment
けんちょんさんのブログやながたかなさんのブログに解説があります。
これらの解説や公式解説で共通するのは、各セグメントを見るだけでなく、各時間における重なり合いを見ているところ。つまり、Hello2020のDで書いた「区間のままみるのではなく、時間ごとにみる」という発想の転換を使っている。
私もコンテスト中にそのことは考えたのだけど、結局、それでそんなに簡単になると思えなかった。実際、そうしても実装は結構大変だと思う。（これらの解説を参考に書いたのがこれです。長くはないけど、「どこで+1するか」とかがややこしくてきつかった）
だから、（私のコンテスト中の方針である）各セグメントごとに考えてもいけるんじゃないの？ と思って、さっき通したのですが……。非常に大変でした。もっと上手く書けるのかもしれないけれど……。
一応、このコードでしていることを簡単に書きます。
・とりあえずソートして、
・左右それぞれから、そのセグメントまで順に使ったときのUnionの個数のリストを作る
-左から考えるときは、i番目までの右端の最大値を使えば更新していける。（これをLEFTという名前にします）
-右から考えるとき（この名前をRIGHTとします）が難しい。
★
S[i] = [l,r] としたとき, 左端がr以上のものの中で一番左にあるセグメントが何番目かを二分探索で求める。→x番目だったとする
S[x]=rなら、RIGHT[i]=RIGHT[x]、ではなく、「RIGHT[i+1]～RIGHT[x]の最小値」がRIGHT[i]になる（図がないと分からないと思うけど、どういう図を描けば良いかよく分からないので省略。すみません）。
これを、（RIGHTを値として持ち、区間の最小値を得られる）セグメント木を更新しながら求めていく。
S[x]>rなら、RIGHT[i]は、RIGHT[x]+1、もしくは、R[i+1]～R[x]の最小値。
★
・これを使って、i番目を取り除いたときを考えたい。
-左側はLEFT[i-1]でOK
-右側は、i-1番目までの最大値を使って、★と似たようなことをすれば求まる
これ、★というほぼ同じことを二回やっていて、その上結局、RIGHTの配列は使ってないから、★は一回にまとめられるはずですよね……。整理すればもう少し簡単になるはずですが、整理するにも頭が混乱してしまい大変です。
方針としては自然だと思うんだけど、どうでしょう？
これらの解説や公式解説で共通するのは、各セグメントを見るだけでなく、各時間における重なり合いを見ているところ。つまり、Hello2020のDで書いた「区間のままみるのではなく、時間ごとにみる」という発想の転換を使っている。
私もコンテスト中にそのことは考えたのだけど、結局、それでそんなに簡単になると思えなかった。実際、そうしても実装は結構大変だと思う。（これらの解説を参考に書いたのがこれです。長くはないけど、「どこで+1するか」とかがややこしくてきつかった）
だから、（私のコンテスト中の方針である）各セグメントごとに考えてもいけるんじゃないの？ と思って、さっき通したのですが……。非常に大変でした。もっと上手く書けるのかもしれないけれど……。
一応、このコードでしていることを簡単に書きます。
・とりあえずソートして、
・左右それぞれから、そのセグメントまで順に使ったときのUnionの個数のリストを作る
-左から考えるときは、i番目までの右端の最大値を使えば更新していける。（これをLEFTという名前にします）
-右から考えるとき（この名前をRIGHTとします）が難しい。
★
S[i] = [l,r] としたとき, 左端がr以上のものの中で一番左にあるセグメントが何番目かを二分探索で求める。→x番目だったとする
S[x]=rなら、RIGHT[i]=RIGHT[x]、ではなく、「RIGHT[i+1]～RIGHT[x]の最小値」がRIGHT[i]になる（図がないと分からないと思うけど、どういう図を描けば良いかよく分からないので省略。すみません）。
これを、（RIGHTを値として持ち、区間の最小値を得られる）セグメント木を更新しながら求めていく。
S[x]>rなら、RIGHT[i]は、RIGHT[x]+1、もしくは、R[i+1]～R[x]の最小値。
★
・これを使って、i番目を取り除いたときを考えたい。
-左側はLEFT[i-1]でOK
-右側は、i-1番目までの最大値を使って、★と似たようなことをすれば求まる
これ、★というほぼ同じことを二回やっていて、その上結局、RIGHTの配列は使ってないから、★は一回にまとめられるはずですよね……。整理すればもう少し簡単になるはずですが、整理するにも頭が混乱してしまい大変です。
方針としては自然だと思うんだけど、どうでしょう？
0 件のコメント:
コメントを投稿