naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉700点問題 (ARC 082 E, 083 E, 085 E, 087 E, 090 E, 092 E, 094 F, 095 E, 102 E)

ARC埋めの秋がやってきたのでまたARCを埋めていきます。
(企業コンを除くともう700以上しか残ってない…)

11/10 (土)

ARC 082 E - ConvexScore

寝る前に問題読んで考えてたけど全く方針が立たない。そのうち寝落ち。

起きてから解説を読む

ある特定の(面積が正の)凸多角形(凸包)を成す頂点集合Xについて考えるんだけど

> {X|S=Sx}と{S∪t|t∈Ts}が集合として等しい

って辺りが全く理解できなくて躓きかけた。S=Sxな集合Xってただ1つではなくて、皮(輪郭)Sの部分だけ同じで中身が任意だから、皮以外の部分がk(=n-|S|)頂点あるならそれだけで2^k、すなわち2^n-|S|通りあるわけね。

輪郭に注目して、考えられるすべての凸多角形輪郭Sに関するこの2^n-|S|の総和を求めるのがこの問題なんだけど、

頂点集合の側から見ると、ある頂点集合Xはその凸包を考えることができて、輪郭に乗る頂点は上で考えたSのどれかに該当するので、上の総和で1回だけカウントされていて。
(面積が正の)凸包をなす頂点集合をすべて数え上げた結果は上の総和に等しくなるはず、という話。

はぁ…(その置き換えができないと解けない問題でした)

(面積が正の)凸包をなす頂点集合というのは、凸包の面積が0になる頂点集合をあらゆる部分集合の組み合わせ(2^N) から引いたものだというのは難しい話ではない。

で、凸包の面積が0になる頂点集合というのは、2個以下の頂点からなる集合(0個が1通り、1個がN通り、2個はNC2通り)と、3個以上だけど1直線上に並んでしまっている頂点からなる集合。(2個の組み合わせは1直線上の判定の側のカウントに入る)

一直線状に並ぶ頂点集合が何通りあるか数え上げるのが実装面でのポイント。
2頂点の組み合わせをNC2通り見てそれぞれの直線の式を立てていけばいいんだけど、問題は直線の正規化。
ax + by + c = 0 の a が (y=-cの形を除いて)できるだけ1になるようにしたんだけど
→WA
https://beta.atcoder.jp/contests/arc082/submissions/3584747

そこまでのロジックは合ってる(と思う)ので、正規化の部分だけ考える。

2投目: -(double)0 は -0.0 になるので (double)(-0) になるようにキャストの順番を変更 →WA (減らない)
https://beta.atcoder.jp/contests/arc082/submissions/3584787

3投目: a,b,cをdoubleではなく定数倍して丸めた整数値で扱ってみる。100万倍。→WA (2つ)
https://beta.atcoder.jp/contests/arc082/submissions/3584815

4投目: 1e7倍 →WA(1つ) おっ
https://beta.atcoder.jp/contests/arc082/submissions/3584824

5投目: 1e8倍 →AC
https://beta.atcoder.jp/contests/arc082/submissions/3584835

それでいいのかよという気がする

他のみんながどうしてるのか見てみる

ブログ等に上げてる人のやつを見ると、3点について同一直線上にあるかを整数演算で調べるのが定石っぽい。

2頂点(i,j)の全組み合わせに対し、他のすべての点(k≠i k≠j)について直線ij上にあるかを調べる(これは整数演算で可能)
複数の(i,j)の組み合わせが同じ直線上に乗るとダブってカウントされるので、ある点とある点が同一直線カウント済かをチェックする二次元テーブルを使っている。

kmjpさんと同様の解法

kmjpさんと同様の解法
a=y_j-y_i, b=x_i-x_j, c=-(a\cdot x_i+b\cdot y_i) を式 ax+by+c にあてはめて0判定するというやり方は個人的には分かりやすいし好感がもてる。同一直線上判定界のtouristだ。

kmjpさんと同様の解法(i<j<kで回してる)

kmjpさんと同様の解法(i<j<kで回してる)

11/11 (日)

ARC 083 E - Bichrome Tree

