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

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

ABC 123-C Five Transportations Go言語環境構築編(Go)

競プロ AtCoder ABC123 C問題 Go

irisruneです。最近のD問題難しくないですかね…

atcoder.jp

前回に引き続きGo言語ですが、今回は環境構築を行ったのでネタ作りのためその辺にも触れる予定です。

package main

import (
    "fmt"
    "math"
)

func minArray(arr []int, nCity int) int {
    var minCapa = 10000000000000000.0
    for i := 0; i < nCity; i++ {
        minCapa = math.Min(minCapa, float64(arr[i]))
    }
    return int(minCapa)
}

func main() {
    const nCity = 5
    var n, a, b, c, d, e int
    fmt.Scan(&n, &a, &b, &c, &d, &e)

    var minCapa = minArray([]int{a, b, c, d, e}, nCity)
    var maxTime int
    if n%minCapa == 0 {
        maxTime = n / minCapa
    } else {
        maxTime = (n / minCapa) + 1
    }

    fmt.Println(maxTime + nCity - 1)
}

正直に言うと、今回は公式の解説が丁寧なのでアルゴリズム面で書くことがないです。

一方で実装面はかなり苦戦しました。ポイントを挙げると、

  • 配列の構文が独特
  • forEachがない
  • Kotlinと違いmin関数の引数も戻り値もfloat64(double)型なのでキャストが必要
  • キャストがC言語ともKotlinとも違う構文

パッと思いついたのがこの辺です。C言語を使ってた頃に戻った気分ですね…

とりあえずコードレビューを。

  • Kotlinと違ってリストにmin関数を使って簡潔に記述できないので関数に退避したが、ループで済ませたのであまり意味がない。
  • 1016はわかりにくいのでconst INFとかで宣言しておいた方がよい。

Go言語を使った所感（続）

今回は環境構築を含む所感になります。環境構築の参照にしたサイトはこちら。

blog.okazuki.jp

  • （AtCoderとバージョンを揃えるため）当初バージョン1.6をインストールしたが、ツールのインストールが出来ずバージョン1.12.2を入れざるを得なかった。
  • 出来ないことが多いため記述が冗長になりがち。
  • for文やif文などやけに記号を省略させようとしてくる。
    • 型宣言もKotlinからコロンを省いたような感じ。
  • （無償の）IDEがない。

個人的にはIDEがないのは初心者向けではないと思うんですが、 初心者向けと言われがちなスクリプト言語のIDEってあまり思いつかないなあとか思ったりしました。 PythonはPyCharmとかJupyter Notebookとかありますが。

でも今はVSCodeが使えるだけでも有難いですね。あとは外部ツールが結構多いのでそれを使いこなせれば快適な環境になりそう…あれ？それはもう初心者とは程遠いのでは

雑記

  • Kotlin使ってるから猶更ですが、Go言語のIDEまで出してるJetbrains社はすごいなあと思います。
  • Kotlinがぬるま湯すぎたのかGo言語がどんどん難しく思えてきます。

AGC 024-A Fairness で新しい言語に挑戦してみる(Go)

競プロ AtCoder AGC024 A問題 Go

irisruneです。今回はかなり軽めの記事です。

社内で今プログラミング言語始めるなら何がいいかという話題があり、 とりあえず調べてたらGo言語が割とおすすめに挙がっていたので試しに使ってみました。

https://atcoder.jp/contests/agc024/tasks/agc024_a

この問題、勘のいい人ならUnfairになるケースがないのでは？という察しが付くのではないでしょうか。 それどころか32bit整数で済んでしまう非常にあっさりした問題です。 嘘吐きました、Kは明らかに32bit整数では済まないですね。

前回の問題と配点逆なのではと思いましたがでも200点だと流石に難しいですね。

package main

import "fmt"

func main() {
    var a, b, c, k int
    fmt.Scan(&a, &b, &c, &k)
    if k % 2 == 0{
        fmt.Println(a - b)
    }else{
        fmt.Println(b - a)
    }
}

Go言語についての話は後に回すとして、方針について軽く説明を。

解説のように3人のもつ値をA+x,A,Bとおけなくても、A,B,Cとおいて2回操作を行うと解答に辿り着けると思います。具体的にどうなるかというと、

  • 0回目の操作後：答えはA-Bになる。
  • 1回目の操作後：B+C,C+A,A+Bになるので答えはB-Aになる。
  • 2回目の操作後：2A+B+C,A+2B+C,A+B+2Cになるので答えはA-Bになる。

ここから単純にA-BとB-Aの繰り返しになると結論付けてもいいです。もう少し厳密に考えると、 2回目の操作後はA+(A+B+C),B+(A+B+C),C+(A+B+C)となるわけですが、 これは結局初期状態と同じであると考えられます。

コードレビューは今回も見送ります。

Go言語を使った所感

  • 公式ページで簡単にコードを試せるのはプログラミング初心者への導入としてはよいと思いました。
    • さすがに競プロに使うなら（今回のコード程度でも）自前の環境を使うべきだと思います。
  • 実行速度や関数の機能はC言語に近いものがある一方で変数の宣言がKotlinっぽかったりすると思いました。
  • 今回のような簡単なコードだとC言語とそれほど見分けがつかないですね…
  • （64bit環境なら）雑にintを使うだけで64bit整数になるのは楽だと思いました。

