少ない学びをせめて記録する

技術記録、競プロメモ、その他調べたことを書く @京都, twitter : @nehan_der_thal

AtCoder ABC155 メモ

atcoder

ABCEを解きました。今回難しかったようでこれでも青パフォでした。

D Pairs

割とABC149EのHandshakeに近いです。今回はゼロとマイナスの要素があるので複雑度が大きくなっています。 本番ではゼロを分けないといけないことに気づかず解けませんでした。終了後、他のバグにも気づいたのでどちらにしろ解けなかった可能性が高いです。

K以下のAi*Aj(i<j)の数をO(N)で数えることができれば二分探索でO(N*log(max(Ai+Aj)))でできます。次に数え方です。

i<jの条件を外して数えることにします。
配列Aの要素数をNとします。Aを正、ゼロ、負の要素に分けます。それぞれpA, zA, nAとします。またそれぞれ予めソートしているものとします。 pAi * pAj がK以下のものはpAiを固定してpAi*pAj<=Kとなるような境界のjを大きい方から探索すればいいです。i++すると次の境界jはさらに小さくなるので尺取り法で大丈夫です。 nAi * nAj についてはnAiを固定してnAjを小さい方から見ます。i--していきます。iの順もjの順も上と逆です。 pAi * nAj についてはiを小さい方、jも小さい方から見ていきます。nAi * pAj も同じ数になるはずなので2倍します。 あとはゼロとなる数です。K<0の時は気にしなくていいです。K>=0の時はlen(zA) * N - len(zA)2の数がK以下の数です。

上記の和をとればいいです。そのあとAi * Ai <= K となる数を数えて引いて2で割ります。 そうするとK以下の数になります。 上の尺取のところ、上からなのか下からなのか迷いながらやっているのですが脳死でできるようになりたいです。

追記

ゼロは分ける必要がなかったです。。 整理すると結構簡単な実装になりました。以下に貼っておきます。

N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    # k以下の数
    # positive positive
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # negative negative
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # positive negative
    i, j = 0, lmA-1
    while i < lnA:
        while j >= 0 and mA[j]*nA[i] <= k:
            j -= 1
        r += 2*(lmA-j-1)
        i += 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx+mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
    idx = (mx+mn)//2
print(idx+1)

E Payment

貪欲で解こうとして30分くらい溶かしてdpで解きました。dp1とdp2は下からi桁見てぴったり払うのに必要な枚数と１つ上の桁のお金を1枚払うときのそれぞれの枚数を意味しています。 更新式は以下です。（dp2 → dp2の更新が頭壊れそうになった。）

dp1[i+1] = min(dp1[i] + c, dp2[i] + c)
dp2[i+1] = min(dp1[i] + 11 - c, dp2[i] + 9 - c)

貪欲でも解けるらしい。解法を見て感心。要追記

F Perils in Parallel

まだ解いていないです。

AGC038-C の高速ゼータ変換と高速メビウス変換解法

以下にわかりやすい記事があった。うまく理解できず苦戦した。今もわかっていないが今後のために行間として考えたことをメモ

competitive12.blogspot.com

GCD(Ai, Aj) = xであるような全てのAi, AjについてAi * Aj の和を求めることができれば解が求まることが上記記事よりわかる。

まず、f(x)を(x=Aiであるようなiの数) * Ai と定義する。実装としては1からMax(Ai)までのxについてf(x)をそれぞれ求めるだけで準備できる。 そうすると、f(x) * f(y) は　Ai=x, Aj=y となるような全ての(Ai, Aj)に関するAi*Ajの和になる。

次にXの倍数に関する高速ゼータ変換によってF(X)を求める。 F(X)はf(x)の和の形になる。例えばF(1)はf(1)+f(2)+...+f(Max(Ai))であり、F(3)はf(3)+f(6)+f(9)... となる。 これは普通にX<=Max(Ai)について計算すると計算量はMax(Ai) * log(Max(Ai))になる。 高速ゼータ変換を利用すると、Max(Ai) * loglog(Max(Ai)) になる？

次にH(X) = F(X) * F(X) を計算する。単にそれぞれのXについてF(X) * F(X)を計算するだけなので計算量はMax(Ai)

H(X) を高速メビウス変換して、h(x)を得る。 高速メビウス変換は高速ゼータ変換の逆変換であり、h(x) は xの約数Xについてu(x, X) * H(X)の和を取ったものとなる。u(x, X)はメビウス関数という簡単に求められるらしいがよくわかっていない。 h(x)はgcd(x1, x2) = xとなる全てのx1, x2についてf(x1) * f(x2)の和を取ったものになる。 なぜそうなるかは冒頭記事参照。 x<=Max(gcd(x1, x2))についてh(x)を計算すればいい。計算時間はMax(Ai) * loglog(Max(Ai)) になる？

