Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

ListViewにButtonとか入れてるけどOnItemClickListenerが動かない

Androidアプリの開発で、ListViewにCheckBoxやButtonを入れて、OnItemClickListenerを設定したが働かないという問題にであいました。 結構な既出問題でしたが、日本語情報ではなかなか十全な記事がなかったです。そして、自分のFocus、TouchModeの理解などもかねてまとめることにしました。

続きを読む

ABC194 - E - Mex Min

https://atcoder.jp/contests/abc194/tasks/abc194_e

問題概要

$ mex(a, b, c\cdots) $は$ a, b, c\cdots $のうちに含まれていない、最小の0以上の整数とする。

数列$ {A _ i} $と$ M $が与えられる。すべての$ A _ i $の連続した$ M $個の部分について、それぞれmexを考える。この時、$ |A| - M + 1 $個のmexの最小値を求めよ。

制約:$ 1 \leq |A| < M < 1.5 \times 10 ^ {6}, 0 \leq A _ i \leq |A| $

考え方

  1. 連続M個のmexを調べたいので、1つだけ見て、そこから首尾だけ変更して効率よく計算でいないか?
  2. しかし、これはなかなかに厳しい。mexを馬鹿正直に計算するとどうしても$ O(|A _ i| \log M) $ぐらい最悪かかってしまう。巧妙にvectorで数の続いてる区間をもって、削除と挿入による差分更新も可能ではあるが、複数個に対応させようとすると断然厳しい実装量となる。
  3. 常套テク発想を逆転させる。 $ 0 \leq A _ I \leq |A| $を利用すると、たかだか答えの候補は$ A $通りしかないと抑えられる。そして、答えとして満たすかは小さい順番に試せばよさそう。
  4. 具体的にはこうする。$ x $が最終的なmexの最小値だとすると、すべての$ M $個連続する区間のmexは当然$ x $以上。mexが$ x $以上である条件は実は簡単に求められるので、あとは少し効率化すればAC。

考察

mex演算

Grundy数などでも使われる0以上の整数の集合に対するmex演算は、以下のようなstd::setを用いて計算できる。

std::set<int> S;//Sにmexを計算したい要素が入ってる。
int ans = 0;
while(S.count(ans) != 0){
    //Sにansが含まれていたら、ans + 1がSにまたあるかを確かめる。 なくなったら終わり。
    ans++;
}
//ansがmexとなる。

これは、Sの中の要素の最大を$ X $とすると、$ O(X \log |S|) $の計算量が最悪かかる。(Grundy数の場合は、$ X $は一般的に大きくなることが少なく、なったとしても均してみた時は大丈夫) 今回の場合、愚直にシミュレーションは不可能だ。

差分更新

では、長さ$ M $の連続列であることを利用して、常套テクの最初と最後だけを変更しての差分更新を考えてみる。しかし、先ほどのmexのアルゴリズムのままではこれは効率的には行えない。ほとんど変わってなくても、効率的に再利用が難しい。

一つの方針としては、std::setに入れるのではなく、std::vector<pair<int, int>>として、 $$ [連続の始まり, 連続の終わり] $$ の形で持つことである。例えば、$ |S| = {1, 2, 4, 5, 6, 9, 34} $なら、{{1, 2}, {4, 6}, {9}, {34}}として持ち、ここから要素を1つ削除 and 挿入は 二分探索で該当する場所を探し当てて、行うことである。

しかし、この方法では同じ要素が複数ある場合の適用に難儀してしまう。一応丁寧にやれば可能ではあると思うが、実装量は恐ろしく多い。

ここでこの方針を置いておき、別方針で探るべきだ。

答えを仮定して

別方針として考えられるのは、答えはたかだか$ |A| $通りということだ。仮に答えが$ x $だとして、それが条件を満たすようにチェックできれば、$ x $を小さい順に試しておき初めて条件を満たしたものが答えでよい。(今回の求める連続列のmexの最小値はこの単調性がある)これは$ O(|A|) $のループしか回らない。(しかし、これで行くならばループの中は限りなく$ O(1) $出なければ間に合うことは難しいだろう)

