脳log[20211206]

2021年12月06日 (月) [AtCoder] 精進。JOIG 2021 過去問／D - 展覧会 2 (Exhibition 2)。まずは TLE & WA だけど 39/100 点の提出 #27698611。よくある DP をした。あるインデックス i より右から j 個の要素を選んだ場合の価値の最低値を記録する DP。これを j が 1 から M に至るまで繰り返した。N と M の上限がともに 10 万だから二重ループが TLE になるのはわかる。でも WA が 7 個(もしくは TLE の背後にそれ以上)あるのはわからん。■個数と価値を記録するのでなく個数だけ記録するのはどうだろうかと考えた。i 番目の絵画の右と左に合わせて M-1 個(以上)の絵画が飾れるなら、i 番目の絵画の価値は答えの候補になる。右からと左からの２度のスキャンで済むから処理時間は足りる。だけど M 番目に大きい価値がいくつになるのかがわからない。■制約をメタ読みすると N^2 はダメでも NlogN の処理は許されている。ある価値で足切りした場合にいくつの絵画が飾れるか。足切りラインの探索に二分探索を、いくつの絵画が飾れるか調べるのに２度のスキャンを繰り返してもまだ時間は足りる。提出 #27735789 (100 点 / 617 Byte / 792 ms)■スキャンは２回１セットである必要はないみたい。自分にはわからんけども。■JOI が何かも知らないなら JOIG が何かも知らなかったけど、G は Girls の G だったらしい。EGOI などというものもあって J (日本) 固有ではないらしいけど、あえて for Girls をもうけるモチベーションはよく周知してほしいと思う。わからないから。女子を集めて愛でるためではないだろうし、数的能力に性差を認めて平等に活躍の機会を与えるための不平等な取り扱いというわけでもないだろうし。母集団の大きさが違いすぎるのかなという気はするけど、分類の基準は性別に限らず能力別も考えられるはずで、決め手に欠ける感じがある。■■■E - パレード (Parade)。普通かな。逆行する回数を１ずつ増やしながらプライオリティキューでダイクストラ法を繰り返した。提出 #27742640 (100 点 / 1112 Byte / 535 ms)。頂点 0 と頂点 1 から 0 への辺を追加するとメインループのコピペが解消できる。