C言語を扱った経験があればかなり入りやすい言語だとは思いますが、 スクリプト言語しか（スクリプト言語も）触ったことがない人に向いているかはもう少し触ってみないと判断できないですね。

雑記

  • テーマをデフォルトから差し替えてみましたが、コードを黒背景で表示する方法がわからなくて困っています。
  • 次のRatedまでには500点問題には手が出るようにしたいですね。

AGC 023-A Zero-Sum Ranges に失敗談を添えて(Kotlin/Java)

競プロ AtCoder AGC023 A問題 Kotlin Java

irisruneです。令和と聞いてこの問題が出てくる人はすごいと思いました。 今回は4提出分のコードがあるのでまた長いです。

atcoder.jp

約1年前の問題で、自分がAtCoderを始めて1月もしないうちに挑戦したそして玉砕した問題です。 この記事で触れました累積和の存在を初めて認識した問題でもあります。

まずは、累積和を使うことだけ覚えていた今Kotlinで解いたコードを。

fun combination2(m : Long) : Long{
    return m * (m - 1L) / 2L
}

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val la = readLine()!!.split(" ").map(String::toLong)

    val lCumSum = mutableListOf(0L)
    for(i in 1..n){
        lCumSum.add(lCumSum[i - 1] + la[i - 1])
    }
    lCumSum.sort()
    var retValue = 0L
    var elm = lCumSum[0]
    var cntSame = 1L
    for(i in 1..n){
        if(lCumSum[i] == elm){
            cntSame++
            if(i == n) retValue += combination2(cntSame)
        }
        else{
            retValue += combination2(cntSame)
            elm = lCumSum[i]
            cntSame = 1L
        }
    }
    println(retValue)
}

累積和を求めただけでは終わらない200点ではない問題なんですが、解説通りの手法に行き着く普通…のコードですね。 というわけで、1年前の自分のコードを見てみたいと思います。

なお、当時はJavaを使っていました。 まずは開始30分ほどで提出したこちらのコード。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.next());

        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }

        int count = 0;
        for(int i = 0; i < n; i++) {
            int sum = 0;
            for(int j = i; j < n; j++) {
                sum += a[j];
                if(sum == 0) {
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

これは愚直に解いてますね。当然ですがこれではO(N^2)時間かかってしまいます。

次に、コンテスト終了3分後に提出したコードを。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);


        int n = Integer.parseInt(sc.next());

        long[] a = new long[n];
        for(int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sc.next());
        }

        int count = 0;
        long[] sumAbsPart = new long[n];
        long sumAbs = 0;
        for(int i = n - 1; i >= 0; i--) {
            sumAbsPart[i] = sumAbs;
            sumAbs += Math.abs(a[i]);
        }
        for(int i = 0; i < n; i++) {
            long sum = 0;
            for(int j = i; j < n; j++) {
                sum += a[j];
                if(sum == 0) {
                    count++;
                }else if(Math.abs(sum) > sumAbsPart[i]) {
                    break;
                }
            }
        }

        System.out.println(count);

    }
}

こちらは根本は変えずに、枝刈りをしてTLEを解消しようとしていますね。結果としてはむしろTLEが増えてしまいました。

最後に、おそらく解説を見た後で書いたであろうコードを。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);


        int n = Integer.parseInt(sc.next());

        long[] a = new long[n];
        for(int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sc.next());
        }

        ArrayList<Long> s = new ArrayList<Long>();
        s.add((long) 0);
        for(int i = 0; i < n; i++) {
            s.add(s.get(i) + a[i]);
        }
        Collections.sort(s);

        int count = 0;
        for(int i = 0; i < n + 1; i++) {
            long base = s.get(i);
            for(int j = i + 1; j < n + 1; j++) {
                if(s.get(j) == base) {
                    count++;
                }else {
                    break;
                }
            }
        }
        System.out.println(count);

    }
}

解説を見て累積和を求める部分までは理解できたようですが、その後の処理がまずいですね。 どういうわけか_{M}C_2を求めるのに数式ではなく（二重目の）ループを用いています。 結局これでは最悪計算量がO(N^2)かかってしまいます（最初のコードに比べTLEは減りました）。

以上、失敗談でした。今回はコードレビューはお休みしてポエムこの問題を解き直して思うところを。

  • 1年前は解説を見ても上手く解けなかった問題が普通に解けたのは成長してます。
  • 1年前のしかも最近見ていないJavaコードを読んでて、コードの可読性は本当に重要と感じました。

雑記

  • 令和発表直後に開かれた0WAバチャコン（ペナルティ10000分）の発想力はすごいと思いました。
  • 競プロに有利らしいからとJavaからC++に乗り換えたのに、今はKotlinで競プロしてる辺り因果だなあと思います。
  • chokudaiさんが弊社のJobs募集に触れていたのに今更気づいて驚きました。

AGC 122-D We Like AGC (Kotlin)

競プロ AtCoder ABC122 D問題 Kotlin

irisruneです。500点問題が厳しいので予定を変更して先週扱わなかったこの問題を。コードがかなり長いです。

atcoder.jp

Twitterで検索をしたら糸口というかほぼ答えが見つかったので解いてみました。 …が方針変更が激しくて変数名とかがめちゃくちゃになってます。

