ferinの競プロ帳

競プロについてのメモ

markdownをはてなブログ用に変換し投稿するスクリプト

はてなブログに投稿するときに数式を$ $でなく[tex: ]で囲んだり_や^をエスケープしたり色々面倒だったので変換や投稿などを行うスクリプトを書きました.markdownファイルの数式や箇条書き,XMLはてなブログ用に書き換える処理を行いブログに投稿します.

基本的に自分が使う書き方のみ対応させた適当実装なので動かないことを知っているmarkdownの構文やバグが大量に存在しています.利用の結果生じた損害について、一切責任を負いません.

使い方

最初にスクリプトの該当変数(16~18行目)にはてなブログAPIキー,URL,ユーザー名を書いておきます.APIキーはブログの設定画面から見ることができます.

ブログ記事にしたいmarkdownファイルを用意します.1行目にタイトル,2行目にカテゴリ,4行目以降に本文を記述します.
(例)

# ABC143 A - Curtain
tag: Atcoder

[問題ページ](https://atcoder.jp/contests/abc143/tasks/abc143\_a)  

[tex:\max(0, a-2b)]を出力する

スクリプトを実行するとブログへ投稿されます.第一引数にファイル名を指定します.下書き投稿をしたい場合は第2引数に'--draft'か'-d'をつけます.
(例)

$ python3 blog\_post.py filename.md
$ python3 blog\_post.py filename.md --draft

スクリプト blog_post.py

行っている変換処理について

数式について

$ $を[tex:]に変換します
_と^の前に\を追加します
$$ $$には対応させていません

箇条書き

先頭の*の前に改行を追加します
先頭に太字で*title*などが来るときに余計な改行はいれないようになってます

XML

API経由でブログを投稿する場合,XMLファイルをPOSTするのですが,<>&"' はXMLエスケープが必要な記号なので変換します

画像(これバグってるので使えない)

markdownに画像のパスを書いておくと (\img{path}) その画像をはてなフォトライフにアップロードして該当画像を表示するURLをブログの該当部分に埋め込む

今後実装したいもの

  • カテゴリ関連
  • 画像投稿のバグを直す
  • 投稿した記事についてのツイート機能

ABC143 F - Distinct Numbers

問題ページ

基本的に使用している文字は公式解説と同じ意味になるように使っています.
X回操作ができるような整数Kのうち最大のものをf(X)とする.

C_iを数列Aに含まれるiの個数とする.X回操作するとき,整数iを選択できる回数は \min(C_i, X) 回である.よってX回操作をするときに,操作の対象にできるカードは \sum_{i=1}^{N} \min(C_i, X)枚である.したがって f(X)=\lfloor \sum_{i=1}^{N} \min(C_i, X) / X \rfloor となる.

C_iをソートしておくと C_i > X となるような最小の i を二分探索で求めることができる.このような i\text{itr} とすると f(X) = \lfloor (\sum_{i=1}^{\text{itr}-1} C_i + X(n-\text{itr})) / X \rfloor となる.よって f(X)\ (1\leq X\leq N)O(NlogN)で求めることができた.
公式解説と比べて二分探索をしている分logがついているが,数式変形が楽(主観)な気がした.

あとは,K\ (1 \leq K \leq N) について K \leq f(X) であるような最大の X を二分探索を用いて求めればよい.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync\_with\_stdio(0); }}fastiofastio;
#ifdef DEBUG\_ 
#include "../program\_contest\_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n) cin >> a[i], a[i]--;

    vector<ll> cnt(n);
    REP(i, n) cnt[a[i]]++;
    sort(ALL(cnt));
    vector<ll> sum(cnt);
    FOR(i, 1, n) sum[i] += sum[i-1];

    vector<ll> f(n+1);
    FOR(x, 1, n+1) {
        ll itr = upper\_bound(ALL(cnt), x) - cnt.begin();
        f[x] = ((itr==0?0:sum[itr-1]) + x*(n-itr)) / x;
    }

    FOR(k, 1, n+1) {
        auto check = [&](ll mid) { return k <= f[mid]; };
        ll lb = 0, ub = n+1;
        while(ub-lb>1) {
            ll mid = (lb+ub)/2;
            if(check(mid)) lb = mid;
            else ub = mid;  
        }
        cout << lb << endl;
    }

    return 0;
}

カタラン数

数え上げにおいてときどき現れる.括弧列の数・多角形の分割・グリッドの経路数などがカタラン数で表される.

