C1まで三完。C2もD1も難しい……。
C2. XOR-convenience (Hard Version)
分からず解説を見てAC。
2ベキだと解が存在しないことは分かるが、そこからどうすれば良いか分からなかった。
nが奇数ならC1のままでOK。
nが偶数でもC1の解法を利用を考えるべき、というのが重要か。
そのままだと、最初の要素が上手くいかないので、そこをどこかとswapすれば良いのでは？ と考え、最上位bitに思い至れば構築方法が分かる。
偶数の場合、全く別の構築方法が必要だと考えてしまったのがまずかったかもしれない。が、普通に難しい気がする。
D1. Little String (Easy Version)
苦戦したが自力AC。
こちらはcについてはあまり考える必要がなく（答えがn個程度の数の積になるため）、数え上げを行う問題。
まず、S[0]="0"やS[-1]="0"のときは存在しない。
それ以外のとき、0001という部分を一度に考える。
012までの位置関係が決まっているとし、そこに3～6を付け加えるとすると、6はその最も左か最も右におくしかない。そして、3～5は端以外のどこにおいても良い。
なので、2（左右）*3*4*5をかける。
……というのを繰り返していく。
かなり長いこと実験したら気付けたけど、難しかった。
0 件のコメント:
コメントを投稿