あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder AGC 035 A - XOR Circle ※正攻法 (Rust)

競プロ AtCoder AGC035 A問題 300点 Rust

irisruneです。一応Rust第2回です。

問題

atcoder.jp

300点問題ですが、正攻法で解こうとすると考慮すべきケースを整理したり実装がやや面倒だったりと厄介な問題です。

use std::collections::HashMap;

fn main() {
    input!{
        n: usize,
        la: [usize; n]
    }
    let mut map: HashMap<usize, usize> = HashMap::new();
    for a in la {
        let value = map.entry(a).or_insert(0);
        *value += 1;
    }

    if map.len() >= 4 {
        println!("No");
        return;
    }

    let mut keys = vec![];
    let mut values = vec![];
    for (key, val) in map.iter() {
        keys.push(*key);
        values.push(*val);
    }

    if map.len() == 1 {
        if keys[0] == 0 {
            println!("Yes");
        }else {
            println!("No");
        }
        return;
    }

    if map.len() == 2 {
        if keys[0] == 0 && values[0] * 2 == values[1] {
            println!("Yes");
            return;
        } else if keys[1] == 0 && values[1] * 2 == values[0] {
            println!("Yes");
            return;
        }
        println!("No");
        return;
    }

    if values[0] != values[1] || values[1] != values[2] {
        println!("No");
        return;
    }
    if keys[0] ^ keys[1] == keys[2] {
        println!("Yes");
        return;
    }
    println!("No");
}

まずこの問題の最も大きなポイントとしては、条件を満たす場合に登場する帽子の値は高々3種類までということです。これは排他的論理和の性質を用いることで導き出すことができます。

問題はある値の帽子が何個存在する必要があるかを考える部分で、登場する帽子の値の種類数によって変わってきます。具体的には、

  • 3種類であればそれぞれ同数（N/3）であればよいことが簡単に導き出せます。
  • 2種類の場合は、1種類は値が0である必要があり、さらにもう1種類の半分の個数（N/3:2N/3）存在する必要があります。
  • 1種類の場合は、個数はNでよいですが値は0である必要があります。

以上のように場合分けを行う必要があり、かなり見落としやすく感じられました。実際、当初は3種類の場合しか正しく考えられておらず、2回WAを出しています。

また、実装についても少し面倒なところがあり、上記コードのように連想配列を使う方法では連想配列で帽子の値と個数を整理した後に、一度配列（ベクトル）に移してから条件を満たすか確認する必要があります。

公式解説では計算量O(N\log N)と書かれているので、おそらくソートを行ってから順番に確認する方法を取るのだと思いますが、いずれにしてもやや面倒かつ冗長な気がしています。

雑記

Rustについて、

  • Hashmap.entry().or_insert()で条件分岐の必要なく連想配列への値の追加が行えるのは便利だと思いました。
  • 一方で参照渡しと値渡しを的確に使い分けないとコンパイルすら許されないなど、プログラムを動かすまでの道のりが険しく感じられます。
    • プログラムが正しく動くことがある程度保証されるのは強みだと思いますが、個人的には動かしてからデバッグしたいので少し合わない所があるかもしれません。

AtCoder AGC 035 C - Skolem XOR Tree (Rust)

競プロ AtCoder AGC035 C問題 700点 Rust

irisruneです。Rust第一回ですが、余りにも茨の道すぎて早くも最終回が近い予感がしています。

前置き

Rustは入力がかなり難解なので下記サイトよりマクロを拝借しております。中身はほとんど理解できていません。本ブログ上では記述を省略します。

qiita.com

問題

atcoder.jp

本ブログ初の700点問題です。ある程度手計算で試すと最近の500点くらいに感じられました。

fn main() {
    input!{
        n: usize
    }
    let mut m = 1;
    while m <= n {
        if m == n {
            println!("No");
            return;
        }
        m *= 2;
    }
    println!("Yes");
    m = 2;
    while m < n {
        println!("{} {}", 1, m);
        println!("{} {}", 1, m + 1);
        println!("{} {}", m, m + n + 1);
        println!("{} {}", m + 1, m + n);
        m += 2;
    }

    println!("{} {}", n + 1, n + 3);

    if n % 2 == 0 {
        m = n;
        let mut e = 0;
        while m > 1 {
            m /= 2;
            e += 1;
        }
        println!("{} {}", n, 2usize.pow(e));
        println!("{} {}", n * 2, n + 1 - 2usize.pow(e));
    }
}

図がないと説明が難しいので、以下では公式解説を見ていることを前提とします。まず、Nが2のべき数（2のべき乗で表される数）の場合は条件を満たす木は存在しません。なぜなら、重みが2^eより小さい数同士の排他的論理和は必ず2^eより小さくなるためです。

次に、Nが3以上の奇数の場合について考えます。まず、N=3の場合は入出力例1のように条件を満たす木を構成することができます。ここで頂点の重みについてのみ考えると公式解説の図（の一部）になります。

