ABC209参加しました。

A - Counting

B - Can you buy them all?

ずっと1円引きではなく、1割引だと思ってたので、なぜWAなのかわからなかった...

配列として受け取った場合、Aは0から(A[0])始まります(そうならない言語もあるかもしれません)。問題文ではAは1から始まるので、そこのズレを解消するため、偶数番目で1円引きするのではなく、奇数番目で1円引きします。表で書くと以下のようになります。

問題文とサンプルをよく読んで、まず問題文の意味をつかみます。

まずソートしても答えには影響がないので、ソートします。

次に、入力例2をもとにして考えます。入力例2は
N=4, C = (3,3,4,4)
でした。

ここから以下の図を考えます。

この図で、それぞれの$C_i$の数だけ玉が下に並びます。玉の選び方がそのまま答えになります。
玉は左から選んでいきます。このとき玉を選んだら、その行の(=右方向の)玉は選べません。これは、問題文の制約2を満たすためです。

答えの例としてA=(1,2,4,3)があります。選べない玉は赤線を引いてあります。

他の例としてA=(3,1,4,2)があります。

こう考えると、各列での玉の選び方は、前の列までで選ばれた玉の数分だけ減っていくことがわかります。

あとは単なる玉の組み合わせの問題です。最初は玉は自由に選べるので、A[0]通りそのまま。次はA[0]で選んだ玉は選べないのでA[1]-1通り、この次はA[2]-2通りとなり、最後はA[3]-3通り。これらの組み合わせの総数は、その積となります。

まとめると以下のようになります。

for(int i = 0 ; i < N ; ++i){
  ans *= A[i] - i;
}

適宜MODを取ることを忘れないようにしてください。

最初にソートしておくことが大事で、これがないと、上のロジックが使えません。

面白い問題でした。ACしたかった。

公式解説を元にしてACしたコードを張っておきます。以下理解を確認するために解説。

まず実際に各クエリごとにグラフを辿ってRoadかTownかの判定するのではなく、「高橋さんの都市(ノードA)と青木さんの都市(ノードB)の間の距離L」から判定できそうだとわかります。Roadの場合、Lは偶数ですし、Townの場合、Lは奇数になります。簡単な例で確認してみてください。

こう考えると、クエリの度にLを求めるのではなく、予め全都市間の距離を予め求めておけば、LをO(1)ですぐに求められて、よさそうと思うかもしれません。しかし、例えば、前回のABC208Dにあった、ワーシャル・フロイド法だと、計算量がO(頂点数³)になり、TLEしてしまいます。

ここで発想を変えてみると、偶奇で決まるのなら、2部グラフとして考えられそうです。(ここが思いつかなかった...)また、今回の場合、各都市が木構造になるのも使えます。

つまり、各頂点をA,B2つのグループに分けます。このために、例えば都市1を木のrootとして、各都市の「rootからの距離」を予め求めておきます。これはそのノードの深さに相当します。この距離が偶数か、奇数かでA,Bのグループに分けます。

分けられたら、高橋さんと青木さんがどちらのグループから出発したかによって、Town,Roadが求められます。同じグループから出発していたらTown,違うグループからならRoadになります。

rootからの距離は簡単なBFS,DFSで求められます。この計算量はO(頂点数+辺数)なので、時間的にも間にあいます。

また、後で公開された解答(ABC209 - yunix_kyopro’s blog) には、rootからノードA、rootからノードBの距離を合計した距離の偶奇を見ても問題ないことがわかります。

どのみち、大事なのは、各頂点のrootからの距離を求めるところであって、最終的にクエリを処理する部分が「rootからの距離の偶奇を判定する」か、「距離の和の偶奇を判定する」かの違いでしかありません。

Dはなるほどなと思いました。ずっとワーシャルフロイドの計算量を削減できないかとか、とにかく全都市間距離を手早く求められないかということに頭を取られてしまったのが悔しいです