fun initList(lmChar : MutableList<MutableList<MutableList<MutableList<MutableList<Long>>>>>){
    val l3 = mutableListOf<MutableList<MutableList<MutableList<Long>>>>()
    for(b3 in 0..3) {
        val l2 = mutableListOf<MutableList<MutableList<Long>>>()
        for (b2 in 0..3) {
            val l1 = mutableListOf<MutableList<Long>>()
            for (b1 in 0..3) {
                val l0 = mutableListOf<Long>()
                for (b0 in 0..3) {
                    if(b0 + b1 + b2 + b3 == 0) l0.add(1L)
                    else l0.add(0L)
                }
                l1.add(l0)
            }
            l2.add(l1)
        }
        l3.add(l2)
    }
    lmChar.add(l3)
}

fun nextStep(lmChar : MutableList<MutableList<MutableList<MutableList<MutableList<Long>>>>>, i : Int){
    val l3 = mutableListOf<MutableList<MutableList<MutableList<Long>>>>()
    for(b3 in 0..3) {
        val l2 = mutableListOf<MutableList<MutableList<Long>>>()
        for (b2 in 0..3) {
            val l1 = mutableListOf<MutableList<Long>>()
            for (b1 in 0..3) {
                val l0 = mutableListOf<Long>()
                for (b0 in 0..3) {
                    val flag = calculator(listOf(b3, b2, b1, b0))
                    val value =
                        lmChar[i - 1][1][b3][b2][b1] + lmChar[i - 1][2][b3][b2][b1] + lmChar[i - 1][3][b3][b2][b1] + lmChar[i - 1][0][b3][b2][b1]
                    l0.add((value % 1000000007L) * flag)
                }
                l1.add(l0)
            }
            l2.add(l1)
        }
        l3.add(l2)
    }
    lmChar.add(l3)
}

fun calculator(l : List<Int>) : Long{
    if(l[0] == 1 && l[1] == 2 && l[2] == 3) return 0L
    if(l[0] == 2 && l[1] == 1 && l[2] == 3) return 0L
    if(l[0] == 1 && l[1] == 3 && l[2] == 2) return 0L
    if(l[1] == 1 && l[2] == 2 && l[3] == 3) return 0L
    if(l[1] == 2 && l[2] == 1 && l[3] == 3) return 0L
    if(l[1] == 1 && l[2] == 3 && l[3] == 2) return 0L
    if(l[0] == 1 && l[2] == 2 && l[3] == 3) return 0L
    if(l[0] == 1 && l[1] == 2 && l[3] == 3) return 0L
    return 1L
}

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val lmChar = mutableListOf<MutableList<MutableList<MutableList<MutableList<Long>>>>>()
    initList(lmChar)
    for(i in 1..n) nextStep(lmChar, i)
    var retValue = 0L
    for(b3 in 0..3){
        for(b2 in 0..3){
            for(b1 in 0..3){
                for(b0 in 0..3){
                    retValue += lmChar[n][b3][b2][b1][b0]
                    retValue %= 1000000007L
                }
            }
        }
    }
    println(retValue)
}

『後ろ3文字を使ってDPする』という解法を自分なりに解釈して実装した結果がこれです。 とりあえず躓いたポイントは、

  • Char型でfor文を回す方法がわからなかったので'A'=1,'G'=2,'C'=3,'T'=0としてInt型で扱うことに。
  • 当初はMutableList<MutableMap<List<Int>, Long>>を使っていたが計算が上手くいかなかったので多次元リストに。
    • 結論を言えば原因は次のポイント。
  • 関数nextStep内でvalueを計算する際、式右辺の途中で改行が混ざると正しく計算できなかったので改行をやめた。

自力でDPを思いつかなかった所から躓いてるわけですが、この問題は実装力もかなり求められてますね… Kotlinの仕様を把握しきれていない点もあると思うので精進しましょう。

コードレビュー

  • lmCharという変数名が実態と全く乖離している。
    • 当初はChar型で扱う予定だったがfor文が回せないとコードが肥大化するので断念。
    • Mapを使う予定だったが多次元Listにした。
  • 3/2/1文字前を表す変数としてb3/2/1と名付けているが意図がわかりにくい。
    • bはbackではなくbaseだったりもする。

そもそものデータ構造の使い方とかがまずいのでコードレビューする箇所にキリがないですね。

雑記

  • 同作問者のABC119-CでもそうでしたがDFSが出てこないのを何とかしたいです。
  • エクサウィザーズ2019は配点見て人権がないと思ってましたがAB早解きでパフォが盛れるコンテストでしたね。
  • 今週は過去問を扱うことになりそうです。

AGC 032 A Limited Insertion (Kotlin)

競プロ AtCoder AGC032 A問題 Kotlin

irisruneです。今回は少し長めに書いてみました。

atcoder.jp

この問題は解き方は明確なんですが、 そこにたどり着くまでが長かったので思考面に重点を当てたいと思います。前回言った糸口は嘘でした。

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val ln = readLine()!!.split(" ").map(String::toInt).toMutableList()
    val lRet = mutableListOf<Int>()
    while(ln.size > 0){
        for(i in ln.size.downTo(0)){
            if(i == 0){
                println(-1)
                return
            }
            if(ln[i - 1] == i){
                lRet.add(ln[i - 1])
                ln.removeAt(i - 1)
                break
            }
        }
    }
    lRet.reverse()
    lRet.forEach{
        println(it)
    }
}