参考資料
wikipedia 括弧列・二分木・最短経路・三角形分割・平面グラフ・非交差分割
高校数学の美しい物語 トーナメント・最短経路・三角形分割
カタラン数 括弧列・最短経路・整数を2段に並べる
講義スライド 凸多角形・二分木

定義

 C_n = \frac{1}{n+1} \binom{2n}{n}

i  C_i
0 1
1 1
2 2
3 5
4 14
5 42

競プロ的にはcombinationの部分の前計算をO(n)でしておけばあとはO(1)

応用例

グリッドで対角線をまたがない最短経路数

n \times nの二次元グリッドで対角線をまたがないような最短経路が何通りあるか? 制約なしの最短経路数は\binom{2n}{n} 対角線をまたぐような最短経路数は\binom{2n}{n-1} グリッドで対角線をまたがない最短経路数は\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1} \binom{2n}{n}=C_n

括弧列

開括弧と閉括弧が対応するような長さ2nの括弧列はC_n通り 開括弧を上への移動,閉括弧を右への移動とすると対角線をまたがないことが括弧列の対応が取れていることに相当する

二分木

葉がn+1個の二分木はC_n通り 葉がn+1個の二分木と長さ2nの括弧列を対応づけられる

凸多角形の三角形分割

n+2頂点の凸多角形をn個の三角形に分割する方法はC_n通り

トーナメント

n+1人によるトーナメント表はC_n通り ただしチームは区別しない

平面グラフの交差

円上の2n個の点を交差させずに結ぶ方法はC_n通り

カタラン数がでてくるわけではまったくないけど ARC076 E - Connected? とかはこれが括弧列と同一視できることをつかってる気がする

非交差分割

非交差分割とは、集合の分割の内、「集合の要素を円状に並べ、同じ部分集合に属する要素を頂点とした多角形同士が交差しない」分割を指す。 非交差分割 - Wikipedia

n要素の集合の非交差分割はC_n通り

2段の表に並べる

2n列の表に12nまでの整数を以下の制約にしたがいつつ並べる方法はC_n通り

  • 各行で左から右へ数が増加
  • 各列で上から下へ数が増加

この問題はそのままこれを使っている KUPC2019 D - Maximin Game

ヤング盤

ヤング図形 wikipedia
フック長 wikipedia

「ヤング盤が何通りあるか?」はフック長の公式から計算できる
分割\lambda=(\lambda_1,\ldots,\lambda_m)ヤング図形のあるマス(i,j)について

  • 同じ行で(i,j)より右にあるマス
  • 同じ列で(i,j)より下にあるマス

の個数をh_{\lambda}(i,j)とする

h_{\lambda}(i,j) の例
img

フック長の公式の定義 d_{\lambda} = \frac{n!}{\prod h_{\lambda}(i,j)}
2段の表に並べる方法が何通りか \iff 2n列のヤング盤が何通りか
フック長の公式に当てはめるとd_{\lambda}=\frac{(2n)!}{n!(n+1)!}=C_n

JAG夏合宿2019 Day2

J

各操作で左崎さんは a_1,右男さんは a_nを必ず1減らす
相手の値を減らせるなら減らすべきなので数列に0が存在しないときは[1,n]を選択するべき
よって \text{min}(A_i)回[1,n]を選択する操作を繰り返す
この操作をした後はお互いa_1とa_nを減らし合って先に0になった方が負けになるゲーム
よって  (a_1 > a_n) (a_1 = a_n かつ minが奇数) なら勝てる

 a_1 > a_n \frac{(S+1)^n - (S+1)^{n-1}}{2} 通り
 a_1 = a_n かつ minが奇数 →  f(S) = S^(n-1) - (S-1)^(n-1) + … - 2^(n-1) + 1^(n-1) f(x)はn-1次の多項式っぽいのでn点を使用してf(S)を多項式補完で求める

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3884679

変形すると  \sum_{i=0}^{S} i^{n-1} の形になる
 \sum_{i=0}^{n-1} i^k はベルヌーイ数がわかっていればO(k)
ベルヌーイ数の前計算は O(k^2)

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3884834

C

s[i]のsuffixとs[j]のprefixが一致する最大の文字数(=w(i,j))の分削減できる
頂点を2n個並べた二部グラフをつくって文字列i → 文字列j に重みw(i,j)の辺を貼って最大二部マッチング
これは最小費用流を使えばできる

w(i,j)はkmpとかで求まる

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3886334

F

グラフの最大独立集合 = 線グラフの最大マッチング
最大マッチングのサイズはtutte行列でO(n3)で計算可能

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day2/3886596

