ABC127 E. Cell Distance

問題

N*Mのマス目のKマスに1つずつ駒を置くことを考える。
ここで、K個の駒が(x1,y1), ...., (xK,yK)と置かれるときの配置コストを
Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|)
とする。
駒のすべての配置の仕方のコストを考えたとき、その配置コストの総和を10^9+7で割ったあまりで求めよ。

制約

• 2 <= N*M <= 2*10^5
• 2 <= K <= N*M
• 入力はすべて整数

解法

問題は、
Σ_{すべてのあり得る駒の配置} Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|)
= Σ_{すべてのあり得る駒の配置} (すべての駒のペアについてそのマンハッタン距離を求めたときの合計値)
を求めよ、ということを言っている。

ある2つの駒が(xi,yi)と(xj,yj)に置かれる状況を考えると、この2つの駒がそこに置かれるような配置は、この2つ以外の駒がこの2か所以外に置かれる通りだけあり得るので、(M*N-2)_C_(K-2)通りだけ答えの中で出現している。
しかし、これを使って求めるのだとペアを決めるのにO(N*M * N*M)かかってしまうため、もっとまとめ上げて計算してあげる必要がある。

まず、マンハッタン距離の性質として、x軸とy軸は独立に求められるので、xだけを考える。(ただし、駒の配置は2次元のまま考える)

まとめあげとして、|xi-xj|を求めたいので2つの駒の距離に注目すると、この距離がdであるような場合を考える。
距離がdであるようなx軸の選び方は(M-d)通りあり、選んだ軸の左側と右側それぞれN通り置き方があり得るので、結局、(M-d)*N*N通りあることがわかる。(距離dは1～Mまで考えればよい)

したがって、求めたい値のx軸については以下のようになる。
Σ_{d=1}^{M} d * (M-d)*N*N * (M*N-2)_C_(K-2)
これをNとMをひっくり返してy軸についても同様に求めてあげれば答えが求まる。

計算量は、組み合わせの計算の部分が重くて実装方法次第だが、O(N*M)程度。

反省

• 問題を誤読＆制約を見間違っていた(N,Mと思ったがN*Mだった)
  • 制約はなんか同じような見間違いをしていた人が多かった模様
  • なんか問題読解にミスってることが最近多い気がするので、ちゃんと時間かけて読むようにする
• 組み合わせ問題は、言い換えが重要なので、どういう言い換えをしているかなど知見を貯める

ABC126 F. XOR Matching

問題

以下の条件を満たす長さ2^{M+1}の数列aが存在するなら1つ構築せよ。

• 数列aには、0以上2^M未満の整数がちょうど2つずつ含まれる
• a_i == a_jになるi,jについて、a_i xor ... xor a_j == Kとなっている

制約

• 0 <= M <= 17
• 0 <= K <= 10^9

解法

明確にわかる条件から抑えていく。

M=0のときは、K=0しかだめで、そのときの答えは「0 0」。
M=1のときは、同じくK=0しかだめで、答えは「0 0 1 1」か「1 1 0 0」。「0 1 0 1」のようなものは、0で挟まれる部分が1で、1で挟まれる部分が0になってしまう。

M=2の場合を考える。
まず、Kは2^M以上の場合、XORを取ってKが作れないので、構築できない。したがって、「K < 2^M」である必要がある。

M=2のときに現れる数字は、0 0 1 1 2 2 3 3の8つ。
実験として、これをnext_permutationで全通り試して、条件を満たすものを出力して観察すると、「Kを作って、それを両側から挟んでいるような形」が多く見受けられる。
具体的には、「X Y 0 K Y X」や「X Y K Y X」のような形ができている。

ここから、あるKについて、その両側を挟んでいくような形で考えると、同じ数字はxorを取ると0になるので、満たすことがわかる。
なので、Kを置いてその両側を挟むように他の数字を対象に置いていけばK以外の数字は条件を満たす。
ただ、Kが1つ余っており、これをどこかに置く必要があるが、すでに置いたKの両側には、0から2^M-1までの数字でKを除いた数字が並んでおり、このxorを考えるとKになっている。
(「0から2^M-1までの数字でKを除いた数字のxor」とKのxorが0にならないといけないため、Kであることがわかる)
したがって、「Kの両側に対称となるようにK以外の数字をならべ、最初か最後にKを置いたもの」は条件を満たすため、これを返せばよい。

Google Code Jam 2019 Round 2 A. New Elements: Part 1

0完だった。。。(点数分布的にAのlargeは通さないとACDのsmallだけでは無理そうだったので時間をかけてたけどsmallすら通せなかった・・・)

問題

CodiumとJamariumという新しい元素を研究しており、これらの原子量に関する統計を調べたいと思っている。
過去の研究より、これらの原子量は厳密に正の値であることはわかっている。

今、N個の分子が与えられている。この分子は上記の2つの原子のみが何個か組み合わさって構成されており、i番目の分子のそれぞれの原子の構成要素数が(Ci, Ji)で与えられる。
分子の重さは、原子量の合計値で表される。