解き方は解説の通り、数列の（1始まりの）インデックスと項の値が一致するもののうち、 一番右の（インデックスが大きい）ものを取り除いて出力の末尾に加える操作を繰り返せばいいだけです。 操作ができなくなった時点で数列が空でなければ元の数列は作れないことになります。

…なんですが、この問題は割と入力例が簡単すぎて違う解法でもできそうに見えてしまうのが罠だと思います。 例えば、入力例3の

9
1 1 1 2 2 1 2 3 2

については、

1 1 122 1232

というように1始まりのブロックに分けて考えることでなんとなく出力例3が導けそうに見えてきます。

ですが、入力として例えば

5
1 2 3 2 4

が与えられたとき、数列を前から舐めるだけでは

1
2
2
4
3

を導くのは困難だと思います。少なくとも自分は方法が思いつきませんでした。

ここでなぜ数列を前から舐める方法が困難になるかを考えることにします。そもそも入力された数列が作成できないケースはというと、例えば

5
1 2 4 2 3

のように、インデックスより大きな値を持つ項が存在する数列は作ることができません。 逆に、この条件さえ満たさない数列は作成できてしまうということがNが小さいケースで試すと見えてきます。証明はできてません。

そのため作成される数列の自由度が高いことから、数列を前から舐めながら作成手順を導き出すのは困難になってしまいます。

そこから解答に行き着くまでですが、自分の場合は

1 2 3 2 4
1 2 2 4
1 2 2
1 2
1

という形が急に見えたので解くことができました。ここまで書いて結局フィーリングですか？

とりあえず今回の問題の教訓は提示された入力例以外にも怪しいものを試してみることだと思います。TLEがネックになりそうな問題には使えないですが…

コードレビュー

  • 調べるのが面倒だったのでループにラベルを付けていないおかげで作成手順がない場合の処理がやや強引。
  • これまた調べるのが面倒だったので入力リストのインデックスを1始まりにしていないので項の値と比較する際にズレが生じている。
    • 要素1のリストを用意してplusメソッドを使えばいい。その他部分は適宜修正。
val ln = listOf(-1).plus(readLine()!!.split(" ").map(String::toInt)).toMutableList()

雑記

  • 逆詐称でもない400点問題で早解きしてもパフォ1300行かないのはレベルが高すぎますね…
  • 次回記事は明日開催のエクサウィザーズ2019を扱う予定です。リアルタイムで参加できるかは未定ですが。

ABC 122-C GeT AC (Kotlin)

競プロ AtCoder ABC122 C問題 Kotlin

irisruneです。先週のAGCはA問題早解きで1300出ないらしいしABCはD問題が難しすぎるし過酷ですね…

atcoder.jp

この問題は数列の部分和を求める問題と（ほぼ）等価です。つまり典型問題ですね。

あらかじめ数列（文字列）の先頭から各インデックスまでの累積和（解）を求めておくことで、 Q個のクエリそれぞれに対して解をO(1)時間で求めることができます。

fun main(args: Array<String>){
    val(n, q) = readLine()!!.split(" ").map(String::toInt)
    val s = readLine()!!
    val cumSum = mutableListOf(0)
    for(i in 1..(n - 1)){
        if(s.substring(i - 1, i + 1) == "AC") cumSum.add(cumSum[i - 1] + 1)
        else cumSum.add(cumSum[i - 1])
    }
    for(i in 1..q){
        val(l, r) = readLine()!!.split(" ").map(String::toInt)
        println(
            when {
                l == 1 -> cumSum[r - 1]
                s.substring(l - 2, l) == "AC" -> cumSum[r - 1] - cumSum[l - 2] - 1
                else -> cumSum[r - 1] - cumSum[l - 2]
            }
        )
    }
}

結論から言えば解説と同様に

println(cumSum[r - 1] - cumSum[l - 2])

で出力部分は事足ります。

今回一番悩んだのはこの部分で、累積和の差から解を求める際に左側の区切り位置がちょうど"AC"の間だった場合 1を引く必要があると考えた結果、上記のように出力部分が複雑になってしまいました。

実際は2文字セットで解を求めていく関係上、累積和のインデックスがズレるようです？ まだ今一つ理解しきれていません。

今回のコードレビューは特筆するほどでもないですが、

  • 累積和を求める部分のif文でKotlin記法を用いて簡略化できる。
    • 出力部分のようにwhen文に置き換えることもできる（やってみると余計読みにくいという感想）。

雑記

  • AGC032-Aについてはおそらく糸口は掴めているので近いうちに。
  • ABC122-Dについては正直に言って解法がわかりません。愚直に場合の数を求めるのはほぼ不可能ですよね…

ABC119 D Lazy Faith を二分探索を使わずに解く(C++)

競プロ AtCoder ABC119 D問題 C++

irisruneです。一昨日のAGCは所用で参加できなかったので今日も過去問になります。

前回と同様、今回もC++での提出コードです。

https://atcoder.jp/contests/abc119/tasks/abc119_d

この問題のポイントは

  1. x_iに（東西それぞれで）最寄りの神社と寺を高速で求める方法
  2. 最寄りの神社と寺から要求された解を求める方法