更にN=5に増やした場合について考えると、木に対し重みが4,5の頂点を2つずつ追加することとなります。ここで端点でない重み1の頂点に対し、公式解説の図のように頂点を接続することで条件を満たす木を構成することができます。これは、整数Mに対して2M xor (2M+1) = 1となることから証明できます。

あとは同様の操作により、N=7,9,\ldotsに対しても条件を満たす木を構成することができます。

最後にNが（2のべき数でない）偶数の場合についてですが、重み1の頂点と重み2,3,\ldots,N-1の頂点が隣接していることと、（Nが2のべき数でないとき）A xor B=A+B=Nとなる2整数を用いてA xor 1 xor (B+1) = Nとなることから条件を満たす木を構成することができます。具体的な手順としては、Nより小さい最大の2のべき数をAとおき、重み1の頂点に接続している重みA,B+1の頂点それぞれに重みNの頂点を接続すればよいです。

雑記

  • グラフ（木）問題を解説する場合は図が必要となることが多いので鬼門ですね。
    • グラフ作成ツールを探してくるべきだとは思います。
  • A問題は一応正攻法で解きましたが時間もWAもかさんで大変でした。嘘解法がなければC問題の方が簡単だと思います。

AtCoder ABC 133 E - Virus Tree 2

競プロ AtCoder ABC133 E問題 500点 Python

irisruneです。個人的に以前のABCの4完が最近のABCの5完に相当するように思えるのですが、誰か統計取ったりしているのでしょうか。

問題

atcoder.jp

500点問題の割にアルゴリズムも実装もかなり軽めで、発想系の問題だと思いました。

import sys
import collections as col
import numpy as np
MOD = 1000000007


def input():
    return sys.stdin.readline().rstrip()


def main():
    n, k = [int(e) for e in input().split()]
    adj = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = [int(e) for e in input().split()]
        adj[u].append(v)
        adj[v].append(u)

    ans = 1
    queue = col.deque([(1, 0, k)])
    while len(queue) > 0:
        u, p, k_ = queue.popleft()
        ans = (ans * k_) % MOD
        if p == 0:
            k_next = k - 1
        else:
            k_next = k - 2
        for v in adj[u]:
            if v == p:
                continue
            queue.append((v, u, k_next))
            k_next -= 1
    print(ans)


main()

500点問題ということやグラフ（正確には木）問題ということもあってかなり難しく捉えがちですが実はかなり単純で、幅優先探索を行うことを考えると、

  • 適当な点を始点として考えると、始点で選べる色はK通り。
  • 始点から1番目に選んだ点で選べる色はK-1通り。
  • 始点から2番目に選んだ点で選べる色は、
    • 始点と隣接している場合はK-2通り。
    • 始点から1番目に選んだ点と隣接している場合はK-2通り。
  • 始点から3番目に選んだ点で選べる色は、
    • 始点と隣接している場合はK-3通り。
    • 始点から1番目に選んだ点と隣接している場合はK-3通り。
    • 始点から2番目に選んだ点と隣接している場合はK-2通り。

…というように組み合わせの数が決まっていきます。少し整理すると、

  • 始点に隣接する点については、順番にK-1,K-2,\ldots通りの色を選べる。
  • それ以外の点に隣接する点については、順番にK-2,K-3,\ldots通りの色を選べる。
    • 当然ながら、親となる点は含まない。

となるので、それに従って色を選ぶ組み合わせの数を計算することができます。途中で負の値が出現するケースも考えられますが、その場合は0も出現するため出力結果が0となるだけで問題はないです。

計算量はO(N)程度なので、順列の組み合わせ数を求めて計算に用いる場合（おそらくO(N+K)）に比べると計算量は少なく済むと思います。公式解説のコードでは順列の組み合わせを用いていないようですが。

余談ですが、深さ優先探索で解く場合には順列の組み合わせ数を用いざるを得ないとは思います。

雑記

  • 変数について、k_nextはまだしもk_は流石にネタが切れすぎでしょうと見直して思いました。

AtCoder ABC 133 D - Rain Flows into Dams

競プロ AtCoder ABC133 D問題 400点 Python

irisruneです。弊社でRustが布教されているので試していますが、気を付けなければいけないことが多い言語なのでなかなか大変ですね。

問題

atcoder.jp

単純な連立方程式を解くだけの問題ですが、規模が大きいので一工夫必要となります。

import sys
import numpy as np


def input():
    return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    a = [int(e) for e in input().split()]
    x = [0 for _ in range(n)]
    x[0] = sum(a) - (sum(a[1:n:2]) * 2)
    for i in range(2, n, 2):
        x[i] = x[i-2] + ((a[i-1] - a[i-2]) * 2)
    x[1] = sum(a) - (sum(a[2:n:2]) * 2)
    for i in range(3, n, 2):
        x[i] = x[i-2] + ((a[i-1] - a[i-2]) * 2)
    print(*x)