残りは解けたら…

JAG2019 Day3

ABC はい
E DP
D 2SAT
H UFマージテク
G 期待値で式変形を頑張る
I 係数がパスカルの三角形になってる FFTでやる
J 行列を構築するやつ
F よくわからん

D

x_i = (iを集合に入れるならtrue) とする
XORについてのclosureを (not x_i) or (not x{i xor X}) と (x_i) or (x{i xor X}) の両方入れないといけないことに注意
AND, ORは部分集合の列挙でO(3n)でできる

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3883568

E

dp[i問目まで][赤をj個][赤の残量k]
dp[n][i][j] で赤と黒それぞれ足りてれば chmin(ans, dp[n][i][j])
足りてるやつがなければ-1

累積和のindexでごちゃごちゃやるの初心者か?

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3883738

H

c_iとd_iをつないだグラフで \sum_連結成分 min(頂点数,辺数) が答え
各頂点を根とする部分木を表すUnionFindと辺の集合を持ってマージテクでマージする
UnionFind全てにK色分の情報をもたせると終わるのでmapかunordered_mapで必要なところだけもつ

dfsの内部のマージ処理をmerge関数に切り分けたらREが消えた
RE: https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884172
AC: https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884159

スタック領域を広げるやつを使ったけどREだった
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884229
構造体をswapするのがまずいのかと思って参照渡ししてswapするのを書いたけどRE
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884250

わからん

G

連結成分の個数 = 頂点数 - 辺数
確率変数として

  •  X_{v_i} = Tの頂点 v_iが残るなら1で残らないなら0
  •  X_{e_i} = Tの辺 e_iが残るなら1で残らないなら0

と定める. U についても  Y_{v_j}, Y_{e_j} を同様に定める.期待値の線形性より
 E \lbrack (\sum_{i} X_{v_i} - \sum_{i} X_{e_i}) \times (\sum_{i} X_{v_i} - \sum_{i} X_{e_i}) \rbrack = \sum_{i,j} E \lbrack X_{v_i} Y_{v_j} \rbrack - E \lbrack X_{v_i} Y_{e_j}  \rbrack - E \lbrack X_{e_i} Y_{v_j} \rbrack + E \lbrack X_{e_i} Y_{e_j} \rbrack
となる.
 X_{v_i} Y_{v_j} v_i = v_j のとき0, v_i \neq v_j のとき1/4となる.
 X_{v_i} Y_{e_j} e_j の端点に  v_i があるとき0,ないなら1/8となる.
 X_{e_i} Y_{e_j} e_i e_j の端点に共通する頂点番号があれば0,ないなら1/16となる.

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3891209

I

畳み込みに帰着 f:id:ferin_tech:20190927161324j:plain

これはNTTでやってる
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3893071

NTTじゃなくてFFTでやったら落ちたので多分誤差
FFTでやって通ってるのもある https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3871633
long doubleにしたらFFTでも通った

実部と虚部にそれぞれ数列を埋め込むとFFT2回で畳み込みができる
A_x + iB_xをDFT したやつを掛け合わせて係数を合わせると畳み込みのDFTと一致することが確認できる

fft::multiply が本質
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3895035

上位15bitと下位15bitに分割してそれぞれ畳み込むとdoubleで誤差が出ない範囲で収まると期待できる これはFFT4回 でできる https://min-25.hatenablog.com/entry/2017/09/23/085053
NTTで任意MOD畳み込みするより早い

fft::multiply_mod が本質
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3895029

J

解説の通りに構築すると通ります どうやったら思いつくかは知りません
対角線で二等分して片方だけ構築すれば残りも自動的に決まる

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3895278

F

解けません

JAG夏合宿Day1

ABCDEJ → コンテスト中に解いた F: 凸関数 G: DP H: 2数の積の桁長 I: 誤差がやばい K: 畳み込み

K

1次元につぶす
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day1/3873509

G

解説で素直なDPとなっているDPの一例を書く.A[i][j], B[i][j], D[i][j] を解説の通り定める.

初期値 A[0][0]=0, B[0][0]=1, D[0][0]=s[0][0]の数字