…らしいです1。自分は完全に1.で引っかかった口でした。

回答と方針

割と思いつきやすい二分探索が模範解答だったわけですが、自分の回答はというと…

#include <bits/stdc++.h>
using namespace std;

int a, b, q;
vector<long long> va;
vector<long long> vb;
int idxA, idxB;

class X {
    public : int idx;
    public : long long x;
    public : long long l;
    X(int i, long long s){
        idx = i;
        x = s;
    }
};
vector<X> vX;

bool cmp_idx(const X &a, const X &b){
    return a.idx < b.idx;
}

bool cmp_x(const X &a, const X &b){
    return a.x < b.x;
}

void init() {
    cin >> a >> b >> q;
    for(int i = 0; i < a; i++){
        long long s;
        cin >> s;
        va.push_back(s);
    }
    for(int i = 0; i < b; i++){
        long long s;
        cin >> s;
        vb.push_back(s);
    }
    for(int i = 0; i < q; i++){
        long long x;
        cin >> x;
        X X(i, x);
        vX.push_back(X);
    }
    sort(vX.begin(), vX.end(), cmp_x);
}

long long solve(long long x){
    for(int i = idxA; i < a; i++){
        if(x < va.at(i)) break;
        idxA++;
    }
    for(int i = idxB; i < b; i++){
        if(x < vb.at(i)) break;
        idxB++;
    }
    long long westA, eastA, westB, eastB;
    if(idxA == 0) westA = -50000000000;
    else westA = va.at(idxA - 1);
    if(idxA == a) eastA = 50000000000;
    else eastA = va.at(idxA);
    if(idxB == 0) westB = -50000000000;
    else westB = vb.at(idxB - 1);
    if(idxB == b) eastB = 50000000000;
    else eastB = vb.at(idxB);
    long long minL = max(x - westA, x - westB);
    minL = min(minL, (eastA - x) + (eastA - westB));
    minL = min(minL, (x - westB) + (eastA - westB));
    minL = min(minL, (eastB - x) + (eastB - westA));
    minL = min(minL, (x - westA) + (eastB - westA));
    minL = min(minL, max(eastA - x, eastB - x));
    return minL;
}

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

    init();

    for(int i = 0; i < q; i++){
        vX.at(i).l = solve(vX.at(i).x);
    }
    sort(vX.begin(), vX.end(), cmp_idx);

    for(int i = 0; i < q; i++){
        cout << vX.at(i).l << "\n";
    }
    return 0;
}

一応方針を説明すると、

  1. iを保持しながらx_iを西から順にソートする。
  2. x_iの西最寄りの神社と寺を記録する変数をおく。
  3. 2.の変数に記録しながらソートした順にx_iについて問題を解く。
  4. x_iをiでソートしてから出力する。

という感じです。

こんな手順でなぜ解けるか

  • 単純に線形探索をする →各x_iにつきO(Q)の計算量がかかる →全体でO(Q^2)になってしまう →TLEしてしまう

  • x_iを西から順番に見て線形探索をする →(1\leq i \leq Q)について計算量の合計がO(Q)になる →TLEしない

という形になります。前回のABC119-Cといい全体の計算量を抑える手法をよく使いますね、今回は明らかに嘘解法ですが。

ちなみにソート自体にO(Q\log Q)かかるので二分探索を使う手法と計算量は（オーダーの上では）同じです。x_iが予めソートされているならもっと速いですね。

コードレビュー

  • グローバル変数の濫用。
  • INFがマジックナンバーに見えるので変数（定数）を使った方がよい。

雑記

  • Kotlinのコードに比べてC++のコードが随分長い気がするのは気のせいでしょうか。
  • Kotlinで二分探索を用いて解いてみましたが、入力にreadLine()を用いても1400msくらいに落ち着きました。

  1. https://twitter.com/evima0/status/1099672794969690112↩

ABC119 C Synthetic Kadomatsu (C++)

競プロ AtCoder ABC119 C問題 C++

irisruneです。今回はC++使ってた頃のコンテストなのでC++です。

atcoder.jp

自分が水色になった回でもある大変愉快な問題ですね。解くためのポイントは大きく2つあって、

  1. O(4^N)の全探索アルゴリズムに持ち込めるか
  2. 1.を実装できるか

まず1.について、この問題DPっぽいですがC問題でDPは滅多にない…と思うので除外。まだ全然過去問埋まってないからわからないですね。

それでなくても3\leq N\leq 8という不自然に小さい問題規模に着目すれば全探索に行き着くことはできると思います。 問題はO(4^N)にモデル変換できるかなんですが…理屈ではよくわからないです。 解説見てもフィーリングとしか言えない。

とりあえず1.を達成できたことにします。では全探索を実装するわけですが…とりあえず自分のコードを。

#include <bits/stdc++.h>
using namespace std;

int n, a, b, c;
vector<int> vl;
vector<int> vx;

void init() {
    cin >> n >> a >> b >> c;
    for(int i = 0; i < n; i++){
        int l;
        cin >> l;
        vl.push_back(l);
    }
}

