JAPLJ Contest まとめと解説 - TopCoderとJ言語と時々F#

結果

hos.lyricさんが600点(全問完答)で、2位の420点に大差をつけて優勝でした！おめでとうございます！

2位以下は接戦で、上位陣は3完にあとどれだけ点数を上乗せできるかがポイントだったようです。

問題

A, B, C, D, E, Fの6問でした。すべてお花を題材にした問題文になっています。あと、問題IDと問題の名前の頭文字が一致しています。

難易度はA, B, Cが簡単でD, E, Fが難しい、の3：3構成でした。D, E, Fは予想していたよりも皆さんの点が低かったのですが、部分点有りのコンテストの醍醐味を味わって頂けたと思います。

謝辞

素晴らしいコンテスト環境を提供してくれた imos さん、問題のテストや改良に協力してくださった rng_58 さん、問題文の日本語校正を手伝って頂いた kioa2002 さん、ありがとうございました。

↓以下に出題した問題の解説があります

問題A Anemone 解説

解法

問題文が長ったらしいですが、要は方程式 g_n(t) = k の解の個数がちょうど p 個になるような n, k を求めればよいです。

わけわからん関数が出てきてよくわからないので、グラフを書いてどんな関数か把握しましょう。

要は g_n のグラフを書くと山が 2^n-1 個できます。

さらに次のこともわかります。

方程式 g_n(t) = 0 の解の個数は 2^n-1+1 個
方程式 g_n(t) = k (0 < k < 1) の解の個数は 2ⁿ 個
方程式 g_n(t) = 1 の解の個数は 2^n-1 個

解の個数は n に比べて指数オーダーで増えるので、p が20億あっても n はせいぜい30ちょっとです。なので、n を小さい方から回して全部確かめましょう。

基本的にはこれで解けますが、この問題には罠があります。 p = 0 のケースです。

p = 0 の場合、要は方程式が解なしになればよいので k を g_n(t) の値域外の値にすればよいです。それと、n は小さい方がよいので 1 としましょう。

感想

基本的には簡単な問題ですが、問題文が少し分かりにくくなっています。このおかげで(せいで)p = 0の罠にはまる人がたくさんいました。p = 0のケースが70点分のグループに紛れているのでそのまま放置というわけにもいかなかったようです。

また、パッと見で数式が出てきて、かつ意味がよくわからないということで混乱してしまった人もいるようです。グラフを書くなどして確認しましょう。

作問側の意図としては、Aなので簡単な問題であり、かつやるだけではない問題を目指しました。1度罠にかかって30点をもらったのち、100点をとる流れを想像しました。

問題B Banksia 解説

解法

上位 K 人に入っている可能性がある、を(コンピュータにとって)分かりやすく言い換えると「必ず負けると分かっている相手が K 人未満しか居ない」になります。

トーナメント戦は N-1 戦行われるので、その N-1 個の戦いのデータから「必ず負けると分かっている相手が K 人未満しか居ない」人を選び出すことになります。

ある人 A が B に負けることを A < B と表すと、問題文にある通り A < B かつ B < C なら A < C が成り立ちます。

チャンピオン以外の人は必ず1度負けますから、チャンピオンを根として、それ以外の人については自分が負けた相手を親とするような木を考えましょう。

すると、あるノード v についてその親を p(v) で表すと、 v < p(v) かつ p(v) < p(p(v)) なので v < p(p(v)) です。簡単に言えば、ある人はその親に負けるし、親の親にも負けるし、……、チャンピオンにも負ける、ということです。

つまり、その木において自分から根までの経路の長さが「必ず負けると分かっている相手」の数になります。なので、根から幅優先探索をして経路の長さが K 未満のところにある頂点を列挙するなどの方法で答を得ることができます。

感想

「必ず負けると分かっている相手が K 人未満しか居ない」の言い換えができればあとは容易です。それができないと色々変な選び方を試すことになってハマってしまうかもしれません。

あとは実装面で苦労した人もいたようです。根から幅優先をしようと思うと、親が子のリストを持つ形の表現をする必要があって、それが少し面倒かもしれません。ある子の深さ = その親の深さ+1 を使って深さを計算してやれば、子が親を持つ形の表現でよいので実装はだいぶ楽です。