仮に答えが$ x $であるとして、それが真であるには、次の条件を満たす必要がある。

  • どの長さ$ M $の連続列でも、mexが$ x $以上。

mexが$ x - 1 $より大きいとわかっているとき、$ x $がmexの最小値の候補としてあり得るかは、すべての$ A $の中の$ x $を見て、(先頭と後尾と)お互いと、$ M $個以上だけ間を空けていたら$ x $はmexの最小値となる。(そこの$ M $個以上の連続列では確実に$ x $は含まれていないが、$ x - 1 $以下は含まれているので、そこからとればmexの最小値は明らかに$ x $)

これは、すべての$ A[] $の値ごとに、要素としてどこにあるかをメモしておけば、$ x $が小さい順に確認するときに効率的に見ることができる。 全体で計算量はたかだか$ O(|A|) $となる。

ACソースコード

C++

最後に

青天、堕つ。いざ、昇らんや。

ABC189 - F - Sugoroku2

https://atcoder.jp/contests/abc189/tasks/abc189_f

概要

マス目が0からNまであるすごろくが存在していて、あなたは1からMまですべての数が等確率で出るルーレットを持っている。あなたは最初にマス0にいて、マス目Nを目指して、以下のように進む。

  • マス目$ i $にいるとき、ルーレットで$ j $が出た時にはマス目$ i + j $へ移動する。移動先の$ i + j $が$ N $を超えた場合は、ゴールしたと見なす。

そして、このすごろくにはK個の初めに戻るマス$ {A[i]} $があり、そこにたどり着いてしまうとマス0に戻されてしまう。

この時、ゴールするまでのルーレットの数の期待値はいくつでしょう?

制約:$ 1 \leq N, M \leq 10 ^ 5, 0 \leq K \leq 10, 0 < A[1] < \dots < A[N] < N $

続きを読む

ABC191 - F - GCD or MIN

https://atcoder.jp/contests/abc191/tasks/abc191_f

概要

黒板にN個の数字${A[i]}$が書かれている。以下の操作をN-1回行って、最後に残った数は何通りあるでしょう?

  • 2つの数字$a, b$を選び、それらを黒板から消す。代わりに、$\min(a, b)$もしくは、$\gcd(a, b)$のいずれか一方を黒板に書き込む。

制約:$1 \leq N \leq 2000, 1 \leq A[i] \leq 109$

考え方

  1. 少し考えると、残る数字は$\min({A[i]})$より小さくないといけない。(そうでなければ絶対に最後まで残せない)
  2. また、残る数字は明らかに$A[i]$の要素のうちのいくつかの$\gcd$である。(gcdかminなので)
  3. よって、$\gcd(A[i], A[j], \cdots) \leq \min(A[i])$となる$\gcd$をすべて列挙したい。
  4. 2つペアでgcd取ればすべて行けるんじゃない?->嘘です。
  5. $dp[i] := iが作れるか?$のDPをするのは時間計算量が足りない。
  6. 発想の転換をし、$x$の倍数となるもののgcdはいくつか?(これが$x$と等しければ$x$をgcdとして残せるので)を数えると、これは時間内に数えられそう->AC。

考察

まず、$\min(A[i])$より大きい値を残すのは不可能である。なぜならば、常にmin方向(gcdも数字としては小さくなる)に数が選ばれるからである。そして、操作は

  1. いくつかの要素を選んでそのgcdを取る。この時、その値たちのgcdは$\min(A[i])$以下である。
  2. 残ったすべての操作についてminを取る。

の操作で言い換えられるとわかる(残る数字ならば必ずこの手順で黒板に残せる)。

では問題は、$A[i]$からいくつかの値を選んで、作れるgcdを列挙する方法である。

試し方1(間違い)