int solveSub2(){
    int MP = -30;
    int la = 0;
    int lb = 0;
    int lc = 0;
    for(int k = 0; k < n; k++){
        if(vx.at(k) == 1){
            la += vl.at(k);
            MP += 10;
        }
        else if(vx.at(k) == 2){
            lb += vl.at(k);
            MP += 10;
        }
        else if(vx.at(k) == 3){
            lc += vl.at(k);
            MP += 10;
        }
    }
    if(la == 0 || lb == 0 || lc == 0) return 3000;
    MP += abs(a - la) + abs(b - lb) + abs(c - lc);
    return MP;
}

int solveSub1(int idx){
    int minMP = 3000;
    for(int j = 0; j < 4; j++){
        vx.at(idx) = j;
        if(idx < n - 1) minMP = min(minMP, solveSub1(idx + 1));
        else minMP = min(minMP, solveSub2());
    }
    return minMP;
}

int solve(){
    for(int i = 0; i < n; i++){
        vx.push_back(0);
    }
    return solveSub1(0);
}

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

    init();

    cout << solve() << "\n";

    return 0;
}

突っ込みどころは多いですがそこは後でコードレビューしましょう。

原理としてはそれぞれの竹の用途を0,1,2,3に当てはめ、そこからMPを求めて最小値を取るだけです。 どうしてこういう解き方をしたかというと、_n\text{C}_rを列挙してそれを用いるようなコードを過去に見たことがあるからでした。

一方、公式解説ではDFSで実装してるので大変スマートですね。こういう基本的な探索アルゴリズムを覚えておくことも重要だと思いました。

最後に今回のコードレビュー。

  • 関数名が適当すぎる。
  • 関数solve()の存在意義がない。
  • 竹の用途のリストを作りながらMPを求めるより、いったん『竹の用途のリスト』のリストを作って順番にMPを求める方が明確。
  • なんでもかんでもグローバル変数にするのは楽だけどよくない。

雑記

  • 明日のAGCは冷えないことを祈ります。
  • マラソンコンテストの初心者記事とかも書いてみたいですね。

全国統一プログラミング王決定戦予選 C Different Strokes をKotlinで

競プロ AtCoder 全国統一プログラミング王決定戦予選 企業コン400点 Kotlin

irisruneです。どのくらいの重さの問題を扱えばいいか毎回悩みどころです。

今回は趣向を変えまして1月開催の企業コンについて、C問題までは解けたのでC問題を。

atcoder.jp

個人的な感触では400点にしては簡単な方でしょうか。 ABC121 Cと比べるとソートの実装力よりは発想力の方に比重があると思います。

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val ll = mutableListOf<List<Long>>()
    for(i in 0..(n - 1)){
        val (a, b) = readLine()!!.split(" ").map(String::toLong)
        val l = listOf(a, b, a + b)
        ll.add(l)
    }
    ll.sortBy{it[2] * -1}
    var aSum = 0L
    var bSum = 0L
    for(i in 0..(n - 1)){
        if(i % 2 == 0) aSum += ll[i][0]
        else bSum += ll[i][1]
    }
    println(aSum - bSum)
}

解法としては大体解説と同じなので、そこに至った経緯について。

「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値（以下スコアと呼ぶ） を最大化したいので、相手が幸福度を得るとその幸福度分スコアが下がるとみなすことができます。

一方、ルール上自分が食べた料理を相手が食べることはできないので自分が料理を食べることで 相手がその料理から得る幸福度を0にすることができます。

以上のことから、料理を食べることで自分が得る幸福度と相手が得るはずだった幸福度の和を 疑似的なスコアとみなすことができます。そのため、自分と相手の幸福度の和が高い料理を食べるのが 高橋くんと青木さん双方にとって最適戦略となります。

あとは幸福度の和で料理をソートし、それに対して愚直に最適戦略をとった際のスコアの計算を行えば解答を導き出すことができます。

ゲーム理論的に説明したかったのですが少し本を読んだ程度なのであまりうまくいかないですね。

今回のコードレビューについてですが、配列インデックスの0や1がマジックナンバーっぽくなってるので 辞書型を使えば可読性が上がるかもしれないです。

雑記

  • 最近忙しいため更新日を守れない可能性があります（予防線）。
  • ABC117のC問題もD問題も解けなくてつらい。

AGC031 A Colorful Subsequence をKotlinで

競プロ AtCoder Kotlin AGC031 A問題

irisruneです。皆さんAGC031はどうでしたか？自分は冷えました。

結局コンテストでもKotlinを使うことにしました。今回は1完だったのでA問題について。

atcoder.jp

とりあえず200点ではないですね…300点で少し難しいくらいですかね？ なお3WAでした、0WAでも冷えてますが。

fun main(args: Array<String>){
    val len = readLine()!!.toInt()
    val s = readLine()!!
    val lc = mutableListOf<Char>()
    for(i in 0..(len - 1)){
        lc.add(s[i])
    }
    lc.sort()
    var ret = 1L
    var i = 0
    while(i < len){
        val c = lc[i]
        var cnt = 1L
        while(++i < len){
            if(lc[i] != c) break
            cnt++
        }
        ret = (ret * (cnt + 1L)) % 1000000007L
    }
    println(ret - 1)
}

解説にもある通り、各文字種について出てくる文字数をカウントすれば解くことができます。 本来は2^N-1通りになるのが制約条件によって変形して(\text{文字数}+1)^\text{文字種数}-1通りになるわけですね。