作問側としては、特に罠もない簡単な問題として用意しました。10〜15分程度でみんな解いてくるだろうと思っていましたが、意外とハマっている人も多かったようです。

あと、Bで始まる花を探して問題文を書くのに苦労しました。お陰でバンクシアは全く関係のない問題文になっています。

問題C Cosmos 解説

解法

まず、問題の結び方は必ず存在します。

白とピンクの並びの中に必ず白とピンクが隣り合う場所があるので、そのふたつを結ぶことにします。するとその線分は他の線分と交差することはないので、そのふたつを除外してサイズのひとつ小さい問題を考えることができます。これを使って数学的帰納法で解が必ず存在することが示せます。

さて、すると問題は辞書順最小のものを求める方になります。辞書順最初にするには、要は時計回りに辿っていったときにできるだけ近いやつと結んでやればよいわけです。

しかし、下手なところと結ぶと線分が交差しないように出来ないかもしれません。その結ぶ相手の選択の基準として重要なのが、どのような並びでも必ず解は存在するという事実です。

つまり、白とピンクの花の数が同じであれば、どのような配置でも条件を満たす結び方が存在するわけですから、結んだふたつの間にある白とピンクの個数が同じであればよいことが分かります。

入力の並びを元に次のようなグラフを考えます。

ここで、ある点に対応する点を「自分の1つ前の値と同じ値を持つ最初の点」とすることで、条件を満たす結び方が得られます。たとえば2番目の点に対応する点を求めるときは以下のように。

ひとつ前に戻って、その右にある最初の点をさがしてそれと結べばよいのです。

これは、ある値をとる点のリストを保持しておくことで効率よく行えます。具体的には(↑の画像でいうと)

list[0] = 0, 10
list[1] = 1, 5, 9
list[2] = 2, 4, 6, 8
list[3] = 3, 7

というようなリストです。

感想

特段難しいわけではないので解ける人はたくさんいて、特段簡単なわけではないので解けない人もそこそこいるイメージで出しました。途中で50点だけとれた人はたくさんいたようですが、最終的には100点まで行った人が多かったようです。

問題文中の画像がだいぶヒントになっていると思うので、「だいたいこうやればいいんじゃないかなー」程度の解き方を思いつくのは簡単だったと思います。

問題D Dianthus 解説

解法

まず、パターンの大きさが全て d*d で固定されているので縦横ともに mod d で分類して考えましょう。これで d² 個の問題に分割できます。

分割された個々の問題では、フィールドから長方形の形に一定の値を引いていく問題になります。これを d² 回効率良く解く方法を考えましょう。

基本的なアイデアは二分探索です。ただし、ちょっとした工夫が必要になります。ただの二分探索ではなく、行ったり来たり二分探索を使います。

突然行ったり来たりとか言われても意味がわからないと思うので図とコードを使って説明します。ただの二分探索は以下のような実装になると思います。

def check(n):  # n 回分のスケジュールをこなすことが出来るか判定する
  フィールド全体を F で初期化
  for i=0 to n-1:
    フィールドから i 回目のスケジュール分を引く
  if フィールドの最小値 < 0:
    return false
  else:
    return true

def solve():
  lo, hi = 0, N+1
  while hi-lo > 1:
    mid = (hi + lo) / 2
    if check(mid):
      lo = mid
    else:
      hi = mid
  return lo

この普通の二分探索の様子を図にすると次のようになります。

一方、行ったり来たり二分探索は次のようなコードになります。

def check(prev, n): # n 回分のスケジュールをこなすことが出来るか判定する
  # フィールド全体の初期化は無し(前回の状態を引き継ぐ)
  for i=prev to n:
    フィールドから i 回目のスケジュール分を足す or 引く
  if フィールドの最小値 < 0:
    return false
  else:
    return true

def solve():
  prev = 0
  lo, hi = 0, N+1
  while hi-lo > 1:
    mid = (hi + lo) / 2
    if check(prev, mid):
      lo = mid
    else:
      hi = mid
    prev = mid
  return lo