$dp[x] := xがgcdとなれるか?$のbool値DPを行う。遷移式は、(dp[x]がtrueなら)

$$ dp[\gcd(x, A[i])] = true $$

この愚直な遷移式では、すべての$A[i]$の約数の種類を$X$として、$O(NX \log X)$ほどの計算量で押さえられる。

しかし、ここで$X$はとても大きくなりうるのだ。とても雑な$A[i]$の構成法でこれが大きくなると示せる。

A[0] = 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12
A[1] = 13 * 14 * 15 * 16 * 17 * 18
A[2] = 19 * 20 * 21 * 22 * 23 * 24
...

このように構成すると、$N$個目の要素$4197$まで掛けることとなり、これらの間でも更にかけていくことができるので $X$は明らかに膨大になり、時間内には間に合わないとわかるだろう。

試し方2(間違い)

先ほどはすべてを試そうとしたがゆえに、時間計算量が間に合わなくなった。では、すべてのありうる答えの候補は、2つペアのgcdから求められる、と考えて$O(N2)$で試せばいいのではないか?

しかしこれはgcd系の問題でよく出る間違った命題である。 反例として、以下のようなケースがある。

$$ a = 2 \times 3 = 6, b = 3 \times 5 = 15, c = 5 \times 2 = 10 \ \gcd(a, b) = 3, \gcd(b, c) = 5, \gcd(c, a) = 2, \gcd(a, b, c) = 1 $$

このような反例で、2つペアのgcdがすべてのgcdをカバーできるわけではないとわかる。 集合内の部分集合の要素によるgcdの列挙は、○○個のペアだけで~とはならないのだ。

正しいアプローチ

試し方1では、すべての約数の候補を持っていて、かつ毎回の更新でそれらをすべて見ることから計算量が爆発した。 ここで、DPの対象の入れ替え?みたいなことをしてみる。

$ dp[x] := xを約数に持つAの要素すべての\gcd $

このようにすることで、$dp[x]$の計算に関わる$A[i]$の数を大きく減らすことができる。 もともとのDP遷移の場合、共通因数をそもそも持たない多くの遷移先はgcd == 1となっていた。この無駄を省くために、$x$を因数に持つ$A[i]$のみが$dp[x]$の遷移に関わるというアルゴリズム設計をするとうまくいく。

このアプローチの計算量はどうなるのだろうか。$109$以下の1つの数で最も約数の個数が多いのは$1344=d$個であるとわかっているので、$N$個の要素についてそれぞれ約数を全部見ても、たかだか$O(Nd)$で押さえられる。そして、mapを使用することによって、最終的に$O(Nd \log \max(A[i]))$と最悪計算量を抑えられる。(約数列挙部分は$o(N \sqrt{\max(A[i])})$)

$d$の具体的な値は知らずとも、約数であるので大体$O(\sqrt{N})$だなあと見当をつけることができれば、これが間に合うとわかる。

ACソースコード

C++

最後に

40分かけたのに解けなかったのは本当に反省。GCDは2つペアで見ちゃいけない(警告)

ARC112 - C - DFS Game

https://atcoder.jp/contests/arc112/tasks/arc112_c

概要

サイズがNの根付き木が与えられる。木の根は頂点1。 AliceとBobはこの木でゲームをする。

木の各頂点には最初はすべてコインが1枚ずつ置かれている。最初に駒を用意し、頂点1(根)に置く。手番はAliceから始まり、AliceとBobが交互に行動する。 2人はともに以下の条件で動く。

  • 駒が今置かれている頂点にコインがあるなら、それを取って次の人に手番を回す。
  • コインがない時、子の頂点のうちのどれかにコインがある場合は、その子のどれかに駒を動かす。そして次の人に手番を回す。
  • コインがなく、すべての子の頂点にもコインがない場合は、親の頂点に駒を動かす。そして次の人に手番を回す。
  • 根にいるとき、子のコインがすべてなくなったらゲームは終わり。
  • 自分の獲得コインを最大化するように動く。