// 前にもそんな名前の問題埋めなかった?→〈ARC埋め〉AtCoder Regular Contest 093 E - Bichrome Spanning Tree

  • 頂点がvな部分木が条件を満たしているとき、白=X_v, 黒=α=任意の値(白黒は入れ替え可)
    • 便宜上これを (X_v, α) と書く。
  • 葉からナップサックしながら組んでいく。
    • 再帰でstack overflow死したくないのでtopological sort順の逆からDP
    • αを可能な限り小さくしながら葉から根へ上がりたい
    • 葉は無条件に (X_i, 0)
    • 頂点vの子供たちが [(α_1, β_1), (α_2, β_2), ...] のとき、
    • 最低でも\sum\min(α_i,β_i)にはなる。これがX_vを上回ってしまったら"IMPOSSIBLE"
    • [|α_1-β_1|, |α_2-β_2|, ...]X_vになるべく近づくようにナップサックする
    • 色は都合よく塗ればいい
    • 求めたいのはむしろ「入らなかった方の合計」α

計算は合うんだけど、sample case 4で必ずSEGVる
→N=1のとき空行が出来て、そこから0件のデータを読み込むみたいな処理が自分のライブラリでエラーを起こしている

1

0

→件数少ないしcinでいいわもう

→AC
https://beta.atcoder.jp/contests/arc083/submissions/3585854
まるまる1時間かかったけど自力で一発ACできた嬉しみ

解説を読む

同じ解法

11/12(月)

ARC 085 E - MUL

素数で包除で…いや2k,3kは壊さず6kは壊してみたいな時どうするよ
1〜100まで100ビットで2^{100}メビウス変換?
いや無理

フローで解ける?どう矢印引いたらいいんだこれ
なんか燃やす埋めるみたいな感じに落ちるのか

1ポモドーロ考えたところで解説をみる

はい燃やす埋めるー

  • Sから負の頂点に、正の頂点からTに|a_i|の辺を張る
  • n → kn に +∞ の辺を張る
  • で最小カット/最大フロー
  • Σ(正のa_i) - 最大フロー、が答え

前に診断人さんの燃やす埋めるスライドを見たときのコードをコピペして
long longにして
→AC
https://beta.atcoder.jp/contests/arc085/submissions/3589162

とりあえず通ったんだけど、いまいち理解できてないので咀嚼タイム。

kmjpさんの記事を読んだ

Project Selection Problemという枠組みで考えたほうが分かりやすいらしい。
これの7ページ目あたり。

kmjpさんのやつだと辺の張り方が(解説と)逆で

  • Sから正の頂点に、負の頂点からTに|a_i|の辺を張る
  • kn → n に +∞ の辺を張る

で組まれている。

  • 各頂点には生/死(ないし0/1)の状態がある
    • 頂点Sは常に生、頂点Tは常に死
  • (ある頂点が生きてる → ある頂点が死んでる) 時のペナルティが辺
    • 正の頂点を殺すと a_i ペナ
    • 負の頂点を生かしたままにしていると -a_i ペナ
    • kn が生きているのに n が死んでるとか「あってはならない」ので +∞ ペナ
    • n が生きているのに kn が死んでるとか…それはあり得るのでペナ指定なし

ペナルティ0のスコア=正の頂点が全て生きていて、負の頂点が全て死んでいる場合のスコア、
すなわちΣ(正のa_i)
ここから最小ペナルティを引いたのが答え。

最小ペナルティを求めたいのに最大フローってなんか腑に落ちない。
最小カットって思えば最小だけど。泣く泣く切っていって出血量を最小にするのが最小カットか。

11/15(木)

ARC 087 E - Prefix-free Game (700)

時間めちゃかかったけど自力で解けたー

深さLのBST(というかtrieというか)を考える
{s} に含まれるそれぞれの文字列 s_i は、trieにおいてrootからその文字列の終端までの経路上のすべてと、終端より下全てを消去する。
残るのは深さがばらばら(とはいえL以下)の完全二分木的な部分trieが、高々1e5個。