最初の調査として、原子量によってはこの分子を重さ順に並べたいと思っており、「厳密に増加するように並べる並べ方が何通りありえるか？」を知りたい。何通りあるか、答えよ。

例：分子が「(1,1), (2,1), (1,2)」の3つの場合、
Codiumの原子量がJamariumの原子量よりも重い場合は、(1,1), (1,2), (2,1)。
Jamariumの原子量がCodiumの原子量よりも重い場合は、(1,1), (2,1), (1,2)。
同じ原子量の場合は、(2,1)と(1,2)が同じ分子の重さになってしまうため、厳密に増加しないため、条件を満たさない。

制約

• 1 <= T <= 100
• 1 <= Ci, Ji <= 10^9
• 与えられる分子で構成要素が同じものはない
• 2 <= N <= 300
• 制限時間は20秒以内
• メモリ制限は1GB

解法

元々の原子量がわかっていないので、それを変数として考えたい。
それぞれの原子量を(x, y)と考えてもよいが、片方の原子量がXとして、もう片方はその比率wをかけたX*wで考えると、定数Xが与えられた下では1変数wだけで扱える。
そこで、Codiumの原子量をXとしてJamariumの原子量をX*wとして考える。

i番目の分子の重さは、「Ci * X + Ji * X * w = X * ( Ci + Ji * w)」と書ける。
問題文の条件から、0 < wである。
ここで、各分子の重さを横軸w、縦軸分子の重さとした2次元平面にプロットすると、各分子の重さは直線で表現でき、wがw'の場合の順序はグラフのw=w'と直線の交点(下から上にぶつかる順)になる。

ここで、プロット図を観察すると、交点の位置は同じ重さになっている点なので、上記の条件を満たさない、かつ、その左右で分子の重さの大小関係が必ず入れ替わっているということがわかる。
ただし、Sampleの#2のような交点が同じwで2つ以上ある場合やw=0の点で交点がある場合もあるので、ユニークや0になる場合を含めずにカウントしてあげれば、「その交点があるwの数+1」の領域が並べ方の数になる。

2つの直線の交点は、Xは関係しないので直線を「Ci + Ji * w」とすると、
y=ax+bとy=cx+dの交点はa!=cの時w=(d-b)/(a-c)になるので、それを使えばよい。
小数で扱うと誤差が怪しいので、有理数でカウントする(gcdなどで既約にして扱えばよい)。

反省

• 原子量の重さが(1,1), (1,∞), (∞,1)だけを考えればよいのでは？とか答えは1か2だけ？とか最初に思ってしまって、その方向で嘘解法を生成してた(謎に先入観にとらわれすぎてた)
• smallだけの解法も結構難しい、、、

Google Code Jam 2019 Round 1B C. Fair Fight

問題

N種類の異なる武器が2つずつ並べてある。
あなたは審判で、まず(L,R)の範囲を指定する。
対戦者のCharlesとDelilaは、その範囲内の武器の一つを選んで対戦を行う。
また、それぞれ人の武器の熟練度がCiおよびDiで与えられ、それぞれ範囲内で一番熟練度が高い武器を使って戦うことがわかっている。

審判として、フェアな戦いとなるようにしたいので、選んだ武器の熟練度の差が高々Kとなるような(L,R)の選び方をしたい。そのような範囲の選び方はいくつあるか？

制約

• 1 <= T <= 100
• 0 <= K <= 10^5
• 0 <= Ci, Di <= 10^5
• 制限時間は30秒以内
• 8ケースがN = 10^5、それ以外は1 <= N <= 1000

解法

あるiが必ず含まれるような範囲を考える。
このとき、範囲はざっくりと以下のような形になっている。

[条件を満たさないLの範囲][条件を満たすLの範囲][条件を満たさないL,Rの範囲(iを含む)][条件を満たすRの範囲][条件を満たさないRの範囲]

各範囲は、0個かもしれないことに注意。

このとき、iを必ず含むような範囲の個数は「(条件を満たすLの範囲)の個数 * (条件を満たすRの範囲)の個数」で求められる。

すべてのiについて求めることを考えると、上記の範囲をO(logN)程度以下で求めたい。
そこで、二分探索で上記のそれぞれの範囲の境界を見つけることを考える。

LとRはそれぞれ同等の方法で求められるので、Rについて考える。
次のように3つの条件に分けて考える。
(1) max(Ci, ..., Cj) <= Ciを満たす範囲
(2) max(Di, ..., Dj) <= Ci+Kを満たす範囲
(3) max(Di, ..., Dj) < Ci-Kを満たす範囲

iからjの累積和をsum(0,j)-sum(0,i-1)で求める様な感じで、「(2)かつ(1)の範囲」から「(3)かつ(1)の範囲」を引くことで、上記の「条件を満たすRの範囲」の個数を求めたいが、それぞれのmax値はセグメント木などでO(logN)で求められるので、十分高速に求められる。