この時、Aliceの獲得するコインは何枚?

制約:$ 1 \leq N \leq 10 ^ 5 $

考え方

  1. ゲーム問題なのでまず例をトレースしてみる。一本道はAliceが全部とるetc
  2. 木構造なので、自分の子が及ぼす影響で自分自身を計算でき、自分の親、爺、etc以外の頂点には影響を及ぼさない->木DPをいい感じに求めればOK。
  3. 実験やサンプル3を見ると、子を巡って、また親の頂点に戻るときに、コントロール権が移ることがある。->コントロール権のやりとりが大事そう!
  4. 冷静に考察して、詰めていくと子をめぐるときのコントロール権の変遷の有無で場合分けして、計算すれば$ O(n \log n) $で求められる。->AC

考察

どのよう大筋で解くべきか

この問題は問題名の通り、DFSをするかのように駒は動くとわかる。この時、明らかに親頂点での計算結果は子頂点にのみ依存することから、木DPをすることが大筋となる。

動き方

すべての葉(子を持たない頂点)を、葉から見た初めての分かれ道までの距離を見てみる。例えば、

(1) -- (2) --- (3) -- (4) -- (5) -- (6)
        |
        ------ (7) -- (8) -- (9)

の頂点(6)は、枝分かれ(2)までの距離は4であり、頂点(9)は、枝分かれまでの距離が3である。

最初に、Bob(後手)が頂点(6)の方を選択すると、頂点(6)から(2)へ戻るときは、Alice-Bob-Alice-Bobであり、分かれ道を選択した時はBobが行先を選んでいたが、この時点での選択権はAliceに渡ることになる。これは、最初の枝分かれまでの距離が偶数の場合である。

最初に、Bob(後手)が頂点(9)の方を選択すると、頂点(9)から(2)へ戻るときは、Alice-Bob-Aliceであり、分かれ道を選択した時はBobが行先を選んでいたが、この時点でも選択権は相変わらずBobにある。これは、最初の枝分かれまでの距離が奇数の場合である。

すべての枝分かれの先は個のように単純に葉につながってる構造ではないものの、ひとまずこれで葉に直結する分かれ道に関しての利得やコントロール権の変遷を計算できた。葉に直結する枝分かれで、コントロール権を持つ人は、

  • できるならば相手にコントロール権を押し付けたい(自分がコインをもらえるので)
  • コントロール権を押し漬けられるような子が複数個あるなら、相手が得られるコインの数(つまり枝分かれから葉までの距離)が最小になるものから選ぶ
  • コントロール権が変わる枝分かれがすべてなくなったとき、コントロール権がある人が残りのコントロール権が変わらない子をめぐることになり、結果的にこの時点でコントロールできない人は残りの子のコインをすべてもらえることになる。

これは、葉に直結する分かれ道の話だったが、一般の分かれ道にもこの話を帰着させよう。同様に、子へ行くことによるコントロール権の移り変わりがあるかに着目して、先ほどの考察を広げる。

以下のようにDPテーブルを定める。

dp[i] := 頂点iを始めて訪れた時、双方適切に行動して、コントロール権を持った人の得られるコイン-持ってない人の得られるコイン

お互いにコイン数を最大化したいので、これはどの方にとっても、獲得量の差の最大化でもある。

これを使って、先ほどの葉に直結する場合例では$ dp[3] = -4, dp[7] = -3 $である。(選ぶと相手が獲得し、自分が獲得できないため)

この一般化した時のコントロール権にまつわるアルゴリズムは以下である。

  • コントロール権の変化がある子$ x $の場合、$ dp[x] $が大きい順(コントロール権がある人から見て、相手より一杯とれる順)に使う。
  • コントロール権の変化がない子の場合、$ dp[x] > 0 $なら最初にコントロール権がある人が全部使う。(使ってもコントロール権が向こうに行かないので、全部取るのが最適)
  • コントロール権の変化がない子で、$ dp[i] \leq 0 $の場合、使っても行き損である。(相手が得するのみならず、コントロール権も押し付けられない)これは最後の最後までAliceもBobも取りたくない。