これでh(x)を見ればGCD(Ai, Aj) = xであるような全てのAi, AjについてAi * Aj の和がわかり解が求まる。

わかっていない事として、高速化の方法、なぜ逆変換できるのか(できる条件とナイーブな計算方法)、GCDやLCMじゃないもの一般の集合などについて応用例はどんなものかなどがある。 特に前半2つについてわからないと、まだこの問題は解けない。（とりあえずライブラリコピペしてしまう事で一応解けるけど。）

FFTやNTTとも関連が深そうだし研究も進んでそう。いい教科書が欲しい。

Codeforces Round #616 (Div2) 参加記録

codeforces

A, B, Cの3完でしたが、ムーブが最悪だった感じでちょっと悲しかったです。 C通った後に速度が不安になってC#で書き直して20分消費した後、Dが数分間に合わなかったので... が、何はともあれ青色になれました。次は紫目指します。

f:id:whitman:20200203112618p:plain

A Even But Not Even

２つ以上奇数があれば奇数を２つ並べるといいです。 奇数が１つ以下だと無理です。

B Array Sharpening

0indexで以下を満たすkがあればいいです。

ai<i (i<=k) and ai < N-1-i (k<=i)

ミスが相次ぎ3WA出しました。第一の失敗ポイント

C Mind Control

N人(自分含む)が一列に並んでいて自分はM番目にいます。また、長さNの数列が与えられます。 列の先頭の人から順に数列の最初または最後の数を適当に取っていきます。 自分はK人に対して予めマインドコントロールしておき、最初を取るか最後を取るか操作できます。 一人目が取り始めた後はもうマインドコントロールはできません。 ある操作をしたときに自分は最低でもx以上の数が取れるようになるとして、xの最大値を求める問題です。

まず、自分より後ろの人は操作しても意味なしです。 前の人を操作しましょう。 自分の番が来た時、数列は長さN-M+1になっています。このうち、最初と最後の大きい方をとればいいです。 操作することを考えないと、自分に残される長さN-M+1の数列候補は当然M個あります。 前の誰かに前を取るように操作したら、数列候補から先頭が消えます。後ろを取るように操作したら最後が消えます。 こうして残った候補の中で最小となるのがxです。

前を取るように指示するのをj人、そうでないのをK-j人として全探索すればいいです。 各jについて最小値を求めるので愚直にやれば、K*(N-M-K+1)の計算量となります。スライド最小を使えばKlogKになります。

愚直でもK<=1500なので通ると思ったのですが、制約が1sを見て不安になりC#で書き直し20分ロスしました。 C#の練習をした後だったので出来上がったpythonコードがあるなら数分で描き直せると思ったのですが...

D Irreducible Anagrams

はじめ問題設定が複雑に感じて苦戦しました。 ある文字列sがあって、それとanagramになる文字列tのうち、irreducible anagramとなるものがあるかを判定する問題です。 sとtをそれぞれ2つ以上に分割してs1, t1 , s2, t2, ..., sk, tk を得たときにsi, tiが全てアナグラムになっているような分割の方法があるとき、s, t をreducible anagramと呼びます。 irreducible anagramはreducibleでないものです。

結論からいうと、長さ2以上で先頭と最後の文字が同じで2種類しか文字種類がないときにはirreducible anagramとなるものはありません。そうでない時はirreducible anagramとなるものが構成出来ます。 ここまでなんとなく気付いたのは割と早かったのですが、自信がなく証明しようとしても上手くいかず、ギリギリにとりあえず出そうと実装をはじめた結果間に合わず破滅しました。 エスパーで出そうとして完全に嘘で失敗して時間を溶かしたこともあるので証明をちゃんとするか取り敢えず実装するかは迷いどころですね。

CHT (Convex Hull Trick) のpython実装を書いた

AtCoder のEducational DP contest-Z Frogを 解いていて必要だったので整備しました。

自分の実装 : Submission #9866424 - Educational DP Contest

CHTについてはググればたくさんの記事がある。以下の２つの関数がある。

  1. insert 関数 : ax+bを追加する。単調減少である順にaを追加する場合と一般の場合で計算量が変わる。
  2. find関数 : あるxに対する最小値を求める。 xが単調増加になる順にfind関数を作用させる場合と一般の場合で計算量が変わる。

実装

lines = []
def fi(i, x):
    a, b = lines[i]
    return a*x+b

def find(x):
    def f(i):
        return fi(i+1,x) > fi(i,x)
    mn, mx = -1, len(lines)-1
    idx = (mn+mx)//2
    while mx-mn>1:
        if f(idx):
            mx, idx = idx, (mn + idx)//2
            continue
        mn, idx = idx, (mx + idx)//2
    return fi(idx+1, x)

