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

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

ABC119 C Synthetic Kadomatsu (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で

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で

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で

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で解いてみた話

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記事を始めました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で書いてると思います。

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