このことから、子の$ dp[x], dp[y], \cdots $がそろった時に、親の$ dp[a] $(頂点$ a $を初めて訪れた時に、コントロール権を持つ人の獲得コイン-持たない人の獲得コイン)は次のように計算すればよい。

  • コントロール権が変わらない子$ x $に関して、$ dp[x] > 0 $の$ dp[x] $をすべて$ dp[a] $に加算。
  • コントロール権が変わる子$ x $に関して、$ dp[x] $が小さい順に並べ、1, 3, 5, ...番目は加算(自分がとるため)、2, 4, 6, ...番目は減算(相手がとるため)する。
  • 最後に、コントロール権を持つ人がコントロール権不変の$ dp[x] \leq 0 $の子をすべて取る。

これをすべての分かれ道について、再帰的に計算することでこの問題は解くことができた。

計算量についてだが、木DPなのですべての頂点を1度は見ることなり、$O(n)$である。また、分かれ道では以上のアルゴリズムを行うためにソートをする必要があるが、この部分ではたかだか$O(n \log n)$なので、解くことができた。

ACソースコード

C++ いろいろわかりやすい?コメントがついてる。ちょっと冗長。

最後に

コンテスト中に正しい考察してたのに詰め切ることができなかった。お前実装力足りてたらすぐに青上位だぞ精進しろ。

ABC191 - D - Circle Lattice Points

https://atcoder.jp/contests/abc191/tasks/abc191_d

概要

座標平面上で、$ (X, Y) $中心で半径が$ R $の円の内部や辺上に、何個の格子点(座標がすべて整数の点)がある?

制約:$ 0 \leq |X|, |Y|, R \leq 10 ^ 5 $。$ X, Y $は小数点以下4桁まで与えられる

考え方

  1. 円のうち、y座標で見れば最大でも$ O(Y) $通りのy座標の点しか答えの候補にならない。y座標の値さえ決まれば、円内に格子点となれる点の数は簡単に二次方程式を解くことで数えられる。
  2. doubleで実装。->WA doubleでは精度が足りない。これを補う工夫が必要。
  3. long long なら$ 10 ^ 18 $の精度で計算できる。今回はこれならギリギリいけそう。
  4. 入力をlong longに直して(ここ罠あり)、自前でsqrtを書く。
  5. AC!

考察

この問題の解法の大筋は1通りであるが、精度を解決するためには2通りのやり方がある。

  1. $ 10 ^ 4 $倍して、long longで計算する。
  2. long double で精度の問題を解決し、辺上ギリギリの点を数えるために$ R $にEPSを足すことで考える。

アルゴリズム

この問題を解くアルゴリズム自体は平易である。格子点の数を数えるやり方として、「円の内部や辺上に含まれている格子点のy座標はたかだか$ O(Y) $通りしかない。」を利用して、y座標を固定した時に、円の内部や辺上にある格子点は、円の式$ (x - X) ^ 2 + (y - Y) ^ 2 = R ^ 2 $から二次方程式を解けば求まるとわかる。

誤差の問題を考えなければ、√の計算に$ O(\log |Y|) $かかると考えられるので、全体で$ O(|Y| \log |Y|) $程度の計算量で収まる。

精度の問題

しかし、ここで考えなければいけないのはdoubleの精度で足りるか?である。 doubleは倍精度浮動小数点であり、これの計算機イプシロン(doubleで表せる1以上で最小の数と1の差)は$ 2.220 \times 10 ^ {-16} $である。

今回の場合、ルートで最大$ (10 ^ 5) ^ 2 - (10 ^ {-4} ^ 2) $の計算をすることになる。この時、要求される精度は$ 10 ^ 18 $レベルであり、明らかにdoubleの計算機イプシロンを超えている。 つまり、doubleによる計算では今回の場合精度が足りないのである(実際多くの人はここで落ちたがゆえに青上位の難易度になっている)