main()

この問題はN元連立1次方程式に変換することができます。N個の式が作れるため、X_1は計算量O(N)で求めることができます。しかし、残りのX_iを同様にして求めると全体の計算量がO(N^2)となってしまいます。

そこでX_i,X_{i+2}の関係について考えると、X_{i+2}=X_i+2A_{i+1}-2A_iとなるため、尺取り法を用いることでX_3,X_5,\ldotsを求めることができます。同様にX_2からX_4,X_6,\ldotsを求めることができるため、全体の計算量をO(N)に抑えることができます。

iの偶奇にかかわらず漸化式の形は同じなので、上記提出コードのようにループを2つに分ける意味は処理をわかりやすくする以外に特にありません。

雑記

  • 公式解説を見ればわかる通り、X_i,X_{i+1}についての漸化式が存在します。というより連立方程式のそれぞれの式が漸化式です。なので尺取り法とか考える必要は全くなかったです。

  • 連立方程式を解けさえすればいいので、ソルバーに突っ込んだりすれば非常に簡単に解けるとは思います。

    • ただし、行列の形にするとN\times N行列ができてしまうので、疎行列形式でデータを持つ必要があると思います。
    • 実はソルバーについて全く詳しくないのですが、疎行列を渡して計算時間がO(N^2)かからないソルバーってざらにあるものなのでしょうか？

AtCoder ABC 133 C - Remainder Minimization 2019

競プロ AtCoder ABC133 C問題 300点 Python

irisruneです。求められるレベルが上がっている感じがあるので競プロの勉強もしたいですが、他にも勉強するべきことがあるので大変ですね。

問題

atcoder.jp

うっかりするとWAを出してしまうこともあるかと思いましたが…気のせいかもしれません。実装はB問題より軽いです。

import sys
import math
import numpy as np
INF = 1000000000
MOD = 2019


def input():
    return sys.stdin.readline().rstrip()


def main():
    l, r = [int(e) for e in input().split()]
    ans = INF
    for i in range(l, min(l + MOD, r + 1)):
        for j in range(i + 1, min(l + MOD, r + 1)):
            ans = min(ans, ((i % MOD) * (j % MOD)) % MOD)
    print(ans)


main()

公式解説にもあるように、aを2019で割った余りとbを2019で割った余りが同じならば、a\times cを2019で割った余りとb\times cを2019で割った余りが同じであることが言えます。そのためi,jについて2019で割った余りについてのみ考えればよく、考えるべきi,jの組は高々2019^2程度となります。

あとは単純に取り得るすべての組み合わせについてi\times jの剰余を求めて最小値を出力すればいいだけなのですが、変に計算量を減らそうと考えると剰余が最小となるi,jの組み合わせについて求めればよいだけと考えてしまうかもしれません。 しかしこれは2つの理由で正しくありません。

1つ目は、2019が合成数であるということです。例えば、i=3,j=673のときにi\times j=2019となり剰余が0となります。これによってi,jともに剰余が0でなくとも積の剰余が0となることがあります。

2つ目は、そもそもの考え方が間違っているということです。単純に、i=2,j=1010のときにi\times j=2020となり剰余が1となります。i,jの剰余が最小ならば積の剰余が最小となるという前提が間違っているのでこの方法は取れません。

2019が合成数ということを問題を解く前に知ってしまったので、どうせならと思いそれを踏まえた解説を考えていたのですが、別に合成数かどうかはあまり関係ありませんでしたね。

雑記

  • ネタが尽きているので言語アップデートが待ち遠しいです。

AtCoder ABC 133 B - Good Distance (Python)

競プロ AtCoder ABC133 B問題 200点 Python

irisruneです。しばらくコンテストは不参加が続きそうですが、今週はB～E問題まで扱う予定です。

問題

atcoder.jp

書いてあることを実装すれば解けますが、B問題にしては実装がやや重いです。

import sys
import math
import numpy as np


def input():
    return sys.stdin.readline().rstrip()


def dist(y, z, d):
    ret = 0.0
    for i in range(d):
        ret += pow(y[i] - z[i], 2)
    return pow(ret, 0.5)


def main():
    n, d = [int(e) for e in input().split()]
    x = [[int(e) for e in input().split()] for _ in range(n)]

    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            dist_yz = dist(x[i], x[j], d)
            if math.ceil(dist_yz) == math.floor(dist_yz):
                ans += 1
    print(ans)


main()

素直に、各点間の距離（の二乗ノルム）を求めた上で、距離が整数となるかを判定することで解くことができます。距離が整数となるかを判定する方法は、二乗根を求める関数がライブラリにある言語はそれを使えば楽ですし、公式解説のようにfor文で値を探索してもいいです（制約上、距離・ノルムの値がそれほど大きくならないため）。

おそらく実装がこれ以上に軽くなる解き方が存在しないため、二重ループ、ノルムの計算、二乗根（あるいはループによる探索）によりB問題らしからぬ実装の重さとなっています。