また、Ciが同じ値の場合などで重複してカウントしてしまう可能性があるので、(1)で範囲を求めるときに、すでに計算を行った領域を使わないようにしたい。
これは、Ciが大きい順からiを処理していき、Ciが同じ場合は、iが小さい順から処理して、Lの(1)の計算時に前のところを含まないようにしてあげればよい。

Google Code Jam 2019 Round 1B B. Draupnir

問題

「X-day ring」というものがあり、これは、X日ごとに分裂し、2倍の個数になるリングである。
最初は、1-day ringから6-day ringまでの6種類のリングがそれぞれ何個か(0個以上100個以下)ある。

今、1日目から500日目までのいずれかの日でのリングの合計数を2回だけ問い合わせることができる。
ただし、数が大きくなりすぎるため、2^63で割ったあまりが返ってくる。

最初の日(0日目)にあったリングのそれぞれの個数が何個だったかを答えよ。

制約

• 1 <= T <= 50
• 問い合わせ回数W = 2

解法

何日か経つと、リングの個数がかなり大きくなることがわかる。
また、2の累乗の倍数のいずれかになるため、0日目のi-day ringの個数がRiとすると、「(2^x) * Ri」のような形で書くことができる。

ここで、数が大きくなりすぎた場合、2^63で割ったあまりが返ってくることから、2^xの部分が2^63以上になったら2^63の倍数となるため、Riに関する要素が合計数に含まれなくなる。

また、0日目のリングの個数は100個以下であることがわかっているので、7bit以下で表現でき、「(2^x) * Ri」のxの部分がうまく7以上はなれるような日が見つけられれば、ビット部分からRiを求めることができる。

なので、「1-dayから3-dayが2^64の倍数となるような個数、かつ、4-dayから6-day ringが7bit以上離れるような日」で4,5,6-day ringの個数を求め、「1-dayから3-dayが7bit以上離れるような日の合計値から4-dayから6-day ringの個数を引いたもの」から1,2,3-day ringの個数を求めれば、0日目にあったリングの個数をすべて求められる。

Google Code Jam 2019 Round 1B A. Manhattan Crepe Cart

問題

グリッドがあり、各交差点は0からQまでの番号の組で表現できる。
今、P人の人が交差点に立っており、それぞれ、東西南北のいずれか一方を向いている。
各人は、向いている向きの方向に1交差点進んだ領域のどこかの交差点に用事があることがわかっている。(例えば、(Xi,Yi)で北を向いている場合は、北をy軸の正方向とすると、y>Yiとなる領域の交差点のどこかに用事がある)

今、各人の用事がある可能性がある領域で一番人数が多い交差点を見つけたい。
ただし、同じ人数の場合は、一番南西にある交差点を答えよ。

制約

• 1 <= T <= 100
• 1 <= P <= 500
• 20秒以内
• Q = 10^5

解法

2次元領域だが、各軸は独立に考えることができる。
なので、各軸についてimos法などで範囲更新して、一番数が多いところを見つける。
あとは、それぞれの数が多いところの和が2次元領域でも一番数が多いところになっているので、そのなかでも一番南西となる地点を答えればよい。

Tenka1 Programmer Contest 2019 D. Three Colors

問題

N個の整数aiが与えられる。
この整数に赤、緑、青のいずれかの色を塗る。
このとき、以下の条件を満たすような塗りかたの通り数を998244353で割ったあまりを求めよ。
「それぞれの色で塗った整数の和をR,G,Bとするとき、三辺の長さがそれぞれR,G,Bであるような正の面積の三角形が存在する」

制約

• 3 <= N <= 300
• 1 <= ai <= 300

解法

三角形が正の面積を持つ条件は、「三辺のどれか一辺が他の二辺の和より長い」と言える。
三辺の和は整数の全部の和で得られるので、和をSとすると、「すべての辺は長さ1以上で、一番長い辺の長さ < S/2」であればよい。

これを直接求める代わりに、余事象・包除原理っぽく考える。
求めたい通り数は、
(全塗りかた) - ( R>=S/2 ) - ( G>=S/2 ) - ( B>=S/2 ) + (R>=S/2かつG>=S/2) + (R>=S/2かつB>=S/2) + (G>=S/2かつB>=S/2) - (R>=S/2かつG>=S/2かつB>=S/2)
で求められる。

塗りかたは3色のいずれかなので、全塗りかたは3^N。
対称性からGとBの計算はRと同じなので、「R>=S/2」と「(R>=S/2かつB>=S/2)」はそれぞれ求めたものを3倍にすればよい。
「R>=S/2かつG>=S/2かつB>=S/2」はそのようなのは作れないので0通り。

「R>=S/2」は、dp[i][j]:=i番目までで赤に塗った整数の合計がjとなるような通り数、を求めて、dp[N][S/2以上]の合計を求めればよい。
(更新式は、GまたはBを選んだ場合「dp[i+1][j]+=2*dp[i][j]」、Rを選んだ場合「dp[i+1][j+v[i]]+=dp[i][j]」で遷移すればよい)