ということは例えば、ababaとaabbbのように文字列の順序を変えてしまっても答えは同じになります。 そんなわけで今回は文字列を文字の配列に分解してソートしてから文字数をカウントすることにしました。

一応このコードでも解けるのですが色々な意味でよいアルゴリズムではないと思います。理由は大きく2つあって、

  • 計算量がO(N\log N)かかってしまう。N\leq10^5程度なのでこれでも通るが制約次第では厳しくなる。
    • 一応、N\leq10^7までなら26回走査するよりは速い。それ以上だと26回走査してもダメそう。
  • 文字（の配）列を走査しながら文字種ごとの文字数をカウントするのでインデックスの管理が難しい。
    • 3WAの最大の原因。
      • 10^9+7で割った余りに慣れていなくて、WA出た原因がこの辺にあると勘違いしてたのも敗因。

多分、アルゴリズムとしてよい順に並べると

  • 1回走査しながら文字種をインデックスにしたdictionaryなりmapなりで文字数を管理する。
  • 26回走査してアルファベット26文字の文字数を調べる。
  • 文字列をソートして頭から走査しつつ文字数を調べる（このコード）。

こんな感じになると思うんですよね。それでも解ければいいって主張しても3WAなのが悲しいですね。

アルゴリズムについてはこの辺にしておいて、今回のコードレビューは…

  • コードの簡略化を意識しすぎてインデックスの管理がわかりにくい。

このくらいでしょうか。やっぱりアルゴリズムがよくない

雑記

  • 今回はA問題早解きでもパフォ1400行かないのでB問題を解く必要があったようです。（自信ない人は出ない/提出しないので）AGCは厳しいですね。

  • C問題は順列の意味を履き違えて解けると勘違いしてましたが解けませんでした。重複ありだったら簡単すぎますね…

ABC120 D Decayed BridgesをKotlinで

競プロ AtCoder Kotlin ABC120 D問題

irisruneです。今回もKotlinで解いた過去問についてですが、少し重い問題なので1問だけです。

atcoder.jp

橋を減らしていくのではなく逆に増やしていくという発想ができれば愚直に解くことはできると思います。そして時間内に解くのはUnion-Findを知らなくてもできます（できました）、でもD問題にしては実装も重い気がします。

class Bridge(val a : Int, val b : Int)
class Island(var group : Int)

fun moveGroup(s : MutableList<Int>, t : MutableList<Int>, lIsland : MutableList<Island>, group : Int){
    for(i in 0..(s.size - 1)){
        t.add(s[0])
        lIsland[s[0]].group = group
        s.removeAt(0)
    }
}

fun main(args: Array<String>){
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    var lIsland = mutableListOf<Island>()
    var lGroup : MutableList<MutableList<Int>> = mutableListOf()
    for(i in 0..(n - 1)){
        lIsland.add(Island(i))
        val iLGroup = mutableListOf(i)
        lGroup.add(iLGroup)
    }
    var lBridge = mutableListOf<Bridge>()
    for(i in 0..(m - 1)){
        val(a, b) = readLine()!!.split(" ").map(String::toInt)
        lBridge.add(Bridge(a - 1, b - 1))
    }
    var lRet = mutableListOf<Long>()
    lRet.add(n.toLong() * (n - 1).toLong() / 2L)
    for(i in (m - 1) downTo 1){
        val groupA = lIsland[lBridge[i].a].group
        val groupB = lIsland[lBridge[i].b].group
        if(groupA == groupB){
            lRet.add(lRet[(m - 1) - i])
        }else{
            lRet.add(lRet[(m - 1) - i] - (lGroup[groupA].size * lGroup[groupB].size))
            if(lGroup[groupA].size >= lGroup[groupB].size) moveGroup(lGroup[groupB], lGroup[groupA], lIsland, groupA)
            else moveGroup(lGroup[groupA], lGroup[groupB], lIsland, groupB)
        }
    }
    for(i in (m - 1) downTo 0){
        println(lRet[i])
    }
}

この問題の実装面での課題は解説にもある通り、

  1. 頂点uが属するグループと頂点vが属するグループを併合し、同じグループにする操作
  2. 頂点vが属するグループ番号を得る操作
  3. 頂点vが属するグループと同じグループに属する頂点数を得る操作

以上の操作をどのように実装するかになります。愚直に実装するとO(N+M)時間かかる操作が出てしまうので（よくわかってない）、全体でO(M(N+M))時間かかってしまい到底時間内には解けません。

今回自分はどのようにこれらの操作について実装したかというと、

  1. 頂点数の少ないグループの頂点を頂点数の多いグループに移動させる
    • 全体でO(N)時間に。
  2. 頂点にグループ番号を持たせる
    • 1操作あたりO(1)時間に。
  3. グループごとにリストを作ってそこに頂点を入れてsizeを用いる
    • 1操作あたりO(1)時間に。

以上のように実装することで全体でO(N+M)時間に抑えたので、無事ACできました。でもこの実装がUnion-Findかというと多分違うと思います。

今回のコードレビューは、

  • varを多用しすぎ。
  • 一つの変数にIntを使うべき場所とLongを使うべき場所の両方が存在してしまい。toLong()を使う必要が出ている。
  • クラスの作りが非常に雑、こんなクラスならなくていい。