雑記

  • 最近のB問題が難しくなっているように思いましたが、以前から難しめの問題がたまに出ているようなので気のせいですね、多分。
  • 七夕は過ぎましたが、C++から行末のセミコロンを取っ払った言語が欲しいです。

AtCoder ABC 068 D - Decrease (Contestant ver.) (Python)

競プロ AtCoder ABC068 D問題 600点 Python

irisruneです。流石にABC132Fは難しすぎたので久々に過去問です。

問題

atcoder.jp

操作を行った結果として状態がどのように変わるか、どのような状態が停止状態となるかを把握することが重要です。

import sys
import numpy as np


def main():
    k = int(input())
    n = 50
    an = [n - 1 + (k // n) - (k % n) for _ in range(n)]
    for i in range(k % n):
        an[i] += n + 1
    print(n)
    print(*an)


main()

公式解説ではいきなり操作を逆から考えていますが、今回は初めに操作を実行順に考えて大筋を掴むアプローチを取りました。

まず、操作を行った結果どのように状態が変化するかを考えると、最も大きい要素の値がN減る一方で他の要素の値が1増えるため、数列の全要素の値の和は1減少することが簡単にわかります。

そこで数列の全要素の値の和に注目してみます。操作の停止条件は数列の最大値がN-1となることであるため、数列の全要素の値の和がN(N-1)より大きければ操作は停止しないということになります。

逆に数列の全要素の値の和がちょうどN(N-1)となるとき操作が停止する場合を考えます。この場合停止状態は数列の全要素の値がN-1となり、ここから操作を逆順に行うことで初期状態を求めます。

実際のプログラム上ではN=50とおき、数列の全要素に1回ずつ逆操作を行うと全要素の値が1ずつ増加することを利用して初期状態を求めています。

ただし、最後にK\mod N回逆操作を行う部分については、数列の初期状態の最大値が10^{16}+1000以下でなければならないことに注意して操作を行う必要があります。K\mod N回の逆操作をすべて数列の同一要素に対して実行すると、その要素の値が前述の条件を満たさないことがあるため、それぞれ別の要素に対して逆操作を行う必要があります。

なお、上記提出コードでは最後のK\mod N回分の逆操作を忠実にシミュレートしていないので少しわかりにくいかもしれません。

雑記

  • AtCoder Problemsを見ていると、合計220ACなのに100ACに到達している言語がないことに気付きました。
    • 実はただの飽き性なだけでは…？
    • 逆に言えば言語を変えるだけで違った体験ができるのはプログラミングのいいところですね。

AtCoder ABC 132 E - Hopscotch Addict (Kotlin)

競プロ AtCoder ABC132 E問題 500点 Kotlin

irisruneです。どうにか自力ACできたのでE問題も取り上げることにしました。

問題

atcoder.jp

AtCoder上に類題がほぼないらしく、正解率が低めだったそうです。最短経路問題を理解しているならば、試行錯誤によって解法を思いつくのは割と難しくないかもしれません。

import java.util.*
import java.util.zip.Inflater

const val INF = 1000000000

class Node(val num: Int) {
    val adj = mutableListOf<Node>()
    var dMod = mutableListOf(INF, INF, INF)

    fun adjAdd(v: Node) {
        adj.add(v)
    }
}

fun main(args: Array<String>){
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    val graph = mutableListOf(Node(0))
    for (i in 1 until n + 1) graph.add(Node(i))
    for (j in 0 until m) {
        val (u, v) = readLine()!!.split(" ").map(String::toInt)
        graph[u].adjAdd(graph[v])
    }

    val (s, t) = readLine()!!.split(" ").map(String::toInt)
    graph[s].dMod[0] = 0
    var depth = 1
    var queue = ArrayDeque(listOf(graph[s]))
    do {
        val nextQueue = ArrayDeque<Node>()
        while (queue.size > 0) {
            val v = queue.poll()
            v.adj.forEach {
                if (it.num == t && depth % 3 == 0) {
                    println(depth / 3)
                    return
                }
                if (it.dMod[depth % 3] > depth) {
                    it.dMod[depth % 3] = depth
                    nextQueue.add(it)
                }
            }
        }
        queue = nextQueue
        depth++
    } while (queue.size > 0)
    println(-1)
}

まずベースとなるのは最短経路問題であり、辺の重みが1で固定されていることからDFSあるいはBFSを用いるのが無難です。

次にこの問題の本質である、3回の移動をワンセットとすることについて考えます。3回の移動を1セットにするということは始点からの距離を3で割った剰余が0,1,2それぞれの場合について扱いが異なるということになります。これを実現する方法は例えば、

  • 各頂点を3つに分けて辺を適切に張り直す（公式解説の方法）。
  • 始点から（始点を含む）各頂点への距離を3で割った剰余によって3つ用意する（上記提出コードの方法）。

などが考えられます。今回用いたのは後者の方法だったわけですが、メリットとしては実装が比較的簡単なことが挙げられます。一方デメリットとしては、BFS（あるいはDFS）の探索打ち切り（枝刈り？）条件が少々複雑になることが挙げられます。これはどういうことかというと、例えば始点からの距離1（剰余1）が既に記録されている頂点に距離3（剰余0）となる経路が見つかった場合は探索が続行されますが、距離4（剰余1）となる経路が見つかった場合は探索が打ち切られるといった具合です。

また、アルゴリズムの計算量が定数倍部分でよくないのか、DFSで実装するとTLE（さらには恐らく再帰が深すぎたためにREも）してしまったためにBFSで実装することとなりました。

雑記

  • 色々考えるに、個人的にはリスト内包表記が使えてなおかつ高速な言語があると嬉しい気がしてきました。
    • リスト内包表記自体は好みが分かれる面もあるようです。

AtCoder ABC 132 D - Blue and Red Balls (Kotlin)

競プロ AtCoder ABC132 D問題 400点 Kotlin

irisruneです。残念ながら今回のコンテストは不参加でした、問題を見るとD問題以降がかなり難しくなっているようですね。

問題

atcoder.jp

考察（+剰余周りの実装）面の問題ですが、ABCが新形式になって以降のD問題としてはかなり難しいと思います。ただしPythonなどを使う場合は実行時間に余裕があることが救いかもしれません（パスカルの三角形を使う場合は余裕がないようです）。

const val MOD = 1000000007

fun COMinit(m: Int): Pair<List<Long>, List<Long>> {
    val fac = mutableListOf(1L, 1L)
    val finv = mutableListOf(1L, 1L)
    val inv = mutableListOf(1L, 1L)
    for (i in 2 until m + 1) {
        fac.add((fac[i - 1] * i) % MOD)
        inv.add(MOD - ((inv[MOD % i] * (MOD / i)) % MOD))
        finv.add((finv[i - 1] * inv[i]) % MOD)
    }
    return Pair(fac, finv)
}

fun COM(m: Int, r: Int, fac: List<Long>, finv: List<Long>): Long {
    if (m < r) return 0L
    if (m < 0 || r < 0) return 0L
    return (fac[m] * ((finv[r] * finv[m - r]) % MOD)) % MOD
}

fun main(args: Array<String>){
    val (n, k) = readLine()!!.split(" ").map(String::toInt)
    val (fac, finv) = COMinit(Math.max(n - k + 1, k - 1))
    for (i in 1 until k + 1) {
        println((COM(n - k + 1, i, fac, finv) * COM(k - 1, i - 1, fac, finv)) % MOD)
    }
}

まず、剰余を考慮した二項係数の計算についてこちらのブログから拝借して実装したため紹介いたします。

drken1215.hatenablog.com

こちらのアルゴリズムを見た時に何かの機会に使うかもしれないと思っていましたがそれが今回でした。初めパスカルの三角形を用いて求めることを考えていたわけですが、差の剰余の求め方をど忘れしていたため断念しました（今思えば差がマイナスになる場合を考慮してアルゴリズムを組めばいいだけでした）。よく考えたらパスカルの三角形で差を求める機会はないですね…何を見ていたんでしょうか。

実装面は剰余を考慮した二項係数の計算ができるかが全てのため、残りは考察面の問題となります。

ここで白状しますと、自分がこの問題を解いた流れとしては、

  • まず問題文と入出力例1から考察したところ二項係数を使うと推測し、二項係数を計算する関数を実装しました。
  • 計算結果と入出力例2とを見比べた結果、二項係数同士の乗算を行うことで解が導き出せることを突き止めました。

となっており、最終的に問題文ではなく入出力例から解いてしまいました。_{N-K+1}C_iを用いるところまでは考察できたのですが、_{K-1}C_{i-1}を用いることに気付いたのは入出力例との比較を行ったときだったわけです。

そんなわけでちゃんとしたアルゴリズムについては公式解説以上のことは説明できそうにないです。場合の数は苦手ではない（むしろ得意な方）と自覚していたのですが、ノートも取らずに考察できるほど甘い問題ではなかったということですね。

なお、_{K-1}C_{i-1}を用いることに後で気付いたために前計算の配列長が足りなかったり、二項係数同士の乗算の後に剰余を取るのを忘れていたりでWAとREを出しています。ペナルティ込みでも（4完で）水パフォ中位くらいの時間だと思います。

雑記

  • このD問題であれば3完で水パフォ出てもおかしくなさそうですが最高でも緑パフォ上位のようです、参加者のレベルも全体的に上がっていますね。
  • 今週はC問題がかなり簡単でE問題がかなり難しいため、久々に過去問を扱うことになりそうです。
  • GoやPythonを触った後だと、Kotlinは想像以上に入出力が面倒という課題がありました。言語に理想を求めるとなかなかキリがないですね…

AtCoder ABC 131 E - Friendships

競プロ AtCoder ABC131 E問題 500点 Go

irisruneです。今週またABCがあるようなのでなるべく参加できるように調整したいですね。

問題

atcoder.jp

最短距離というワードがありますが、探索系（実装系）の問題ではなく考察系の問題なので気を付けましょう。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, k := nextInt(), nextInt()
    diff := (((n - 1) * (n - 2)) / 2) - k
    if diff < 0 {
        fmt.Println(-1)
        return
    }
    fmt.Println((n - 1) + diff)
    for i := 1; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if diff > 0 {
                fmt.Println(i, j)
                diff--
            }
        }
        fmt.Println(i, n)
    }
}