def find2(x):
    # x が単調増加
    I = find2.I
    u, v = lines[I]
    while I+1<len(lines):
        w, y = lines[I+1]
        if u*x+v < w*x+y:
            break
        u, v = w, y
        I += 1
    find2.I = I
    return u*x+v
find2.I = 0

def insert(a, b):
    pass

def insert2(a, b):
    # a が単調減少
    if not lines:
        lines.append((a,b))
        return
    (e, f) = lines[-1]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.pop()
    lines.append((a, b))

N, = map(int, input().split())
As = map(int, input().split())
for j, a in enumerate(As):
    j+=1
    insert2(-2*j, a+j**2)
for i in range(N):
    print(find(i+1)+(i+1)**2)

insert関数、find関数はそれぞれ一般の場合だがinsertは未実装。

insert2関数、find2関数はそれぞれ傾きが単調減少の場合、xが単調増加の場合で高速に動作する。

linesがglobalな変数となっていてtuple(a, b) (a:傾き, b:切片)のリストになっていて、updateやinsertを実行すると内部が更新される。

遅延セグメントツリーをC#で動かす

先日のEducational Codeforces Contest でE問題が遅延セグメントツリーを利用する必要があったのですがpypyでは通らなかったのでC#で書き直してACを得ました。 せっかくなので実装を残しておきます。 非再帰版の遅延評価セグメント木の実装メモ - 日々ｄｒｄｒする人のメモ の書き方が簡潔だったのでほぼ丸写しです。

using System;
using System.Linq;
using System.Collections.Generic
using static System.Math;

class SegTree
{
  public long[] data;
  public long[] lazydata;
  private int num;
  private long ide_ele;
  private long F(long x, long y){
    if (x>y) return x;
    return y;
  }
  private int Pow(int x, int y){
    int r = 1;
    for (int i = 0; i < y; i++){
      r *= x;
    }
    return r;
  }
  private List<int> Gindices(int l, int r){
    List<int> R = new List<int>();
    l += num; r += num;
    int lm = (l / (l & -l))>>1;
    int rm = (r / (r & -r))>>1;
    //Console.WriteLine(rm);
    while (l < r){
      if (r <= rm){
        R.Add(r-1);
      }
      if (l <= lm){
        R.Add(l-1);
      }
      l >>= 1; r >>= 1;
    }
    while (l > 0){
      R.Add(l-1);
      l >>= 1;
    }
    return R;
  }

  private void Propagate(List<int> indices){
    foreach(int i in indices.AsEnumerable().Reverse()){
      long v = lazydata[i]; lazydata[i] = 0;
      if (v==0) continue;
      lazydata[2*i+1] += v; data[2*i+1] += v;
      lazydata[2*i+2] += v; data[2*i+2] += v;
    }
  }

  public void Update(int i, long x){
    i += num-1;
    data[i] = x;
    while (i>0){
      i = (i-1)>>1;
      data[i] = F(data[2*i+1], data[2*i+2]);
    }
  }
  public void UpdateRange(int l, int r, long x){
    //Console.WriteLine($"{l}, {r}");
    List<int> gindices = Gindices(l, r);
    l += num; r += num;
    while (l < r){
      if (l%2 == 1){
        lazydata[l-1] += x; data[l-1] += x; l++;
      }
      if (r%2 == 1){
        r--; lazydata[r-1] += x; data[r-1] += x;
      }
      l >>= 1; r >>= 1;
    }
    foreach(int i in gindices){
      //Console.WriteLine(i);
      data[i] = F(data[2*i+1], data[2*i+2]) + lazydata[i];
    }
  }
  public long Query(int l, int r){
    Propagate(Gindices(l, r));
    l += num; r += num;
    long R = ide_ele;
    while (l < r){
      //Console.WriteLine($"Q {l-1} {r-2}");
      if (l%2 == 1){
        R = F(R, data[l-1]); l++;
      }
      if (r%2 == 1){
        r--; R = F(R, data[r-1]);
      }
      l >>= 1; r >>= 1;
    }
    return R;
  }
  public SegTree(long[] values, long ide_ele)
  {
    int N = values.Length;
    this.ide_ele = ide_ele;
    int tmp = N+1; // 遅延操作のため1段多く作る
    int r = 0;
    while (tmp > 0){
      tmp >>= 1;
      r++;
    }
    num = Pow(2, r);
    data = new long[2*num];
    lazydata = new long[2*num];
    for (int i = 0; i < N; i++){
      data[i+num-1] = values[i];
    }
    for (int i = num - 2; i >= 0; i--){
      data[i] = F(data[2*i+1], data[2*i+2]);
    }
  }
}