「(R>=S/2かつB>=S/2)」は、それぞれが等号の場合しか成り立たないので、Sが2で割り切れるときのみ考慮する。
これもdp[N][S/2]の通り数で求められる。

エクサウィザーズ2019 C. Snuke the Wizard

問題

N個のマスが並んでおり、各マスには1体のゴーレムと1文字が書かれている。
ここで、呪文を唱えると、ある文字の書かれたマスにいるすべてのゴーレムを右か左に1マス移動させることができる。
マスの外側に移動させられたゴーレムは消滅する。
Q回の呪文が与えられるので、最終的にマスに残っているゴーレムの数を答えよ。

制約

• 1 <= N, Q <= 2*10^5
• 文字は英大文字のみ

解法

あるマスxにあるゴーレムが左側から消滅する場合、マスx-1にあるゴーレムも(通過するはずなので)必ず左側から消滅する。(右側も同様)
なので、消滅するか否かを二分探索で位置を求めればよい。

反省

本番中は、両端から消滅ゴーレムは連続するのは気づいたけど、呪文を逆順にして消滅する範囲がどこまでか？を見つける様な方法でアプローチしてしまった。
これの場合、

2 2
AB
A R
A L

のケースでは、1つ目のマスのゴーレムが落ちる様な計算をしてしまうが、そのゴーレムは呪文1で2つ目のマスに移動していてゴーレムがないので、消滅するゴーレムはない。
なので、消滅しない範囲に移動したかどうかも同様な感じで求めればいいか？と提出したけど、両端からの範囲が重なるようなケース

2 3
AB
B R
A R
A L

など、いろいろ嘘だった。

Topcoder MM108 CrosswordPuzzler

概要

1週間マラソンはきつい。
最終順位は、20位(58人参加)で、結構良かった。

問題

W*Hのグリッドと辞書(単語の集合)が与えられるので、グリッド上に単語を敷き詰めたい。
このとき、グリッドに敷き詰めたときに、縦方向か横方向に2文字以上が並んでいる場合、必ず辞書にある単語になるようにしなければならないし、2回以上同じ単語がでてくるようにはしてはいけない。
スコアは、フィボナッチ数列fib(x)を用いて「Σ_{グリッドに出現する単語i} fib(i)」とするとき、スコアができるだけ高くなるようなグリッド敷き詰めを返せ。

最終的に提出したアプローチ

seed6 beam searchの雰囲気 pic.twitter.com/tSkcLQCU0L

— phyllo (@phyllo) February 21, 2019

• ベースはビームサーチ
  • ただし、計算時間の都合で、グリッドのサイズでパラメータを調整
  • 単語は、真ん中付近(サイズが小さかったら微妙にずらしたものも候補に入れた)
• 評価関数は「単語スコア合計+文字を置いていないマスの数-使ったマス数」
  • お気持ちは、重なりが多いほどよさそうと思ったので、できるだけマスを使わずにたくさん置いた方がいい、という感じ
  • 単純なスコアにしてしまうと、終盤までスコアに差が出ずに、ビーム幅を必要としそうだったので、できるだけ序盤でも差がでるようにしたかった
• 辞書は、長さ順にkグループに分け、順番にビームサーチで最適化するようにした
  • 単語数が減るので、最適解が得られない可能性があるが、計算量が減らせて、辞書サイズが多くてもまわせた

振り返り

1週間マラソンで、土日が腰痛でダメで何も手を付けられなかったのがかなり痛かった。

方針決め

これまでのマラソンの反省として、「最適解の形がどんな形か？」のイメージをミスるとお話しにならないと思ったので、ざっくりでも最適解の形を考えた。

具体的な形まではわからなかったけど、

• 長い単語をできるだけ使う
• 単語がクロスしている方が、少ないマスで表現できるので、よさそう

は間違いなさそうで、クロスを多く作るような形を目指すことに。

(最初の時点での理想イメージとしては、以下のような図でいくつか歯抜けになるようなものなんじゃないか？を考えていた)

最初は、焼きなましが適用できないか？と考えていたけど、単語を消したときの処理が面倒そう、と思ってビームサーチ方面で考えることにした。
(この時点で、最適解はぐちゃぐちゃ絡み合ったイメージを持っていたので、greedyな解は無理では？と思って除外してしまっていた)

面倒そうというのは、辞書が{aaa,ccc,bacb}の場合、

-a--
-a--
bacb
--c-
--c-

と置いて、bacbを消した場合、acを残してもacが辞書にないのでinvalid、acも消してもaa,ccがinvalidになるので、invalidを許すか、invalidを許さない場合は連鎖的に単語を削除していくイメージ。
invalidは最後まで残すと解消が無理そうだし、invalidを許さない場合、単語の連鎖が多くなりそう、と思ってあきらめた。
(終了後、onigiri(utmath)さんとの感想戦で「消せないなら消さない」というのもあるよね、というアイデアは考慮できていなかった)

テスター、ビジュアライザ

