多倍長（自分用メモ）C++ ～boost or __int128～ 

#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<512>>;

参考

https://qiita.com/tubo28/items/fa8ee013390184b0ba18

boostは入れるのが大変？

  • VS Code + WSLでやっているのだが、いつからかboostのincludeが通らなくなった・・・

__int128

__int128_tをAtCoderで使ってみた

f:id:peroon:20200610171303p:plain

  • 出来たa.outが正しく動いていることを確認して、エイヤッと提出するとACする
  • operatorの定義はなし。>>や<<を使う場合のみ、定義が必要なようだ

verified (__int128_t)

codeforcesでも現在は使える様子

D - 地図が２枚

複素数 アフィン変換 回転 多倍長

Quiz

https://atcoder.jp/contests/utpc2012/tasks/utpc2012_04

Submission

https://atcoder.jp/contests/utpc2012/submissions/5719321

解法

  • 点(a, b)が点(b, c)に縮小・回転・移動されている
  • 縮小・回転は複素数の掛け算・割り算、平行移動は複素数の和・差で求まる
  • (a, b) -> (c, d)に移す変換を求めたら、その変換を(c, d)に適用して(e, f)を求め、収束するまで続ける

精度不足

想定解？

  • 想定解は不動点を方程式の解からO(1)で求まる方法だろう
  • そちらの方が誤差にも強いだろう

複素数でアフィン変換

  • 原点に移動して回転、これだけなのだが中々苦労した

Note

f:id:peroon:20190601142226j:plain

C - 森ですか？

Quiz

https://atcoder.jp/contests/utpc2012/tasks/utpc2012_03

Submission

https://atcoder.jp/contests/utpc2012/submissions/5717188

解法

  • N=5000など大きい時、辺の本数 N*(N-1)/2 = 125万ほど
  • Q=100000で辺を取っても木になりえないので全てN
  • より厳密には、辺の本数が N-1 以下でないと森になりえない
    • N*(N-1)/2 - Q <= N-1
    • じゃないと森になりえない
  • この条件を抜けた時、Nは小さい値になっている
    • 上記式をイコールで解くと、N2=Qに近くなり、最大でもN=400程度
  • 辺の本数はN-1程度
    • 閉路判定の計算量はO(N)
  • クエリごとに閉路判定したとしても、100000 * 400 = 4 * 107
  • よって解けました

閉路判定

  • Union Findを使った

ポイント

  • Nが大きいときと小さい時で遷移を変える

Note

f:id:peroon:20190601080556j:plain

強連結成分分解して縮約するとDAGになる

強連結 (strongly connected) とは

  • 「有向」グラフにて、各頂点が行き来できる状態

強連結成分分解とは

  • 有向グラフを、強連結なグラフに分解すること

縮約とは

  • 頂点をマージすること

DAGとは

  • Directed Acyclic Graph
  • 有向グラフだけどサイクルしていない、つまり強連結ではないグラフ

強連結成分分解して縮約するとDAGになる

DAGになると？

  • トポロジカルソートできるようになる

SCC

SCCした結果を用いて、全体を強連結にするコスト