どういう手を踏んでいくのが最適かはこの段階では全く分からないんだけど、Nimみたいなところに落とし込めるんだろうか(=Grundy数が定義できるだろうか)。

部分trieにAlice/Bobが何らかの手を打つ(文字列をSに追加する)とそのtrieはどうなるか。
部分trieのrootを取るとそのtrieは消滅。1段下を取ると、もう片方の部分trieが残る(ので深さが1減る)。2段下を取ると、深さが1減ったtrieと深さが2減ったtrieが残る。
Nimで言えば、手によって山が増える場合があることになる。

ある状態のGrundy数は行き着くことの出来る状態に含まれない最小の非負整数。

  • G(山のない状態) = 0 。
  • G(深さ1の部分trie) = 消すことしかできないので {0} に含まれない最小の非負整数、すなわち1
  • G(深さ2の部分trie) = 消すこともできるし深さ1にも変えられるので {0, G(1)}={0,1} に含まれない最小の非負整数、すなわち2
  • G(深さ3の部分trie) = 消すこともできる / 深さ2にも変えられる / 深さ2と深さ1の木を生み出せる、ということで {0, G(2), G(2) xor G(1)} = {0,2,3} に含まれない最小の非負整数、すなわち1

...

  • これをあらかじめ計算して用意しておけば…いや深さの最大はL=1e18だし無理
  • 規則性があるのか、小さめのLでシミュレートして様子をみる
  • 0,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,...
    • ???
    • あ、もしかしてxの一番下のbitでは
    • とすると、黒魔術 x & -x でO(1)で求められるではないか
    • G(x) = x & -x
  • ここまで来ればただのNim
    • Nimの勝利条件って何だっけ
    • ああ、山を全部xorして0なら負け、非0なら勝ち、か

練習がてら transform() とか、accumulate() に xor を渡すのとか書いてみた。

bool nim(vector<int>& a) {
    int acc = accumulate(a.begin(), a.end(), 0, [](int x, int y){ return x ^ y; });
    return acc != 0;
}

bool solve(vector<int>& a) {
    vector<int> b(a.size());    
    transform(b.begin(), b.end(), [](int x){return x & -x;});
    return nim(b);
}

accumulateにまとめられる気がするなこれ

bool nim(vector<int>& a, function<int(int)> grundy_proc) {
    int acc = accumulate(a.begin(), a.end(), 0, [grundy_proc](int x, int y){ return x ^ grundy_proc(y); });
    return acc != 0;
}

bool solve(vector<int>& a) {
    return nim(a, [](int x){return x & -x;});
}

ついでにtemplate化して

template <typename T>
bool nim(vector<T>& a, function<T(T)> grundy_proc) {
    T acc = accumulate(a.begin(), a.end(), (T)0, [grundy_proc](T x, T y){ return x ^ grundy_proc(y); });
    return acc != (T)0;
}

bool solve(vector<int>& a) {
    return nim(a, [](int x){return x & -x;});
}

いざ提出
→WA(1)
https://beta.atcoder.jp/contests/arc087/submissions/3603825
いっけなーい!Lが10^{18}までっての忘れてたー!
Lが絡む箇所をlong longに直して
→AC
https://beta.atcoder.jp/contests/arc087/submissions/3603842

解説読んだ

解法同じだった
// こんなの時間内に出来るのかよ、と思ったけど本番では80人が通してた…

11/17(土)

ARC 090 E - Avoiding Collision

  • とりあえずSとTから全頂点へdijkstra
  • その最短距離である頂点にたどり着くのが何通りずつあるかも求めておく
    • dS[u] = (最短距離, 何通り), dT[u] = (最短距離, 何通り) みたいな
    • dS[T] == dT[S] なはず
    • (S→Tの最短距離) = dS[T].first
  • 高橋くんも青木くんも dS[T] の組み合わせの数だけパターンを持ってるので、まずこの数の2乗をとる。そこから2人がぶつかる組み合わせを排除していく
  • ある頂点 x でぶつかるケース:dS[x] == dT[x] かつ dS[x] + dT[x] == (S→Tの最短距離)
    • dS[x], dT[x] それぞれ何通りか求めてあるのでそれらの積を引く
    • 高々1e5通り
  • ある辺 uv でぶつかるケース:dS[u] + len(uv) + dT[v] == (S→Tの最短距離) かつ (S→Tの最短距離)/2 が uとvの間(両端を除く)に来ること
    • u,vをひっくり返したやつも試す
    • dS[x], dT[x] それぞれ何通りか求めてあるのでそれらの積を引く
    • 高々2e5×2通り