まず、連結グラフという条件を無視した場合とはいえグラフの辺を配置する組み合わせは2^Nとなるので、全ての場合に対して考えるのは現実的ではありません。そのため、適当なグラフを作成して条件を満たすか確認するという手順を取ることはあり得ないので、探索系のアルゴリズムを使う機会はないです。

次に、Kの取り得る値の範囲について考えます。

最小値については単純で、完全グラフの場合すべての頂点対について最短距離が1となるのでK=0となります。

一方で最大値については少しアイデアが必要なため結果だけ出すと、公式解説で触れられているようにK\leq (((N(N-1))/2)-(N-1))=(((N-1)(N-2))/2)が示せ、また等号が成立する条件としてはある1点とそれ以外すべての点を結ぶ辺以外に辺を持たないスター型のグラフであることが挙げられます。

あとはKが与えられたときに条件を満たすグラフを求める手順ですが、スター型のグラフに(((N-1)(N-2))/2)-K本の辺を単純グラフとなる条件を守りながら追加するだけです。

スター型のグラフを構築するための辺も出力する必要があるため、先にスター型のグラフに必要な辺を出力してから追加の辺を出力する形の方がミスが少ないかもしれません。

雑記

  • とりあえず考えた結果としてAtCoderでは再びKotlinを使うことにしました。
    • （JVM系言語の宿命として一定のタイムロスはありますが）実行速度自体はおそらく問題がないこと、Javaライブラリが使えるため機能的に不足はおそらくないこと、記述が比較的簡易なことが利点ですね。
    • 欠点は入力処理の弱さで、それを補おうとすると長めのライブラリを貼ることになる点でしょうか。