遷移 modを取るのは省略して書く

  • A[i][j]
    • A[i][j] = (A[i-1][j]+D[i-1][j]) + (A[i][j-1]+D[i][j-1]) (s[i][j]='+')
    • A{i][j] = A[i-1][j] + A[i][j-1] (s[i][j]='*' か 数字)
  • B[i][j]
    • B[i][j] = combi(i+j, i) (s[i][j]='+')
    • B[i][j] = D[i-1][j] + D[i][j-1] (s[i][j]='*')
    • B[i][j] = B[i-1][j] + B[i][j-1] (s[i][j]は数字)
  • D[i][j]
    • D[i][j] = 0 (s[i][j]='+' か '*')
    • D[i][j] = 10D[i-1][j]+dB[i-1][j] + 10D[i][j-1]+dB[i][j-1] (s[i][j]=d 数字)

答え
A[h-1][w-1] + D[h-1][w-1]

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day1/3874148

H

  • クエリを「i行目のj文字目は何か?」に帰着するパート
    浮動小数点のような持ち方を考えると,2数の積の長さは それぞれの桁数の和+1+(仮数部の積が10以上か?) となる.仮数部でソートしておくと,仮数部の積が10以上になる最小のb[i]を二分探索で求められるので,i行目が何文字か?を求められる.

  • 行ごとにj文字目は何かを求めていくパート
    行yのj文字目が属するマス(y,x)が何か?を高速に求められればいい.xは二分探索で求まる.
    複数行について考える場合,仮数部が小さい行から順番に見ると数列に+1する更新しか飛んでこないのでBITで管理できる.

仮数部でソートするのは文字列にして辞書順ソートすると楽
サボってlog2個にしたけど普通に通った

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day1/3874931

I

折れ線の集合をchtで持って交差する位置を二分探索で求める
TLも誤差も厳しすぎて泣いた

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day1/3886846

F

凸関数のsum,maxを取っても凸関数が保持される
ユークリッド距離 sqrt((x1-x2)2+(y1-y2)2) は凸関数
k個の点の距離の和はsumを取ってるだけなので凸関数
nCk個のsumのmaxを取ると上位k個の和になるがこれは凸関数

凸関数なので三分探索をすればいい

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day1/3886897

CODE FESTIVAL 2016 Final H - Tokaido

問題ページ

考えたこと

  • dp[すぬけくんのコマの位置][りんごさんのコマの位置][手番] としたDPはできそう
  • 明らかに状態が多すぎるので減らしたい
  • コマが隣接して置かれていないとき,左のコマは右に隣接するまで一つずつずらすのが最適
  • dp[左のコマの位置][手番] としたDPにできそう
  • 手番が変わったとしてもdpの正負が反転するだけなので手番は持たなくていい
  • 遷移を考えると dp[i] = max(-dp[j]+a[j]-sum(a[i+1]~a[j-1]) | i<j) となる
  • この遷移はO(N)かかるので高速化が必要
  • 区間add区間maxができる遅延セグ木があればO(log N)でできる
  • M=1なら解けた
  • a[n-1]が変化したときに答えがどう変化するのか?
  • a[n-1]がめっちゃ大きかったら答えが a[0]-a[1]-sum(a[2]~a[n-2])+a[n-1] となるのははい
  • 実験を書いたが大した規則がなくて不可能では?
    -----解説を見た-----
  • dpの遷移の高速化をもっと単純な形にできる
  • 蟻本p67の重複組み合わせの変形のように dp[i] と dp[i+1] の形が似ていることを使う
  • dp[i] = max(dp[i+1]-a[i+1], a[i+1]-dp[i+1]) = abs(dp[i+1]-a[i+1]) となる
  • ans = a[n-1] からスタートして ans = abs(ans-a[i]) という遷移をi=n-2からi=2まで行えばよい
  • dp[i=jまで遷移を行った][ansの値] = score としたDPを考えると答えはdp[n-1][a[n-1]]となる
  • このDPの遷移は特徴的なので高速にできる
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n-1) cin >> a[i];

    ll sum = 0;
    FOR(i, 2, n-1) sum += a[i];

    deque<ll> dp(sum+1);
    REP(i, sum+1) dp[i] = i;
    FOR(i, 2, n-1) {
        // dp[1]~dp[a[i]] を逆順にしてpush
        vector<ll> v;
        REP(j, a[i]) v.push_back(dp[j+1]);
        REP(j, a[i]) dp.push_front(v[j]);
    }

    ll q;
    cin >> q;
    while(q--) {
        ll x;
        cin >> x;
        if(sum <= x) {
            cout << x-sum+a[0]-a[1] << endl;
        } else {
            cout << dp[x]+a[0]-a[1] << endl;
        }
    }

    return 0;
}

こういうDPの高速化を問題としてはじめて見た
DPを高速化して単純な問題にする→その問題の愚直DPを書いて高速化 するDP高速化詰め合わせセットって印象