サンプルケース通った!
(80分ぐらいかかったけど)自力で解けたかも!?
…と思ったけどWA

組み合わせの数の計算が間違ってる?
(最短でない時に加算してなかった… あと一度訪問した点を排除しちゃいけない?)

直して
→WA(+TLE)

  • [WA] 組み合わせの数の計算がまだ違うか
    • SからとTからで数が違うぞ…
    • dijkstraの十分大きな定数が十分に大きくなかった
  • [TLE] 組み合わせの数の計算の効率が悪い。
    • 一旦普通のdijkstraした後、topologicalな順序でdpすればよくね?

いろいろ直したけどまだ半分以上WA…

解説読む

解法は概ね合ってるんだけど、
dS[u] * dT[v] じゃなくて、dS[u]^2 * dT[v]^2 を引いていかなくちゃいけなかった。
なんで?(最初のdS[T]^2は分かるんだけど…)

ああ。高橋くん・青木くんそれぞれについて dS[u] * dT[v] だからその2乗なのか。

直して
→AC
https://beta.atcoder.jp/contests/arc090/submissions/3619241


11/18(日)

ARC 092 E - Both Sides Merger

割とすんなり解けた(かに見えた)

  • 奇数番目のみ or 偶数番目のみ で、非負整数だけ残して全部消したものの和
    • 負の値は偶奇が逆のものに消してもらう
    • 最後にカスケード的にまとめる
  • 右から消したほうがインデックスが動かなくて良いかな

それでも1時間ぐらいかかってて
→WA
https://beta.atcoder.jp/contests/arc092/submissions/3619683

解説みた

大体あってるんだけど、まとめ方で問題があったかも

  • 残したいもの(あるいは消したいもの)の位置のリスト (oxxxoxoxoxxxo...みたいな)のを作ってそれを処理するのが便利。
    • xxxxoxxxoxoxoxxxxx みたいなのを
      • まず左右のxxxを全部消して
      • ox(xx)*ox(xx)*o みたいになるので
      • xxxの塊をそれぞれ、長さ1になるまで2番めのxを叩いて、長さ1になったらそのxを叩いて潰す(この処理でoが2つ繋がる)

あと、コーナーケースとして「全部負の値だった場合」の例外処理が必要。

→AC
https://beta.atcoder.jp/contests/arc092/submissions/3619832

ARC 094 F - Normalization (700)

寝る前に考えてて寝落ちした問題。(D=E=F=700点だった回のARCだ)

起きて考えても分からない...

  • a/b/c→0/1/2に置き換えるとか
  • 隣接項が同じか同じでないか
  • 何らかの数列になってたりするのか

時間オーバー

解説よむ

まず、Sがすべて同じ文字から成る場合は操作できないので1を返す(例外ケース)。

どんなに操作しても変わらないもの:合計のmod3 *1 *2

だとしたら

mod3が元のSと等しくなる文字列なら何でも作れるのか?

いや

何らかの操作を施した文字列は、少なくとも1箇所、同じ文字が連続する箇所がある

それなら

mod3が元のSと等しく、同じ文字が連続する箇所が1箇所以上ある文字列なら何でも作れるのか?

解説によると、|S|が4以上ならYesらしい。3以下の場合は分からないので全探索。

  • |S|=2のとき:例外ケース以外では1文字目と2文字目は異なるので1回操作できる。操作するかしないかで2通り。
  • |S|=3のとき:高々3^3=27パターンなのでまあ適当に探索。
  • |S|≧4のとき:
    • mod3が元のSと等しい:任意の文字を選び続けて最後の1文字をチェックサム的に調整するだけなので3^{|S|-1}通り
    • 同じ文字が連続する箇所が1箇所以上ある → 連続する箇所が1つもないパターン数を引く
      • 任意の文字から始めて、2文字ずつの分岐だから3\cdot2^{|S|-1}通り?
      • いや、チェックサムが合わない場合があるから…DPで
    • というわけで操作後に出来上がる文字列集合の大きさは求められる。
    • 元のSに連続した部分が1つもない場合、操作後に出来上がる文字列集合からSが外れているので+1する必要がある