ざっと見た感じだとこのくらいですかね。多分もっと突っ込みどころありそうですね。

雑記

  • ACできたとは書きましたが、1800msくらいかかっていたので多分入力がボトルネックになっています。でも入力を実装するとブログ上にコード貼り付けるときに困るんですよね…

  • ABC120 C Unificationは愚直に解いてTLE出し続けました。他人の実行時間を見てから解けたので事実上自力ではないです。

ABC121 C Energy Drink Collector,D XOR WorldをKotlinで解いてみた話

競プロ AtCoder Kotlin ABC121 C問題 D問題

irisruneです。自己紹介でも軽く触れましたがKotlinが面白そうだったので過去問はだいたいKotlinでやります。

今日のテーマはちょっと軽めですがABC121のC問題とD問題。あと一応AtCoderで使うKotlinについて。

ABC121-C

atcoder.jp

やるだけソートの実装力が9割くらいの問題です。

class Store(val a : Long, val b : Long)

fun main(args: Array<String>){
    var(n, m) = readLine()!!.split(" ").map(String::toLong)
    var l = mutableListOf<Store>()
    for(i in 1..n){
        val (a, b) = readLine()!!.split(" ").map(String::toLong)
        l.add(Store(a, b))
    }
    l.sortBy { it.a }
    var sum = 0L
    l.forEach{
        sum += it.a * listOf(it.b, m).min()!!
        m = listOf(0, m - it.b).max()!!
    }
    println(sum)
}

想定解と同じだしアルゴリズム面で言うこともあまりないと思うので簡単なコードレビューを。

  • MutableListは別にvarにする必要はないのでvalにするべき。
  • 単純な整数2つの組ならクラスを作るなんて仰々しいことをしなくてもPairでなんとかなる。
  • 入力値のmを直接変化させるのは微妙？forEach部分をメソッドに分離してmを値渡しすればすっきりしそう。

ABC121-D

atcoder.jp

XORの性質を理解しているかどうか…というよりはf(0,X)を求める発想ができるかの方が強いと思います。D問題にしては比較的簡単な方です。

fun f(x : Long) : Long{
    return when(x % 4){
        0L -> x
        1L -> 1L
        2L -> x + 1L
        else -> 0L
    }
}

fun main(args: Array<String>){
    var (a, b) = readLine()!!.split(" ").map(String::toLong)
    println(f(a - 1).xor(f(b)))
}

解法に行き着く過程としてはこんな感じでした。

  1. 愚直にやるのはO(X)時間かかるので無理。
  2. O(1)時間で解けるf(X)を使ってf(B)-f(A)みたいに表せるのでは？
  3. XORの性質上2.はだいたい正しい。
  4. f(X)をX=0,1,\dotsで列挙したら法則性が見つかったので解けた。

解説ではf(X)は排他的論理和の性質から数学的に導けるとありましたが、いずれにせよ(X\mod 4)での場合分けに行き着くと思います（(X\mod 2)と(\lfloor \frac{X}{2}\rfloor \mod 2)とで二回分岐するのも本質的に同じなので）。

あとはコードレビュー。

  • (a, b)はvalにするべき。
  • (x % 4)は(x % 4L)にするべき。

型関連はバグの原因になるので気を付けましょう。今回はセーフでした。

(pure)Kotlin(v1.0)のポイント

（2019/03/05現在）AtCoderではKotlin1.0しか使えません。これはどの辺に影響してくるかというと例えば

    val minA = minOf(A1, A2)

が使えないので、(pure)Kotlinで書くならば

    val minA = listOf(A1, A2).min()

という形に。Java関数を使えば別に不自由しないと思うんですがせっかくなのでJava関数は（なるべく）使わない方針で。

でもkotlin.mathが使えないのは代替案が思いつかないのでjava.lang.Math使います。つらい。

自己紹介とこのブログについて

競プロ AtCoder

自己紹介とブログ開設の経緯

初めまして、AtCoder記事を始めましたirisruneです。AtCoderプロフで自己紹介しますと、

f:id:amifiable:20190308105109p:plain:w360

atcoder.jp

大体こんな感じに1年弱かけて水色になったところで、主にC++（いわゆるBetter C）を使っておりABC3-4完、AGCはA問題早解き勢くらいの実力です。

業務ではどっちかというとC#とかKotlinとかの方が多め、Kotlinが面白そうなので過去問に使ってみたりしてます。

ブログを開設したきっかけは、リーダーにAtCoderのレートを聞かれて水色寸前です（当時）と答えたところ『試しにレート2000への道とかブログ書いてみようぜ！』と言われ時間を頂いたので書いてみることに。黄色はちょっと辛いけど青色くらいは目指したいです。

うちの会社の宣伝にもなればいいよねとかそんな打算的な話もあったりなかったり。 AtCoderJobsにも登録してます！

このブログについて

メインはAtCoderの問題（コンテストか過去問）を解いて、それについて

  • 問題に対する自分のアプローチ
  • コードレビュー
  • 解説の想定解法との違い

など書き綴るいわゆる普通の感じです。まだほとんど過去問を埋めてないのでしばらくはABCのC,D問題が中心になります。 多分コンテスト参加した時はC++、過去問をやってる時はKotlinで書いてると思います。

月・水・金で更新する予定なのでどうぞよろしくお願いします。