これも図にすると次のようになります。

この方法をとることで、「フィールドに i 回目のスケジュール分を足す or 引く」の回数を減らすことができます。

通常の二分探索だと、 O(log N) 回あるステップごとに O(N) 回の操作が必要だったので「フィールドに i 回目のスケジュール分を足す or 引く」は全体で O(N log N) 回行われます。

一方行ったり来たり二分探索だと、 O(log N) 回あるステップごとに操作すべき範囲が半分になりますから、操作の回数は N/2 + N/4 + N/8 + ... = O(N) 回です。

さて、次に問題になるのは「フィールドに i 回目のスケジュール分を足す or 引く」一回にかかる時間です。愚直に実装すると一回に O(HW / d²) 時間かかってしまいますから、何とか高速化しなければいけません。

ここでは、「フィールドに i 回目のスケジュール分を足す or 引く」の操作は O(N) 回行われるが「フィールドの最小値を求める」操作は O(log N) 回しか行われないことに注目して、後者の処理に負担を押し付ける方法をとります。

具体的には、フィールドへの加算減算処理を愚直にやると次のようになりますが、

それをこうしてしまいましょう。

こうすると、一番左上からある区画までに書かれている数の和が、そのある区画における肥沃度を表すことになります。つまり、加算減算処理を O(1) で済ます代わりに、参照に O(HW / d²) 時間をかけるというわけです。

最小値はDPを使って O(HW / d²) 時間で求められますから、「フィールドの最小値を求める」操作は O(HW / d²) 時間で行えます。

以上をまとめると、solve関数は O(N + HW log N / d²) 時間で動くことが分かります。これを d² 回繰り返すわけなので、全体では O(N d² + HW log N) 時間です。

感想

問題設定はなかなかシンプルですが、1000*1000のフィールドに100000回の処理を行うという数字がいかにもキツそうに見えます。部分点を得るのは簡単ですが、効率のよいアルゴリズムを考えつくのは難しかったかもしれません。

部分点つきのコンテストでは貪欲に部分点を狙うことも重要ですから、この問題のように部分点が楽にとれるものはとってしまったほうがよいでしょう。

それと、この問題でそこそこ思いつきやすい解法としてはsegtreeの類を使うというものがありますが、segtree は定数倍の影響が大きすぎてよい点を得るのは難しいと思います。

問題E Edohigan 解説

解法

まず、時刻の範囲を表す T が最大で 10⁹ と非常に大きいので、以下の事実を確認しておきましょう(自明だと思います)。

長方形を置き始める時刻は、0か、もしくは他のあるグループが立ち退いた瞬間だけ考えればよい。

すると、長方形を置き始める時刻はせいぜい O(M) の候補しかないので、これを全部試す方向でいきます。

ある時刻から長方形を置き始めると仮定して、そのとき面積が N 以上の長方形を最大でどれぐらいの時間確保することができるかが高速に求まれば嬉しいので、それを考えましょう。

ここではそのために二分探索を使います。もし長さ t だけ確保することが可能なら t 未満の時間だけ確保することも可能であり、長さ t だけ確保することが不可能なら t 以上の時間だけ確保することも不可能ですから、二分探索が適用できますね。

さて、二分探索を使うと決めたので、問題は「面積が N 以上の長方形を長さ t だけ確保することができるか？」というところまで落とせました。

これを解くのはそこまで難しくありません。 X*Y個あるマス目それぞれについて、もし現在時刻からそのマス目ひとつを長さ t だけ確保することができるなら「可能」を、できないなら「不可能」を割り当てます。あとはその二次元配列に最大長方形を見つけるDPを適用して、その面積が N 以上なら可能と判断するだけです。

感想

問題文の通りに問題を解こうとすると、長方形の形は面積が N 以上であれば自由で、その場所も自由で、いつから置くかも自由で、とにかく自由が多くてどうすればよいのか分からなくなってしまうかもしれません。