実装してとりあえず通した
→AC
https://beta.atcoder.jp/contests/arc094/submissions/3620393

さて。
|S|\ge4でこの条件が満たせるのってなぜなんだ?(続く)

  • |S|=4の場合については全パターン試せば示せる
  • |S|=kのとき成り立つなら|S|=k+1のときにも成り立つ(らしい)
    • 先頭の文字を適切に変化させて、|S|-1に帰着させる
      • どゆこと?
  • 数学的帰納法によって(略)

本番でも17人しか通してないし、まあ解けなくてもおかしくない。

11/21(水)

ARC 095 E - Symmetric Grid (700)

これは出場したけど解けなかったやつだ

解法としては

  • 行の組み合わせを固定して、列の並べ替えで点対称が作れるか調べる
    • 行のpermutationを全部やると12!通りだけど、実際には6つのペアを作ればいいだけなので12C6×6! = 12×11×10×9×8×7 通りとかそのくらい
  • 列の並べ替え。
    • 縦読みした文字列(とそれをひっくり返した文字列)を作る。(仮にx[c],y[c]とする)
      • 12文字なので、文字列じゃなくて5ビットずつシフトしたlong long整数で表現してみるか
    • 二部マッチングっぽいことをすればいいのかなと思うんだけど
      • 自分とは組めない?いや、行数が奇数の場合、真ん中の行は自分と組まないといけない
    • palindromeの数を集計
      • 単に数えるだけじゃなくて、何が何種類あるか調べる。偶数個あるやつはペアが作れることが自明なので無視していい。奇数個あるやつがH mod 2個なら行けるけど、それ以外のケースはfalse
      • やっと二部マッチングのターン。palindromeでないものだけ扱う。palindromeでない縦読み文字列x,yがそれぞれm個あるとして、0\le i\lt j\lt m で、x[i]==y[j]のものだけ辺を引いて、mペア作れれば良い。

何度提出してもWAばかり出る

  • 行の組み合わせを網羅できていないのでは
    • 点対称な人工データをシャッフルしたものを食わせてもNOが出る
    • 12C6×6! のところで前半に出てくる物同士がペアになれなくなっていた

そこを直して
→AC (331ms)
https://beta.atcoder.jp/contests/arc095/submissions/3636838

解説を読む
  • 行の組み合わせを固定して、列の並べ替えで点対称が作れるか調べる

という所は合ってるんだけど、もっと合理的かつ計算量の少ない方法で解いている。

行の組み合わせ、というか行同士をペアにする方法は11×9×7×5×3×1=10395通りしかないらしい。
どゆこと?

  • 12個の任意の1つ → 残り11個から1つ選ぶ(で1ペア目)
  • 残り10個の任意の1つ → 残り9個から1つ選ぶ(で2ペア目)
  • ...
  • 残り2個の任意の1つ → 残り1個から1つ選ぶ(で6ペア目)

だからか。

で、列について。

  • まず最初に、すべての列を「未使用」とする
  • ある未使用列について、それを上下反転した列があれば、ペアを組んで、左端・右端に置く(使用済み)
  • すべての列を使用済みにできれば(列数が奇数の場合、最後にpalindromeな列が余れば)OK
    • O(HW^2)の比較が発生

10395×O(HW^2) で、HW^2=1668なので1.6e7で余裕、と。なるほど

この方針で書き直してみる。
(Fisher–Yates shuffleみたいな気持ちでペアを1つずつ組みながらキューに追加して全パターンを走査する方式。あと二部マッチングみたいな大層な仕掛けは必要ない)
→AC (15ms) 22倍速!
https://beta.atcoder.jp/contests/arc095/submissions/3637094