class P
{
  static void Main()
  {
    SegTree x = new SegTree(new long[] {12, 32, 21, 24}, -long.MaxValue);
    x.Update(0, 53);
    x.UpdateRange(2, 3, 8);
    x.UpdateRange(2, 4, 5);
    Console.WriteLine(x.Query(1, 4));
  }
}

利用例 :

https://codeforces.com/contest/1295/submission/69992196

問題は抽象化で現在、各値はlongで持つことが前提の実装になっています。 色々な型を入れられるようになりたいな。C#の習熟度が足りないのでまた次回に。

Educational Codeforces Round 81 参加記録 （ C. Obtain The String, D. Same GCDs ）

atcoder

また、久しぶりにcodeforcesに出てみました。4つ解けたけど自信ないです。 f:id:whitman:20200130021222p:plain 終わってみると簡単だったような気もしてくるから不思議です。Dで結構たくさん迷ったんですが。

C Obtain The String

なんか簡単そうなのに時間がかかりました。 s, tは後ろからみます。 あらかじめsの各文字に対してindexを覚えておきます。 tのそれぞれの文字に対してsのどのindexに対応するか順に計算します。このとき二部探索で一番良いのを探しましょう。

def find(i, l):
    mx,mn=len(l),-1
    if l[-1] <= i:
        return l[0]
    idx = mx//2
    while mx-mn>1:
        if l[idx] > i:
            mx,idx=idx,(idx+mn)//2
            continue
        mn,idx=idx,(idx+mx)//2
    return l[idx+1]

from collections import defaultdict
q = int(input())
for _ in range(q):
    s = input().strip()[::-1]
    t = input().strip()[::-1]
    d = defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)
    f = 0
    for c in t:
        if c not in d:
            f = True
            break
    if f:
        print(-1)
        continue
    i = -1
    r = 1
    for c in t:
        j = find(i, d[c])
        if i >= j:
            r += 1
        i = j
    print(r)

D. Same GCDs

条件を式変形して a/gcd(a,m)<= k < (m+a)/gcd(a,m) という式を得ます。 ここでkは「m/gcdの約数であってa/gcdの約数でない数」の倍数でないようにする必要があります。 少し前のABCで包除の実装をしたところだったので計算できました。

def prime_decomposition(n):
    i = 2
    table = dict()
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table[i] = c
        i += 1
    if n > 1:
        table[int(n)] = 1
    return table

def f(N, mn, ds):
    # N以下mn以上のdsのどれでも割れない数
    M = len(ds)
    r = 0
    for i in range(1, 2**M):
        t=0
        l=1
        for j in range(M):
            if i % 2:
                l*=ds[j]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*(N//l - (mn-1)//l)
        r+=xx
    return r

t = int(input())
for _ in range(t):
    a, m = map(int, input().split())
    aa = prime_decomposition(a)
    mm = prime_decomposition(m)
    ds = list()
    gcd = 1
    for key in mm:
        if key in aa:
            gcd *= key**min(aa[key], mm[key])
            if aa[key] >= mm[key]:
                continue
        ds.append(key)
    mx = -(-(a+m)//gcd)-1
    mn = -(-a//gcd)
    print(mx-mn-f(mx, mn, ds)+1)

AtCoder EDPC W - Interval

全然わからなかったし、今もわかっていない（主に遅延セグ木）ので復習用に簡単にメモ

atcoder.jp

 

 

まず、方針からわからないけどググれば解りやすい解説がたくさん出てくる。

以下が解りやすかった。

 

Educational DP Contest : W - Intervals - kmjp's blog

 

上のリンクをはじめとして多くの解説ページの繰り返しになるけど、更新処理は単純 : 

DPは要素数N+1、初期値0で初期化

dp(n) をnbit目が1、n+1bit以降は0となるような文字列の最大スコアと定義

更新は各nについて以下の3操作をする。

1. l=nであるような入力l,r,aそれぞれに対して、 dp(0..n-1) += a 

2. dp(n) = max(dp(n-1))

3. r=nであるような入力l,r,aそれぞれに対して、dp(0..l-1) -= a

 

最終的な答えはmax(dp)、途中でn-1以下のdp(i)を区間加算とかでいじってるけど最終的には操作1と操作3で打ち消されるので結局操作2で代入された時点でのdp(n)に戻る。

 

1と3では区間加算、2では区間和と単値更新が必要、遅延セグ木は何もわからないのでググって貼った。（結局ここが一番難しかった）

 

非再帰版の遅延評価セグメント木の実装メモ - 日々ｄｒｄｒする人のメモ

 

 

セグ木を実装レベルで理解していないので大変に感じる。

上の実装を理解して自分で好きに弄れるようにならないとこういう問題の本番ACは厳しそう。

 

セグ木が他人のコードのコピペなので、自分で書いた部分が少なく恥ずかしいけど最終的なコード(1939ms)

Submission #9776330 - Educational DP Contest