精度問題の回避手段(方法1)

では、どのように精度問題を回避するのか?ここで着目したいのは、doubleの分解能?は$ 2.220 \times 10 ^ {-16} $レベルであるが、long long は$ 9.0 \times 10 ^ {18} $レベルの精度の演算ができる所である。つまり、64bit整数として計算してあげれば精度面ではなんとか(ギリギリだが)なりそうということだ。

というわけで、まず入力の$ X, Y, R $をすべて$ 10 ^ 4 $倍して、整数としよう。この時、実は以下のように書くとWAになる。

long long mX = X * 10000.0;

ここでも多くの人がつまずいた。そのまま代入による切り捨てや、ceil()は、負の数ではうまく働かなかったり、$ X \times 10000.0 $の値自体を床関数で計算しても綺麗に求まらないことになる。

実際に、以下の場合でエラーが生じる。

99999.9999 * 10000.0
99999.9999は倍精度浮動小数点で表すと、1.525878904724121 * 2^{16}であり、
(Wolfram Alphaで計算すると)、999999998.999...となってしまう。

このような状況では、roundll()で四捨五入するべきである。 そもそも浮動小数点では多くの値は循環小数となり、綺麗に表せない。個の誤差は普段とても小さく、(coutで出力すれば)見た目上は綺麗に表せているものの、計算を重ねることによって誤差が蓄積して最終的な値はずれてしまう現象が起きる。この時、誤差が小さいうちに毎回roundなどの処置を考えるべきである

long long mX = round(X * 10000.00);

二乗根の計算(方法1)

STLのsqrtは、doubleなどの浮動小数点仕様である。この問題では、doubleは精度不足から、std::sqrtを用いることができない。

そこで、$ \sqrt{x} $は単調増加であることを利用して、二分探索で求めることができる。具体的には以下の通りである。

ll my_sqrt(ll x) {
    ll ok = 0, ng = 2 * 1e9;
    while (ng - ok > 1) {
        ll mid = (ok + ng) / 2;
        if (mid * mid <= x)
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}

long doubleで精度問題を対処(方法2)

long double(4倍精度浮動小数点)の計算機イプシロンは$ 1.926 \times 10 ^ {-34} $であり、今回の計算の場合ではこれで精度が事足りるとわかる。

この時、計算幾何によるあるテクニックとして、辺上にあるものの数え上げは、わずかに大きい外形の内部で考える、がある。 例えば、今回の場合は半径$ R $ではなく、ある十分小さな値$ \epsilon $を用意して、$ R + \epsilon $が半径の円の内部を代わりに考える。 この操作を施せば、辺上にあるものは安全に数え上げることができる。

今回の場合、一番精度が危ういようなケースは以下の通り。

$$ X = 0, Y = 100000, R = 100000, x = 0.0001, y = 0 $$

この場合は、ギリギリ入ってないが、$ R $の代わりに$ (R + \epsilon) $を用いて、ギリギリ入ってしまう場合は、 $ 10 ^ {10} + 10 ^ {-8} = (10 ^ 5 + \epsilon) ^ 2 $であり、解くと$ \epsilon = 5.0 \times 10 ^ -{14} $となる。これを超えるとこのようなエラーが生じるので、 $ \epsilon < 4.0 \times 10 ^ {-14} $とするのが無難である。

このように、計算幾何での$ \epsilon $はこのように最悪ケースでエラーする限界を考えて決めるとわかりやすい。

ACソースコード

解法1

C++ 自前で10000倍にceilやroundを実装した。

解法2

C++ EPSを$ 10 ^ {-14} $にした。$ 4.0 \times 10 ^ {-14} $でも落ちるみたいなので、安全を取ろう。

最後に

コンピューターアーキテクチャや開発よりの所を問われた。こういうところは実務でも生きてくるので落としちゃダメだ。