AtCoder ABC 131 B - Bite Eating (Go)

競プロ AtCoder ABC131 B問題 200点 Go

irisruneです。ここ最近競技プログラミングに使う言語についてまた悩んでいるところです。

問題

atcoder.jp

実はD問題より解く時間がかかったので取り上げることにしました。絶対値の差ではなく差の絶対値なので誤読しないようにしましょう。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, l := nextInt(), nextInt()
    dWhole := 0
    for i := 1; i <= n; i++ {
        dWhole += l + i - 1
    }
    switch {
    case 0 <= -l && -l <= n-1:
        fmt.Println(dWhole)
    case -l < 0:
        fmt.Println(dWhole - l)
    default:
        fmt.Println(dWhole - (l + (n - 1)))
    }
}

N\leq200という条件なので、公式解説のように全部のリンゴの「味」の絶対値を求め、絶対値が最小となるリンゴを除いたものの「味」の総和を求めればよいです。計算量はO(N)なので余裕で間に合います。

ではなぜそうせずに計算量O(1)となる解き方をしたのかというと、

  • 当初「味」の絶対値の差と誤読していたので、先に「味」の総和を求める必要があると思い込んでいました。
  • 誤読に気付く前後辺りでGoのAbs関数がInt型を引数にも返り値にも取れないことに気付きました。
    • 今まで何回かやってるようにInt型のAbs関数を自作すればいいのですが、今回はAbs関数を実装するメリットもあまりなさそうです。
    • 別にキャストしてもいいのですが、3回キャストをするのでちょっと記述がごちゃごちゃしてあまり気に入らなかったです。
  • 既に「味」の総和を求めていたので、それを用いて解く手法を考えた結果として計算量O(1)となりました。

という流れでした。B問題だからこれでも10分くらいで済みましたが踏んだり蹴ったりですね…

ちなみに公式解説で触れられていない事柄として

なお、この値は一意に定まることが証明できます。

と問題文にありますが、

  • 「味」がすべて正の場合あるいはすべて負の場合は、食べるリンゴが異なるなら「味」の総和は異なるため求める値は一意に定まる。
  • 「味」が0となるリンゴがある場合はそのリンゴを食べるのが最適であるため求める値は一意に定まる。

といった風に証明することができます。

