https://csacademy.com/contest/beta-round-4/summary/
$N$個の文字列が与えられるので、アナグラムとなるような文字列の集合のなかで一番大きいもののサイズを出力せよ。
各文字列をソートして、同じものをmapなどで数えればよい。
自力AC。簡単。
区間[$A,B$]が与えられる。この区間に含まれる整数全てに対して、最も大きい奇数の約数をすべて足し合わせたものを出力せよ。
ある整数に対して、最も大きい奇数の約数とは、その整数を2で割れるだけ割った数に等しい。よって、奇数の場合は自分自身である。
区間[$A,B$]の和は[$1,B$]の和から[$1,A-1$]の和を引いたものと言い換えられるので、以下では簡単のために区間[$1,N$]を考える。
1から数えて$N$個めまでの奇数の和は$N^2$となることが知られていて、これに偶数の最大奇約数の和を足し合わせたものが答えである。ここで、[$1,N$]のすべての偶数を1度ずつ2で割ったものの和は[$1,\frac{N}{2}$]の和に等しいことから、[$1,N$]のすべての偶数の最大奇約数の和は[$1,\frac{N}{2}$]の最大奇約数の和に等しいことがわかる。これを再帰的に繰り返せば目的の値が得られる。
解説AC。なるほどなぁ。
$N$要素の数列が与えられる。この数列には$\frac{N}{2}$個の整数がそれぞれちょうど2回ずつ含まれている。この数列の隣り合う2要素をswapすることを繰り返して、同じ要素どうしがすべて隣り合うように並び替えるための最小の操作回数を出力せよ。
数列の中で、2つの整数$i$のうち左側のものが$l_i$番目に、右側のものが$r_i$番目にあるとき、その2つを隣どうしにするためのコストは区間[$l_i,r_i$]の中であればどこでも同じであり、かつ最小である。このことを利用して、数列の一番左の要素を変えない最適解が常に存在することがいえて、その場合は一番左の整数のペアを2番目に持ってくることになる。このようにして残った数列に対しても同じ方法を適用していけばよい。
操作の回数を求めるのは簡単で、各整数を最終的な要素の番号に置き換えた数列に対して転倒数を求めるだけである。
解説AC。考察惜しいところまでいってた気がするけど、後一歩ができなかった。
大学の図書館に本が一冊あり、その本を読みたい教授が$N$人、学生が$M$人いる。それぞれの人が図書館に到着する時間と本を読むのにかかる時間が与えられるので、全員が本を読み終わるまでにかかる時間の最小値を出力せよ。ただし、教授は本を一人で読むが、学生は複数人で同時に読むことができる。また、本を読んでいる途中で他人に交代することはできない(一度に読みきらなくてはならない)。
最初に教授と学生をそれぞれ図書館への到着時間でソートしておく。ここで、教授が読むぶんの時間は絶対に全員分かかるので、教授は到着順に本を読んでよい。学生の場合は、自分よりもあとに自分より長く本を読む学生がいる場合にはその学生が読むときに一緒に読めば良いので、実際問題として順番が前後することはない(ある学生が本を読むタイミングは、自分以上に長く本を読む学生のなかで最も遅く来る人と同時としてよい)。 ここで、以下のようなDPが考えられる。
$DP[i][j][0]=i$番目までの教授と$j$番目までの学生が全員読み終えた状態での最小経過時間(最後に本を読んだのが 0:教授 / 1:学生)
このDPの更新は愚直に行うとO($NM^2$)となる。これは学生をどこからどこまでまとめて読ませるかということを更新のたびに探索しているからである。実際には、前述の考察によってすべての学生は自分以上に長く本を読む学生のなかで最も遅く来る人と同時に読むのが常に最適であることがわかっているので、「自分以上に長く読む学生が自分より後にこない学生」のみを考えてよく、これで更新を単純化することができる。
以後、自分より後に自分より長く読む学生がいない$M^\prime$人の学生のみを考える。DPテーブルの更新は以下のように行う。
$DP[i][j^\prime][0]$は、以下のうち小さい方の値である。
$DP[i][j^\prime][1]$は、以下のうち小さい方の値である。
時間計算量はO($NM$)となる。
解説AC。O($NM^2$)から落とせなかった。CSAでは最後に[0/1]のフラグをつけるDP(複数のテーブルを管理するDP)が結構多いかもしれないと思った。
はじめに$N$要素の数列があり、この数列から使用可能な要素を1つずつ選択して使用不能にしていく操作を考える。数列の値と操作不能にする順番が与えられるので、各操作を行った後の数列全体の(使用不能な要素を含まない)連続な部分列のなかで、その総xorがもっとも大きくなるものの総xorを出力せよ。
以下、区間[a,b]の総xorを$xor(a..b)$と表記する。 $$xor(a..b)=xor(1..a-1)\oplus xor(1..b)$$ より、数列のなかで総xorが最大となる区間を見つけることは$xor(1..a)\oplus xor(1..b)$が最大となる$a,b$を見つけることと等しい。
Binary Trieを使えば、ある整数$x$に対して$a \oplus x$が最大となるような$a$をO($\log{a_{max}}$)で探すことができる。これを利用して、Binary Trieに$0, xor(1..1), xor(1..2), \cdots, xor(1..N)$を順番に入れながらすでに入っている要素との最大xorを探すことで、ある数列に対して区間総xorの最大値がO($N\log{a_{max}}$)でわかる。
この問題では数列の要素が順番に使えなくなっていくが、これを逆順で見ると要素がひとつずつ使えるようになっていくと考えることができる。ここで、$i$番目の要素が使えるようになったときにその要素専用のBinary Trieを構築して$xor(1..i-1), xor(1..i)$を入れ、さらに左右の要素が使用可能であれば左右のBinary Trieとマージすることを繰り返せばこの問題を解くことができる。ここで、Binary Trieに要素を入れる際には常にすでに入っている要素との最大xorを取る。Binary Trieは常に小さい方を大きい方にマージすれば挿入操作は合計でO($N\log{N}$)回となり、全体の時間計算量はO($N\log{N}\log{a_{max}}$)となる。
解説AC。Binary Trieを使ったことがなかったので、勉強になった。
兵士が$N$人おり、各兵士の身長はそれぞれ異なる。さらに、これらの兵士は異なる2つの大隊から来ていることがわかっている。各兵士について「自分の所属している大隊で自分より背の高い兵士の数」と「自分の所属していない大隊で自分より背の低い兵士の数」が与えられるので、ありうる大隊の分け方の総数を$10^9+7$で割った余りを出力せよ。さらに、ありうる分け方をbit列で表したときに辞書順最小となるものを出力せよ。なお、必ず有効な分け方が存在することが保証されている。
以下、各兵士の入力を(taller, shorter)と呼ぶ。
身長が同じ兵士はいないので、「もっとも背の低い兵士」が必ず存在する。もっとも背の低い兵士は、shorterが0であるような兵士のうち、tallerが最大のものである。ここで、もっとも背の低い兵士が所属する大隊の人数はそのtaller+1人であることがわかる。これを$X$とすると、もう一つの大隊の人数は$Y=N-X$人とわかる。
兵士を背の低い方から順に見ていくことを考える。$i$番目に背の低い兵士まで見たとき、大隊0出身の兵士が$A$人、大隊1出身の兵士が$B$人いたとする。この情報から$i+1$番目に背の低い兵士を特定することが可能である。
$i+1$番目に背の低い兵士が大隊0出身だった場合、その兵士の回答は($X-A-1, B$)でなくてはならない。同様に、大隊1出身であれば($Y-B-1, A$)となる。ここで、それぞれの回答をしている兵士が存在するかどうかを調べ、どちらかしか存在していない場合はその兵士が次に背の低い兵士であるとわかる。
両方存在している場合にも特定可能である場合がある。$A\lt B$であれば、大隊1出身のほうを次の兵士とすべきである。なぜなら、大隊0のほうを採用してしまうと各隊の人数が($A+1, B$)となってしまい、($Y-B-1, A$)と答えた兵士の証言に矛盾が生じるからである。同様に、$B\lt A$であれば大隊1出身のほうを次の兵士とすべきである。
両方存在していて、かつ$A=B$であるときは2人の兵士の回答は($X-A-1, A$), ($Y-A-1, A$)と書き換えられる。このとき、その2人は最終的に同じ大隊に所属することになる。これはshorterの値に自分が所属していない方の現在の大隊の人数を参照しているためである(2人ともshorterの値が$A$であるという条件を満たすにはそうするしかない)。このことから、次の兵士はtallerが大きい兵士とすべきである。
$A=B$であり、さらに$X=Y$である場合には次の兵士をどちらの大隊に振り分けるべきかということは一意に決まらない。また、この状況が起こった場合にはこれ以前の隊分けはこれ以降の隊分けに全く影響しなくなる(これ以降を新たに独立した問題と考えてよくなる)(このことを「世代が変わる」と表現することにする)。
全く同じ(taller, shorter)をもつ兵士はかならず異なる大隊の所属となる。これは、同じ大隊にtallerが等しい兵士は存在し得ないからである。このことから、同じ回答の兵士は3人以上存在しないことがわかる。また、同じ回答の2人の兵士について、どちらを大隊0とするかということは常に自由に選んでよい。
辞書順最小を構築することを考える。世代ごとに2種類の解が存在し、それは大隊0と大隊1のどちらを'0'として出力するかということである。これは、各世代で「同じ回答の兵士が自分以外にいない兵士」のなかでもっともindexが小さい兵士が'0'となるようにすべきである。これを各世代について行い、回答が同じであるような2人の兵士についてindexが若い方を'0'、そうでない方を'1'とすると辞書順最小の解を作ることができる。
次に、有効な解の数を数えることを考える。解がバリエーションをもつ条件は、先述の大隊分けの際に「どちらの兵士を使っても良い状況」もしくは「どちらの大隊に入れても良い状況」が発生したときに限られる。つまり「同じ回答の兵士が2人いる場合」もしくは「$A=B$かつ$X=Y$となった場合($A=0$かつ$B=0$の場合を除く)」である。これらの状況が発生するたびに有効な解の個数は2倍になっていく。よって、最終的な解の個数はかならず2のべき乗となる。
解説AC。コンテスト本番中にACした人が誰もおらず難易度HARDESTとなっているが、面倒さは確かにHARDESTという感じだった。だが、アドホックな問題であって高度なアルゴリズムが必要となるわけではないため純粋にコーナーケースの多さによるものか。とりあえずもう二度とやりたくない。