2解法たとえば123456の場合、以下の最大値を求めれば良い。桁を'9'とする数値は、以下で求められる。求めよ解法1ボロノイ分割にとらわれかけたが、問題の条件からもっと単純に考えてよかった。玉を落とす範囲は無限と考えていいくらい大きいので、ボロノイ分割した時に他の点に囲われる点の確率は0に収束する。凸包を構成する頂点についてだけ考えればよい。凸包の各辺に垂直二等分線を引き、各凸包頂点を挟む垂直二等分線のなす角が360°に対して占める割合が、そのまま確率になる。厳密には原点に対してのズレがあるが、玉を落とす広大な範囲に比べれば無視できる。(以下の図で線分をわずかに平行移動したところで、面積の変化は誤差の範囲である)ただし、与えられた点が一直線上に並ぶ場合、最も端の2点が0.5ずつの確率になる。pythonでは、scipy.spatial.ConvexHullが使える。自力で凸包とかの実装しなくていい分、ライブラリが豊富なpython向きの解法。pts))))解法2解法1の中で適当に「誤差の範囲である」とか言ったが、本当に誤差が条件の範囲内に収まるかは検証が必要。解法2は、許容される誤差($10^{-5}$)から考えて十分な精度での全探索を行う。向きのベクトル成分が最大の点)必要な精度を担保するには、角度を許容誤差の2倍(20万)に分割して調べればよい。不安なら少し増やして25万くらいにする。いう演算は、pythonならnumpyでさくっとまとめて計算したいところだが、残念ながら全てを一度に持たせるとメモリが制限を超えてしまった。pts))))MLEになるなら適宜分割すればいいじゃない。pts))))もしくは、dtypeをサイズの少ないものに変更する。NumPyのデフォルトは64bit。この場合、減らしすぎるとそれはそれで計算誤差が発生するが、ひとまず32bitにしても大丈夫だった。16bitまで落とすとさすがにWAだった。パーツを敷き詰めるように考えると、AとBを同一に考えられるので考察が楽になる。vv端っこの部分の処理が肝。置ける枚数は変わらない。置ける枚数は変わらない。枚とし、残りの盤面に置けるか考える。個存在する(/は切り捨ての割り算)。盤面に$A,B$を1個ずつは置けないので普通は無理。共に奇数」の場合に限り、既に端に敷き詰めたタイルをずらすことで置けるケースがある。ように、4畳半の畳の敷き方をすればよい。最長共通部分列を最大化し、長さを求めよ解法いかにもなDP問題だけど、個人的にDP問題は何をやってるのかわかんなくなってくる。abcabcabcとする。cbacbacbaとなる。bcbabなどになる。bcbabは回文ではないが、同じ5文字でbcbcbという回文部分列が存在する。これは必ず存在すると言える。回文でない共通部分列bcbabを考える。それぞれが出現する位置は以下になる。T'この時、どこかですれ違うポイントがある。無い場合でも、端っこですれ違うと見做す。この場合、3番目のbですれ違う。部分列の1~2番目を取ってきて逆向けにくっつけたものも、$T,T'$の共通部分列として存在する。4~5番目をくっつけたものも同じ。これらは回文であり、いずれかは少なくとも元の部分文字列の長さ以上である。bなので、回文でない共通部分列があったとしても、その長さ以上の、回文である共通部分列が必ず存在する。問題の答えとしては長さを求めればよいので、回文部分列のみ考えてよいということになる。naoyaのはてなダイアリーしかし今回は、以下の条件の下で行うので、上記の方法では上手くいかない。回まで変更を加えてできる最長共通部分列の長さを求めるとよいらしい。この場合はこういった解法がいいのか、というのが全然理解できてないが、やってみたらなるほど上手くいく。