11/22(木)

ARC 102 E - Stop. Otherwise... (700)

これも出場した回の問題。

k面のサイコロをn個振ったときに出る組み合わせ(重複排除)は二項係数っぽいやつになる
(k-1+n C n)
ってのは分かるんだけど

合計がtになるものが存在しないって

  • すべてのパターンから、(合計がtになるもの)の合計を引く

ってこと?
合計がtになるものって言っても何通りもあるよね…

とりあえず1ペア(a,b)を持ってきたとして

  • aの左には1以上a以下の数、bの右にはb以上K以下の数が来る

それぞれいくつずつかってのも1〜N-1までの幅があって
これ全部ループしてたらO(N^3)とか余裕でかかって駄目じゃん
もっと効率よく計算できる方法があるはず

って辺りまで考えて時間切れ。

解説読む
  • t:2〜2Kそれぞれについて
  • a+b=t になるペア (a,b) (但しa<b)がp組あるとする
  • このペアの要素a,bが同時に出現したら合計tが生じてしまうのでアウト
    • どちらも出現しない or どちらか一方のみが出現しない
  • tが偶数の場合、これに加え m=t/2 が2つあるとtが生じてしまうのでアウト。
    • mは一度も出現しない or 一回だけ出現する
  • pペアのうち、どちらも出現しないものがq個、どちらか一方のみが出現しないものがp-q個ある
    • それだけでpCq通り。qは0〜pまですべて使うのでpCk一段全部求めておけばよい
      • あるいは2000までのnCk全部をテーブルで持っていればよい(計算はそれが一番速い)
  • 出現しないものが c (= 2p+(p-q) = p+q) 個あると、これはk-c面のサイコロをn回振るのと同等では
  • ペアの片方が出現しない場合、もう片方は必ず1回以上出現することを考慮したい(さもないとカウントが重複する)ので、1回の出現を固定し、試行回数(N)を1減らす。
    • m=t/2 の一回出現するケースも同様にNから1引いて考えればよい。
  • 一方のみが出現しないp-q個のペアについては、どちらが出現するかという組み合わせがあるので2^{p-q}を掛ける必要がある。

まとめると

  • p = (a<bで、a+b=tとなるペア(a,b)の個数)
    • p組のペアのうち、どちらも出現しないペアの個数をqとする。
    • 一方のみが出現するペアはp-q個あることになる
    • 出現しない目の総数 c = 2p + (p-q) = p+q
  • f(k,n) は、k面のサイコロをn回振った場合のパターン数 (=k-1+n C n) とする
  • tが奇数の場合: 各q (0≦q≦p) について
    • f(K-c, N-(p-q)) * pCq * 2^{p-q}
  • tが偶数の場合: 各q (0≦q≦p) について
    • m=t/2が1つも含まれない場合
      • cが1つ増えることになって
      • f(K-(c+1), N-(p-q)) * pCq * 2^{p-q}
    • m=t/2が1つだけ含まれる場合
      • mを1つ取り置いて、残りのN-1回についてcを1つ増やして考える
      • f(K-(c+1), (N-1)-(p-q)) * pCq * 2^{p-q}

これを足していくだけ(mod 998244353)。

→WA(1)
Nが小さくてf(k,n)に渡すnが負になってしまう場合に計算が正しく行われなかった(テストケース4つ落ちてた)
n<0のときf(k,n)=0を返すようにした。

→AC
https://beta.atcoder.jp/contests/arc102/submissions/3641732

これでARCの700点までの問題は全部埋まった。
(引き続きAGCの700点問題を攻めていく)

*1:kmjpさん「この類の問題の定番テクとして、a→0,b→1,c→2と置き換えたとき、処理によって文字列における数値の総和 mod 3は変化しないという特性を用いる。」http://kmjp.hatenablog.jp/entry/2018/04/07/1000

*2:てんぷらさん「数列や文字列に対して何らかの操作を施すタイプの問題では、操作の前後で変化しないものに着目するという方法が有効なことがあります。」「個数の差(和)はわりといい性質を持ちがち」https://tempura0224.hatenablog.com/entry/2018/04/18/151712