今回、testerがエラー出力を握りつぶしていたり、visualizerが付いていなかったので、デバッグが非常につらく、途中からc++で書き直したりしてた。

seed6 (my visualizer is text editor. wtf :( pic.twitter.com/iOxlVpf3xW

— phyllo (@phyllo) February 21, 2019

visualizerはなかったので、テキスト出力で見てたけど、縦長になってしまったり、クロスしている文字がどこなのか見にくく、ちゃんと整形して表示するものだけでも作るべきだった。

(結局、終わってからビジュアライザを作ったらそんなに時間かからずできたので、作るべきだったかも・・・)

ビームサーチの調整

ビームサーチをやろうと思ったら、結構生成される近傍が大きくなってしまって探索空間が大きそうというのにハマる。

妥協案として、真ん中付近に一番長い単語を置いて、そこからできるだけ長い単語をクロスするように設置していく(クロスできないならできるだけ長い単語を適当に置く)方法を試す。
結局、これ以外の方法などは時間がなくて試せなかった。

感想戦で、「いうほどクロスが多くない」という話が出ていて、ビジュアライザを作っていれば気づけたかもしれないと思う・・・

パラメータの調整

単純に上記の探索だと無駄な探索も多くて時間がかなりかかっていたので、ある程度時間内に終わるよう調整を考えた。

一つ目は、長さが小さい単語は使う必要があまりないor後で設置すればよさそうかもと思い、辞書を長さごとにグループ分けして、計算量を減らすことを考えた。

二つ目は、サイズが大きすぎるときのパラメータ(ビーム幅や辞書の分割数など)を調整してた。けど、あんまりやりたくなかったので、適当に時間に間に合いそうな値にして提出して、結局最後までそのままだった。。。

その他

盤面や辞書の生成ルール的に、「大きいケース」と「小さいケース」に偏りがあると思って、見ていた。
計算してみると、だいたい、マスのサイズが1000以下になるのが63%ぐらい、1000より多くなるのが37%ぐらいで、半分以上がマスのサイズが1000以下の小さいケースのようだった。

辞書サイズも小さいので、できるだけ小さいケースは十分な探索をできるように調整したかったけど、最終提出には入れられなかった。

反省

• アプローチ
  • 今回は様々な手法が有効だったようで、
    • greedyに単語(またはフレーム)を置いて、それをランダムに繰り返す感じ
    • より多くの交差、より長い単語が最初になるような多くのrandom searchを試す
    • 焼きなましで配置や追加削除を試す(＋様々な工夫)
    • 市松模様っぽく単語を配置しつつ、できるだけ単語を串刺しにする感じを焼きなましする
    • など
• visualizer
  • やはり簡単でも作るべきだなと思った(テキスト出力では印象が違う・・・)
  • wleiteさんのvisualizerが見やすかった
  • https://twitter.com/wleite/status/1098404095759654913

ビジュアライザ

終わった後で、ビジュアライザを作った。
GitHub - jetbead/TopCoderMM108_Visualizer: Topcoder MarathonMatch 108 Visualizer

課題意識としては、

• 最終状態の出力ではなく、焼きなましやビームサーチなどの途中状態も見れるようにしたい
• ファイルに書き出す方法だと膨大な量になってしまったり、読み込み面倒なので、できるだけC++で完結させたい
• macで手頃で使えるのにしたい

というのがあった。

QtやGTKなどはやや大がかりすぎるような気がして、OpenSiv3Dは新しめのコンパイラを必要とすることから、一番手頃そうなSDL2を試してみた。(「ゲームプログラミングC++」という本でも使われていたのを見たので)
悪くなさそうなので、他の手段も調べつつ、いろいろ使ってみたい。(できれば、visualizerで必要な要素をまとめたい)

第3回RCO日本橋ハーフマラソン予選 参加記

概要

第3回RCO日本橋ハーフマラソン予選に参加してみた。
atcoder.jp

結果は、A問題が102位、B問題が45位の総合67位でした。(結構善戦できたと思う)

問題

A. ツーリストXの旅行計画

N個の都市を1度だけずつ順番に巡って最初の年に戻ってくるようなルートを考える。
都市間の移動距離をの分散ができるだけ小さくなるようなルートを見つけよ。

N = 200
0 <= x_i, y_i <= 500

B. ファーマーXの収穫計画

N*Nの区画の庭があり、i行j列目の区画にA_ijの品質の野菜がある。
各区画からは1度だけ野菜を収穫できる。

次の操作をX回実行できるとき、収穫する野菜の品質の合計値をできるだけ大きくなるように操作の計画を立てよ。

• 手入れ：選んだ区画の品質を1増やす。収穫済みなら何もしない
• 収穫：選んだ区画とその周辺の条件を満たす野菜を収穫する
  • 選んだ区画の野菜が品質Kのとき、まだ収穫されていない隣接する品質がKの野菜をまとめて収穫できる
  • ただし、まとめて収穫する野菜の数がK個以上でないと収穫できない。K個未満なら何もしない

N = 50
M = 2500
1 <= A_ij <= 9

最終的に提出したアプローチ

最終提出の解(input_1.txt)

rcohalf3a

rcohalf3b

• A問題
  • 点swapの焼きなまし
• B問題
  • 収穫を目指す品質をxとして、品質y ( < x )のものをxまで育てることを考える
  • 上記をやったとして、できるだけ多く収穫できるものからgreedyに取る
  • xを9から1まで、yはいくつか探索して、最終的に良いスコアのものを返す

時系列での振り返り

進め方の方針

• A問題1時間、B問題1時間を使う
• 残り2時間はA,Bの進捗具合で決める

開始～1時間

• 問題を読む
• 焼きなましが有効そうなのは見てわかるが、TLEが2秒で十分探索できるか不安
• とりあえず組んでみてどの程度スコア行くか見てみる
• 近傍はとりあえず2点swap、細かい高速化はあとで
• そんなに悪くなさそう？
• 一旦提出

1時間～2時間

• 問題を読む
• 方針が難しそうなので、greedy解をとりあえず考えてみる(以下考えてたアイデア)
  • 3x3枠とかで全部9にするとか？
  • 区画をすべて1本の線でたどるようなものを作ってどうとるのが最適化考える？
  • グラフで考えてクラスカルっぽくとることはできないか？
• 9をできるだけ取りたいが、コストが小さくとるために7とか8を育てて9にできるならうれしい
• いったん7と8を9に育てたとしてどの程度の塊ができるか見てみる
• 結構塊ができてる
• 結局全部を収穫するのは無理なので、ある数値以上を収穫したい品質まで育てて、取れるものだけ取る、方針でいくことにする

2時間～3時間

• Bの進捗がまずいのでBにいったん1時間使うことにする
• とりあえず適当に組む
• 品質9で収穫するのに7以上を育てたほうがいいのか、6以上を育てたほうがいいのかなど、細かく考えるとうまい実装を考えないといけなそう
• とはいえ、適当にやってもそんなに悪くない解にいけそうなので、いったん収穫したい品質ごとに独立に計算するように実装
• 一旦提出

3時間～3時間半

• 提出してみると全然時間を使っていない
• 上記のパラメータをいろいろ調べてみるのはありかも
• 実装を変えようと思ったけど、時間が厳しいので、途中でやめて簡単にできるところだけにしようと方針転換
• 下限だけいくつか変えてみるのを試してみるとちょっと良くなりそう
• B再提出

3時間半～終了

• Aの1位のスコアがヤバいことになってる
  • 逆算してみると平均分散が10を切っているよう
• 近傍？チューニング？バグ？そもそも別方針？などテンパりつつどうするか考える
• 近傍をいじるのはやや大変だと思うので、とりあえず時間を延ばして実行して温度調整で様子を見る
• あんまり上位を狙えるものではない
• 近傍は2点swapだと4辺変化してしまうので、普通に2辺swapにするだけでやや良くなるだろうけど、どんなもんか
• 別方針としては、あんまり大きくない辺のみを使って計算することで無駄な辺を考えなくて済むようになる？
• 辺を禁止する方はすぐできそうだしやってみる
• うまくいかなった
• 残り10分で2辺swapに書き換えられるか
• あー間に合わないー
• 終了

反省

• 焼きなましは近傍が大切というのは何度も経験してたはずなのに適当に組んでしまったのはいけなかった
• 結局2optにして分散をO(1)計算にするだけで330万点ぐらいがでてしまった
  • 提出スコアは47万点
  • そもそも2optの実装がうまい方法を自力で出せなかったので時間内に実装できても140万点ぐらいだった模様
• 近傍は小さいのを最初から選択すべき
  • 今回だと3optみたいなやや重でもよい近傍を選べるなら有効だったよう
  • また、今回みたいなのは、辺スワップはreverse操作があって重いので、undo操作ではなく、スコア計算を先にしてundoしないとわかってからreverse操作をするような実装にすべき

• Bの方は他の人を見てもそんなに大筋は外していない方針だったのでよかった
• 「コスパが悪いものを取らない」はすぐに入れられた要素だったのに入れられてなかったのは悪かった

参考

第3回 RCO日本橋ハーフマラソン 予選 - Togetter

みんなのプロコン2019 D. Ears

問題

数直線上のある整数点から自由に左右の整数点に移動し、どこかの整数点で終わるような行動をする。
このとき、整数iについて、i-0.5の地点を通過したら、i番目の位置に石を1つ置く。

目標となるi番目の石の数A_iが与えられたとき、上記の行動を行った後で、目標の石の数にするために石を追加または除去することができる。
追加または除去する石の個数が最小となるように行動を行った時の、追加または除去する石の総数を答えよ。

制約

• 0 <= A_i <= 10^9, (1 <= i <= 2 * 10^5)

解法

行動を行った後の石の形には法則性があり、
【0個】【0でない偶数個】【奇数個】【0でない偶数個】【0個】
のようなゾーンにわかれる(ゾーンがない場合もある)。

dp[i][j] := i番目がゾーンj(上記)だった場合の最小の追加または削除の回数
として、更新すればよい。

解法2

(コンテスト中考えていた方向性の解法で、一応通ったのでメモしておく)

行動を、ある整数iに注目すると、「左から入って右にぬける」「右から入って右にぬける」「左から入って左に抜ける」「右から入って左に抜ける」ような4パターンがあることがわかる。

ここで、右にぬけるようなパターンについてだけ考えると、i番目の地点で右に抜けるようなパターンの最小コストは、
dp1[i][0] := i番目で右から入り、0～i番目のどこかを通って、i番目で右にぬけた場合の最小コスト
dp1[i][1] := 0～i番目のどこかで入り、i番目で右にぬけた場合の最小コスト
を更新すれば、求められる。
(更新は、i-1までのdpの値から更新する場合とi-1までをすべて捨てて更新する場合を考える。A_i=0となる場合のコストに注意)

同様に、逆方向からdpすれば左にぬけるようなパターンについても同様に最小コストが求めらえる。(これをdp2とする)

あとは、ある地点iを境に左側を通った時の最小コストdp1[i][x]と右側を通った時の最小コストdp2[i][y]の組み合わせで最小となるなるものを見つければ、求められる。(dp2は通る向きを逆向きで考えれば等価)

その他

解法2の方の類題
D - 建物

ABC117 D. XXOR

問題

N個の非負整数A_iと、非負整数Kが与えられる。
ここで、f(X) = Σ (X xor A_i) (0 <= X <= K)という関数fを定義する。
この関数fの最大値を求めよ。

制約

• 1 <= N <= 10^5
• 0 <= K <= 10^12
• 0 <= A_i <= 10^12

解法

関数fはビットごとに0にするか1にするかで関数の値を独立に求められるので、雰囲気、上から貪欲に求められそうに見える。
しかしこれは普通に嘘で、貪欲が適用できる場合というのは「選択しなかった場合の最終スコアが、選択した場合の最終スコアを超えない」こと(それを証明できること)が必要。
(今回の場合、Nが大きいケースなどで、下位ビットの方で大きい値が加算される可能性がある)

なので、ちゃんと(全)探索を考える。

今、i bit目を考えているとする。
i bit目を0にするか1にするかが選べるが、Kを超えてはいけないので、「そこまで決めたビットの値+(1< K」ならば必ず0にしなければならない。そして、次のbitを同様に探索すればよい。

逆に0でも1でも選べる場合、0にしたらそれ以降のビットはどう選んでもKを超えないので、下位のすべてのbitでスコアが高くなる方のビットを貪欲に選んでよい。
1にした場合は、次のbitを同様に探索すればよい。

実装は、

• どこのビットを処理しているか: i
• そこまで決めたビットの値: X'
• そこまで決めたビットの分だけの関数のスコア: F'

を持ちながら再帰すればよい。

NIKKEI Programming Contest 2019予選 C. Different Strokes

問題

1～Nまで番号が付いたN皿の料理がある。
高橋くんがi番の料理を食べたときはA_iだけ幸福度が増し、青木さんがi番目の料理を食べたときにはB_iだけ幸福度が増す。
高橋くんから、交互に、2人とも「最終的に自分が得る幸福度の総和」-「最終的に相手が得る幸福度の総和」が最大化するように料理を選ぶ。
「最終的に高橋くんが得る幸福度の総和」-「最終的に青木さんが得る幸福度の総和」はいくつになるか。

制約

• 1 <= N <= 10^5
• 1<= A_i, B_i <= 10^9

解法

求めたい答えを数式で書いて変形するアプローチを考える。

高橋くんが取る皿の集合をX、青木さんの取る皿の集合をYとすると、
max( Σ_X A_i - Σ_Y B_i )
となる。
このままでは、XとYによって決まる変数だが、
max( Σ_X A_i + (Σ_X B_i - Σ_X B_i) - Σ_Y B_i )
= max( Σ_X (A_i + B_i) - (Σ_X B_i + Σ_Y B_i) )
= max( Σ_X (A_i + B_i) - Σ_すべて B_i )
= max( Σ_X (A_i + B_i) ) - Σ_すべて B_i
とすると、Yを消去することができる。

式の通り、A_i + B_i の和が最大になるようにXを選べばいいので、和でソートして交互に取っていけばよい。

ARC067 E. Grouping

問題

1からNまで番号がついたN人がいる。

• どのグループも、そのグループに含まれる人数がA人以上B人以下
• i人のグループの数をF_iとしたとき、F_iは0またはC以上D以下

このようなグループ分けが何通りあり得るかmod 10^9+7で求めよ。

制約

• 1 <= N <= 10^3
• 1 <= A <= B <= N
• 1 <= C <= D <= N

解法

解説、解説放送の方法。

問題がややイメージしにくいので、具体事例を考えてみる。
例えば、「(1),(2),(5),(3,4),(6,7)」のようなグループ分けだった場合は、

グループ内の人数	グループの個数
0人	0グループ
1人	3グループ
2人	2グループ
3人	0グループ

のようになっている。
A,Bは表左の人数に関する条件、CDは表右のグループ数に関する条件を表しており、条件を満たすならこのグループ分けは1カウントに数え上げられる。

数え上げなのでdpを考えてみると、「グループ内の人数」と「それまでの確定した人数」を状態にした以下のようなdpが考えられる。

dp[i][j] := i人以下のグループのみでグループを作ったとして、その合計人数がj人であるようなグループ分けの通り数

漸化式を考えると、i-1までが求められていたとして、i人グループを作ることを考えると、グループをx個作る場合は、

dp[i][j] = Σ_x f(i,j,x) * dp[i-1][j-i*x]

ここでf(i,j,x)は「残っている人で、i人グループをx個作る場合のグループ分けの数」。

これはiとjとxでO(N^3)っぽく見えるが、xはグループの個数で、iが大きくなるほど作れるグループ数は少なくなり、xはj/i個までしか作れないので、これはO(N^2 logN)となる。
( O(N + N/2 + N/3 + ...) = O(N logN) )
したがって、f()が十分に高速に求められれば間に合う。

f(i,j,k)を求める。
N人中すでに(j-i*x)人はグループになっているので、残りの(N-j+i*x)人からi人グループをx個作ることになる。
各人は番号がついていて区別できるので、並びも考慮するイメージで、「(N-j+i*x)人からi*x人を並べる通り数 (N-j+i*x)_P_(i*x)」から、重複分の「グループ内での並びは関係ない分 ( i! )^x」と「グループ自体の並びも関係ない分 x!」を割ってあげた以下の式になる。

f(i,j,k) = (N-j+i*x)_P_(i*x) / { ( i! )^x * x! } = (N-j+i*x) ! / { (N-j)! * (i!)^k * x! }

MOD階乗、MOD累乗、MOD逆元でこれを求めてあげればよい。

その他

ベル数 - Wikipedia

A,B,C,Dの条件がない場合は「ベル数」と呼ばれる。

AGC029 B. Powers of two

問題

N個のボールがあり、i番目のボールには正の整数A_iが書かれている。
このとき、2つのボールを取り出してペアを作り、その数字の和が2ベキ(2^t)になっている場合、そのペアを取り除くことができる。
最大で何回ペアを取り除くことができるか？

制約

• 1 <= N <= 2 * 10^5
• 1 <= A_i <= 10^9

解法

大きい数字の方から注目すると、自身よりも小さい数字でペアを作ることになる場合、2ベキになる数字は一意に決まる(自身より大きい一番小さい2ベキになる)。

ある数字xについて、その数字以下のペアになれる数字yが存在する場合、「xを除いた集合」で「xとyを除いた集合」よりもペアを多く作れないならxとyでペアを作っておいたほうがよいが、ペア数は同数か少なくなるしかないので、結局ペアを作っておいたほうが良い。
したがって、greedyに、大きい方の数字からペアを作れたら取り除く、を繰り返していけば求められる。

c++の場合はmultisetで検索、削除などを簡単に実装できる。

  multiset<int> m;
  rep(i, N) {
    int a;
    cin >> a;
    m.insert(a);
  }
 
  int ret = 0;
 
  while (!m.empty()) {
    int x = *(m.rbegin()); //大きい数字から処理
    m.erase(m.find(x)); //(m.erase(x)にしてしまうと値xがすべて消えてしまう)
 
    ll p = 1;
    while (p <= x) p *= 2;
    int y = p - x; //ペアになれる数字は一意に決まる
 
    if (m.find(y) != m.end()) {
      m.erase(m.find(y));
      ret++;
    }
  }
 
  cout << ret << endl;

解法2

上記の解法の考察がやや自分の感覚では自身なかったので、もうちょっと無駄なことを本番では考えてた。

同じ数字のボールをまとめ上げた(数字, 個数)で考える。これをノードとみなす。
大きい数字のペアをその数字より小さい数字で作る場合は一意に決まることから、大きい数字のノードから小さい数字へのノードに辺を貼ると、これは森になっている。

ある木について考えると、ペアをできるだけ作ることを考えると、葉ノード側からできるだけペアを作るのがいいので、葉ノード側から処理してペアを作る。
最後に、2ベキな数字で残っているボールがある場合、同じ数字でペアが作れるので、それを加えれば答えが求められる。

反省

勉強不足と考察不足。ついでに実装の仕方がダメダメだった。
本番は、2ベキなボールは同じ値でしかペアになれない(嘘)、と思い違いして最初にコーナーケース的処理を入れてしてしまっていて通せなかった。。
すぐに反例が思いつくのに、間違っていないと思っている考察に対して疑うのは難しい・・・

greedy法の証明は典型らしいかも？(帰納的に考える)
「今、操作xをしなかった場合、残りの部分で操作xした場合よりスコアが高くならないならば、今、操作xをしたほうがよい」