Dと最後三問が解けずの11完でした。
D - 立方体を壊せ！
立体図形は苦手なので飛ばしたが、落ち着いてやれば解けることは解ける。
まず、$x+y+z=K$という平面は、(K,0,0),(0,K,0),(0,0,K)を通ることをイメージする。立方体の頂点から各辺（座標）の方向に、切片が1ずつ動いていくイメージ。
それができれば、$K<N$のときが三角錐で、$K>2*N$のときが、立方体から三角錐を除いたものだということが分かる。
問題は、$N<K<2*N$のときだけど……。
ちゃんと図を描けば、$K<N$のときと同じように作った三角錐から、角の三角錐三つを切り取ったものだと分かった。
あまり立体が得意でない私でも分かったのだから、他の人でも分かるはず！ と言うのは容易いけど、私より立体が苦手な人だっているはずで、そういう人にどう説明すれば良いんだろう。
図を描くこと自体にそこそこ立体図形の能力が必要な気がするしねぇ。
私自身、もう少し捻られたら自力で解くのが難しくなる気がする。（いや、色々断面描いて頑張るけど……）
数学を勉強しても、あまりこういう立体をイメージする能力は伸びない気がする。厳しいね。
H - その計算、合ってますか？
コンテスト中にWAを量産してしまった。
各ビットごとに考えると、orが1のところでしかandやxorは1にならないことが分かる。
あとは、「andが1のところは一斉に1を取る」ことに気付くのが重要。偶数回出現すればxorは0、奇数回ならxorは1になる。
各ビットごとに考えていると解けない問題。
とはいえ、各ビットごとに考えるのは基本なので、そう考えてハマってしまうのはある程度仕方ないか。
J - Output-only
「5, 12, 13」で検索したらこのページがでてきた。なるほど。
見たときは何これ、と思ったけど、よく見れば自力でも思いつけそうな式か。
M - 貢ぎ物
結構考えたけど分からず、解説を見てAC。
「高速ゼータ変換」というキーワードを見たがどういうものか忘れていた。この問題のすぬけさんの解説を見たのは結構最近なのに……。名前と内容が結びつきにくいので、覚えにくいのかも。
しかし、そのキーワードを見ても解けず。
各$A_i$が$2^{20}$以下なので、$2^{20}$要素のDP配列を持つことは思いついた。だが、その配列を「その数を作れるか、否か」の01だけを持つものとしても上手くいかない。
それを、DP[i]で「iに含まれる数j達で作ることができる最大の数」（つまり、DP[j]たちをorしたもの）とすると上手くいく。
$2^{20}$要素の配列を持つというところはあってそうだけど、01だけを持つのは無駄なので、他に何か持てないかな……？ と考えたら思いつけたのかな。
N - 背の順
コンテスト後に問題を見て、自力でできるかと思ったら苦労してしまった。
二つ以上の区間を消す必要はない。なぜなら、$[l_0, r_0], [l_1, r_1]$を消すなら、$[l_0, r_1]$を消した方が得だから。
$[L, R]$を消す場合を考える。
$L$の候補は、左端$A[0]$か、左から順に調べて$A[i-1]>A[i]$が成り立つ$A[i]$のどちらかになる。そのような$i$に対して、$j>i$なる$j$を消すと消した後がソート済にならないし、$A[1]～A[i-1]$を消すなら$A[0]$や$A[i]$を消した方が得なので。
その後、$R$も同じように、候補が二個程度に絞れる……と思ってWAを出してしまった。
左右対称な気がしてしまったが、実際はそうではない。
$L=0$のときは簡単。
$A[i], A[i+1], \dots $がソートされているような最小の$A[i]$が最適なRになる。
もう片方の場合も、
$R$は「$A[i], A[i+1], \dots $がソートされている」ような範囲の中にある。求める$R$は、この範囲で、
・$A[L-1]<A[R+1]$
が成り立つような最小の$R$である。
たとえば、
・$A=4, 1, 2, 3, 5$
の場合を考えると、$L$の候補は$A[0]$と$A[1]$だが、$L=A[0]$に対応する$R$として最適なのは$A[1]$, $L=A[1]$に対応する$R$として最適なのは$A[3]$となる。
公式解説がDPだったのは驚き。全く考えなかった……。
O - Xor Sum Sum
解説AC。
最上位bitから考える……といった方法も頭をよぎるけど、A,Bの数字が小さいので、なんらかの方法で全探索するのかな、とは考えた。
が、基底を考える方針は全く浮かばなかった。言われてみればなるほど、という感じでした。
なお、xorの掃き出し法は、noshi91さんの方法が簡単。これで良いと納得するのには苦労したけど、一旦分かれば忘れない方法ですね。
0 件のコメント:
コメントを投稿