雑記

  • 始めに少し触れましたが、競技プログラミングに使う言語の選定に改めて難しさを感じています。
    • 例えばC++は、速度とライブラリについては申し分ないものの、記述量や他用途での使用機会に難があるイメージです。
    • 一方でPythonは、記述量やライブラリ、他用途での使用機会は申し分ないものの、速度に難がある上にスクリプト言語なのでCE（ペナルティ無し）ではなくRE（ペナルティ有り）を起こすリスクも考えています。
      • CEでなくREになるのはバージョンの差異が原因になることがほとんどですが、それ以外においてもPythonでは再帰などREになるケースが比較的多く感じます。
    • 速度と記述の簡易さを両立できる言語としてNimなども考えているのですが、開発中の言語ということでやや難があるという話も聞きます。
  • 言語アップデートで使用感の変わる言語もあると思いますが、いずれにせよ今何の言語を使うかという悩みは尽きませんね…

AtCoder ABC 131 D - Megalomania (Go)

競プロ AtCoder ABC131 D問題 400点 Go

irisruneです。新形式になって以降C,D問題が簡単になったとは思っていましたが、今回はかなり極端だった気がします。

問題

atcoder.jp

解答者にとってはどちらかと言えばMegalomaniaよりParanoiaみたいな問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type task struct {
    a int
    b int
}

type tasks []task

func (t tasks) Len() int {
    return len(t)
}

func (t tasks) Swap(i, j int) {
    t[i], t[j] = t[j], t[i]
}

func (t tasks) Less(i, j int) bool {
    switch {
    case t[i].b != t[j].b:
        return t[i].b < t[j].b
    default:
        return t[i].a < t[j].a
    }
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    var tasks tasks = make([]task, n)
    for i := 0; i < n; i++ {
        tasks[i].a, tasks[i].b = nextInt(), nextInt()
    }
    sort.Sort(tasks)

    time := 0
    for i := 0; i < n; i++ {
        time += tasks[i].a
        if time > tasks[i].b {
            fmt.Println("No")
            return
        }
    }
    fmt.Println("Yes")
}

方針は締め切りが早い仕事から順番に始めて、締め切りを過ぎる仕事が発生したら打ち切るだけです。

あまりにも安直すぎて裏がありそうに思えますがそんなことはないです。これを証明するのはやや難しいですが、証明しなくても正解できるのが競技プログラミングの特徴ですね。

そんなわけでアルゴリズム面ではあまりに解説することがないのですが、実装面についてはGo特有のソート実装の面倒さがネックになっていますね。Go1.8以降であればインタフェースの実装（Len,Swap,Lessメソッドの実装）を行わなくても構造体のソートが実装できるようになっているので、言語アップデートに期待したいところです。

雑記

  • 改めて思うに、Go言語は高級言語とは言い難いけど低級言語と言うほどでもない微妙な立場という感じですね。
  • 4完で茶パフォとはおそろしい時代になったものですね…
    • まだABCE（あるいはABDE）4完であれば水パフォが保証されていたようです。

AtCoder ABC 131 C - Anti-Division (Go)

競プロ AtCoder ABC131 C問題 300点 Go

irisruneです。久々にコンテストに参加した結果、5完で1242→1292とレートが伸びました。

問題

atcoder.jp

典型テクニックの寄せ集めのような問題だと思います。

なお、コンテスト本番でPythonを使う度胸はなかったので久々にGo言語で書いております。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func gcd(x, r int) int {
    if x < r {
        x, r = r, x
    }
    if x%r == 0 {
        return r
    }
    return gcd(r, x%r)
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    a, b, c, d := nextInt(), nextInt(), nextInt(), nextInt()
    a--
    cd := (c * d) / gcd(c, d)
    fmt.Println((b - ((b / c) + (b / d) - (b / cd))) - (a - ((a / c) + (a / d) - (a / cd))))
}

この問題のポイントは2つあります。1つ目のポイントはC,Dどちらでも割り切れない値の個数の求め方です。これは高校数学で習う、場合の数の性質を使うと、

  • C,Dどちらでも割り切れない値の個数=全体の値の個数-C,Dどちらかで割り切れる値の個数
  • C,Dどちらかで割り切れる値の個数=Cで割り切れる値の個数+Dで割り切れる値の個数-C,Dどちらでも割り切れる値の個数

となることが示せます。また、

  • C,Dどちらでも割り切れる値の個数=C,Dの最小公倍数で割り切れる値の個数
  • C,Dの最小公倍数=(C\times D) / C,Dの最大公約数

という性質があります。これらの性質を使うことでX以下の整数のうちC,Dどちらでも割り切れない値の個数を求めることができます。

2つ目のポイントは[A,B]に対してのC,Dどちらでも割り切れない値の個数の求め方です。これを求める方法は2通りあり、

  • [A,B]の各値に対し繰り返し処理などでC,Dどちらでも割り切れないことを判定する。
  • B以下の整数のうちC,Dどちらでも割り切れない値の個数とA未満の整数のうちC,Dどちらでも割り切れない値の個数との差を求める。

計算量について考えると前者はO(B)、後者はO(1)となりますが、A,B\leq10^{18}という条件から使えるアルゴリズムは後者のみとなります。