そういう時はその自由をできるだけ制限してやりましょう。この問題では、いつから置くかの自由を制限しました。そのあとも更に問題を分割して、できるだけ簡単な問題に落としこんでいけばそれほど難しい問題ではありません。

ただ、この解法は少々実装が面倒だと思います。この解法は O(XYM log T) 時間で動きますが、これとだいたい同じ時間で動くアルゴリズムもいくつかあります(それらを頑張って落とそうとしてTLEが5秒になりました)。

ちなみにこの問題はもともとCに配置されていて、Cherryという題名でした。Eに移ることになって、花見の設定を保ったまま題名を変更するのに苦心した結果、Edohiganという謎題名になりました。

問題F Flowers 解説

解法

まず、エリア a, b を結ぶ道を新たに敷設したとすると、もともとの木に存在した a-b 間の経路と新たに敷設した道によって周遊路が形成されます。つまり、新たに敷設する道を選ぶことは与えられた木の中で経路を1本選ぶことと同じです。

さらにこの問題では周遊路がエリアを共有してはいけないわけですから、それをより形式的に言えば頂点を共有しないような K 本の経路を選べ、というわけです。

最初に与えられる木をてきとうな頂点を根として根付き木として扱いましょう。その上で次のようなDPを行ないます。(以下、modをとる部分はすべて省略します)

dp[v][k][0] == 頂点vを根とする部分木内で、頂点を共有しないk本の経路を選ぶ方法の数
dp[v][k][1] == 頂点vを根とする部分木内で、頂点を共有しないk本の経路を選ぶ方法の数。ただし、頂点vはどの経路にも含まれていないか、ある経路の端にあるかのどちらかである。

最終的な答は dp[根][K][0] になりますが、 dp[v][k][1] のほうも計算に使います。

このDPの計算は子を順次見ていくことで行ないます。ある頂点vについて計算する場合、先にその子については計算を終えておきます(つまり深さ優先の帰りがけ順で計算します)。

ここで補助的なDPをもう一段階行う必要があります。頂点vの子は全部でN個あって、それぞれ便宜上1〜NのIDがついているとします。n番目の子をnext[n]とでも書くことにしましょう。そこで次のような定義をします。

s[n][k][0] == 子1〜nをそれぞれ根とする部分木内で、合計でk本の経路を選ぶ方法の数
s[n][k][1] == 子1〜nをそれぞれ根とする部分木および頂点vの中から合計でk本の経路を選ぶ方法の数。ただし、頂点vはある経路の端の頂点である。
s[n][k][2] == 子1〜nをそれぞれ根とする部分木および頂点vの中から合計でk本の経路を選ぶ方法の数。ただし、頂点vはある経路の途中の頂点である。

するとこのDPは次のように計算されます。

s[0][0][0] = 1
for n=1 to N:
  for i=0 to K:
    for j=0 to i:
      s[n][i][0] += s[n-1][j][0]*dp[next[n]][i-j][0]
      s[n][i][1] += s[n-1][j][0]*dp[next[n]][i-j][1] + s[n-1][j][1]*dp[next[n]][i-j][0]
      s[n][i][2] += s[n-1][j][1]*dp[next[n]][i-j][1] + s[n-1][j][2]*dp[next[n]][i-j][0]

この s をもとに最初のDPは容易に計算されます。

for k=0 to K:
  dp[v][k][0] = s[N][k][0] + (k>=1 ? s[N][k-1][2]+s[N][k-1][1] : 0)
  dp[v][k][1] = s[N][k][0] + s[N][k][1]

感想

この問題ははじめはもっと簡単な設定だったのですが、testerのrng_58さんによってこの難易度になりました。自分はこの手の問題に決して慣れているわけではないのですが、rng_58さんによれば慣れている人には典型問題だそうです。ただそのわりには上位陣の挑戦が少なかったように思います。

部分点がかなり細かく設定されているので、試行錯誤して頑張ることで出来るだけの部分点を得るという解き方ができますが、そうした人は少なかったようです。この問題に手をつけた大体の人はとりあえず10%をとろうとしているようでした。ちなみに10%は二項係数 C(N, 2K) を計算するだけです。

題名と問題文は6問中いちばん適当です。