後者のアルゴリズムですが、前もって導き出したX以下の整数のうちC,Dどちらでも割り切れない値の個数を求める方法をA-1,Bに対して適用することで答えを求めることができます。

コードを見直してみると、最大公約数を求める部分は関数化していますが、X以下の整数のうちC,Dどちらでも割り切れない値の個数を求める関数も実装しておいた方がよりわかりやすかったと思います。

雑記

  • 実は最大公約数を求める関数はGoの標準パッケージにもあるのですが…どういうわけか多倍長変数パッケージに実装されているので、自作ライブラリを使った方が使いやすいような気がします。
    • Pythonを触った後なのでなおさら実感するのですが、max,min関数がInt型になかったりなど痒いところに手が届かないことが多いのが難点です。毎回自作ライブラリを貼ってもいいのですがコード長がえらいことになりがちですね。

Paiza プログラミング練習問題 S - 文字列収集 (Python)

Paiza プログラミング練習問題 Sランク相当 Python

irisruneです。先週に引き続き2度目のPaiza練習問題記事です。

問題

paiza.jp

前回とは対照的に、Sランク相当ではありますが正解率が高めとなっております。とはいえSランク問題に挑戦するような人が母数なのでそこまで簡単なわけではないです。

import sys
import numpy as np


def main():
    n, m = [int(x) for x in input().split()]
    dic = {}
    for i in range(n):
        s, p = input().split()
        for j in range(len(s)):
            subs = s[0:j+1]
            if subs in dic:
                dic[subs] += int(p)
            else:
                dic[subs] = int(p)
    for k in range(m):
        q = input()
        if q in dic:
            print(dic[q])
        else:
            print(0)


main()

複数のクエリに対する解答を求める問題の定石として、前処理を行うことでクエリ1個に対する計算量をO(1)で抑えるという手法があります。問題によっては二分探索などを用いてO(\log N)になることもありますね。

前処理には累積和やソートなどがありますが、今回は辞書型を用います。ある特定の文字列から始まる文字列の価値の和を辞書型として持つことで、クエリ1個に対する計算量をO(1)で抑えることができます。

ではそのような辞書を作ることができるのかについてですが、市場に出回っている文字列それぞれについて、先頭から1文字、2文字、…と繰り返し辞書に登録する、あるいは登録済みであれば価値の和を計算するといった手法で作成が可能です。

計算量についてですが、市場に出回っている文字列の長さの最大値をL_S(\leq100)とおくと辞書を作成する処理についてO(NL_S)、クエリに対する処理についてO(M)となるため、全体の計算量はO(NL_S+M)となり十分高速です。

雑記

  • 前処理なしの場合、ある文字列がある別の文字列から始まるかの判定にかかる計算量をO(\alpha)とおくとO(NM\alpha)となります。
    • これは制限時間に間に合うのでしょうか…？文字列長とO(\alpha)の関係性が分からないので何とも言えませんね。

AtCoder ABC 130 D - Enough Array (Python)

競プロ AtCoder ABC130 D問題 400点 Python

irisruneです。AtCoderで言語アップデートがあるそうで、色々な言語が使いやすくなるといいですね。

問題

atcoder.jp

連続部分列とみると累積和を取りたくなりませんか？累積和を取った場合は二分探索が手っ取り早いと思います。

import sys
import bisect
import numpy as np


def main():
    n, k = [int(e) for e in input().split()]
    a = [int(e) for e in input().split()]
    cumsum = [0]
    for i in range(n):
        cumsum.append(cumsum[i] + a[i])
    cumsum.sort()
    ans = 0
    for cs in cumsum:
        if cs < k:
            continue
        ans += bisect.bisect(cumsum, cs - k)
    print(ans)


main()

累積和を用いても連続部分列の和を全通り求めるのに計算量がO(N^2)かかってしまいます。しかし累積和の性質を使うことで、二分探索を用いて解くことができます。

詳しく説明すると、累積和C_iについてC_i-K\geq C_jとなる場合、C_i-C_j\geq Kとなります。これは累積和の性質よりある1つの連続部分列の和がK以上であることを示します（元の数列の各要素が負でないことが前提です）。そのため、累積和C_iをソートし、C_i-K\geq C_jとなる組の数を二分探索を用いて求めることで、全体の計算量をO(N\log N)で抑えることができます。

公式解説では尺取り法を勧められていますが、累積和が思いついて、かつライブラリが使える前提であれば二分探索でも楽に実装できると思います。

雑記

  • C問題は解く前に本質的な画像が流れてきてしまって全く自力でないACをしました。
  • PythonでTLEした問題をPyPyなら解けたという事例が今のところないので、PyPyの使いどころがわからないのが悩みです。
    • この記事の問題など、PyPy推奨らしいのですが自分のコードでは通りませんでした。
    • 記事にはしていないですが、逆にPythonで通るのにPyPyで通らないケースがあったのでPythonの方が信頼できてしまうんですよね…