GCJ R2

思考要素が無さすぎて書くことが…

D

読めないね

読めた?(start gridは任意に選べると誤読をしていた)
→16パターン全探索するだけだと思うんですが…
→WA

間違いが見つからない&問題が読めないので誤読を疑う
→誤読だね

→WA
→1*nで死んでいて
→プログラムがバグっていて
→AC

C

行と列で被らないように←ここあたりで二部グラフに変換してからのフローっぽいなと思う
→フローでした

A

貪欲だけどどうやって実装しよう,適当に実装しよう
→AC

B

被らないようにペア(r, b)をとっていく
→最小のサイズの凸包を作る問題のアルゴリズムとかなり似ている
→(r+b)が小さい順に貪欲?
→反例生成

貪欲じゃなさそう?DP
→最終的な人数を決め打って,Rを全部振り分けてからBを全部振り分けると考えるとなんかDPになった
→AC

Yukicoder #191

D

えーN<=32, 1e9, 構築,これは明らかにbase2で考えるタイプの性質であり
→base2で考えると解けました

E

誤差が非常に厳しい
→微調整をしたいね
 →sqrt(x+1) - sqrt(x)は?だいたい1/sqrt(x)
  →全然精度足りないね
   →じゃあ(sqrt(x+2)+sqrt(x)) - 2×sqrt(x+1)は?
    →だいたい1/xsqrt(x),精度足りそうだね

大雑把に作って,[x, x] -> [x+1, x-1]という遷移で誤差を微妙に調整する事を考える
→微妙に精度足りないね

とりあえず大きいほど微調整が聞くので,1e-10, 2e-10, 4e-10の微調整が可能なやつを用意しておいて,それで最後の調整をすることにする
→うまくいくときもあるしうまくいかないときもあるね
 →じゃあ何回かやればいいか!w
  →TLE
   →微妙に定数倍改善
    →AC

A

うんうん

B

K=0いるか?

C

素数の性質は難しいため,あんまり素数の性質には頼らない解法をしたい

構築の解き方①であるx進数は流石に無理そうなので, 構築の解き方②である「だいたいKをつくる→だいたいさっきのあまりをつくる→だいたいさっきのあまりをつくる→…」を考える

a+bが素数のペアが作れれば1×1, 1×2, ..., 100×100で誤差99まで作れる
c+dが素数のペアが作れれば1×1, 1×2, ..., 10×10で誤差9まで作れる
e+fが素数のペアが作れれば1×1, 1×2, ..., 1×10で誤差0になる

ので要するに,a+b, c+d, e+fが素数でそれ以外のペアは素数ではない(a, b, c, d, e, f)があればいい
→きっと適当に乱択で出てくるだろう
 →出てきた
  →WA
   →えー生成コードくんが間違っており
    →AC

CF #483

A

素因数系?1018なのでgcd/lcmでなんかやるタイプだろう

条件は?
→とりあえずp, qは既約にする
→gcd/lcm系なので素因数ベクトルで考える
→まずb=10の場合は?
 →どうやらqが2x * 5yならば可能
  →さすがにqの素因数のなかでbに含まれないものがあったら不可能だろう
  →これの逆(bに含まれないものがなかったら可能)は言える,多分必要十分

整理する
→p, qを既約にする
→qの素因数のなかでbに含まれないものがあるか判定

これをgcd / lcmで実現可能か?
→p /= gcd(p, q)をたくさんやれば共通素因数が全部除去できるので,可能
 →Pretest Passed?
  →TLE
   →小手先改善,はたして

B

fの性質は?
→CSAで最近見た,経路数 mod 2に帰着できるのでリュカの定理

これのmax?一体全体
→…

N = 5000とは?O(N polylog)ではなくO(N2)ということ?
→経路数,O(N2)と来たらどう考えてもDP[x][y] = DP[x-1][y] + DP[x][y-1]が怪しい
→あーこの形でDPがうまくいくんですね

→Pretest Passed

C

問題文が長い,パス

D

かなり実家を感じる

えー長方形を塗って上書きしていく
→長方形iは長方形i+1, i+2, ...の影響を受ける
→後ろのやつらの影響を受けるが前のやつらの影響は受けない,じゃあ逆から考えれば良い性質?

整理する →以下のクエリを処理せよ
 →長方形を塗る
 →長方形のなかで,まだ塗られていない場所はあるか?
→これRUPCで見た
→…
→これRUPCでは解けなかった

思考を変える,クエリが全部オフラインで二次元平面なので,平面走査もアプローチとして有力だろう

平面走査をするとどういうクエリになる?
→二次元平面に横線を足す
→二次元平面に横線を抜く
→二次元平面を上から見たときに見れる横線の一覧は?

3つめのクエリが絶望的,本当にこれを処理するの?
→よく考えると各横線について一瞬でもわかるかがわかればいい
→じゃあ1個取得にして取得O(polylog)でならしO(N polylog)のタイプに違いない

3つめのクエリは変更可能
→二次元平面を上から見たときに見れる横線のうち,今まで見れていない奴は1個でもあるか?

とりあえずここまでくれば可能か?
→データ構造なので,とりあえず平方分割で可能か考える
 →可能そう
  →じゃあSegTreeは?
   →多分可能

→実装
→バグって大変でした…(ストレステストまで書いた)
→Pretest Passed,はたして?
→Pretest Passed数みたら大間違いでした。かなしいね

ARC 097

CD: 反射

E

Nが2000
→数えるのにO(N2)かかる保存量がある?

保存量
→転倒数を拡張?
 →i個目とi+1個目を通る個数?
 →a[i] > a[j]ならj-iを足す?
  →全部ダメ

最終的な数列が定まると答えは簡単(転倒数)
→最終的な数列はどういう形になるか?
 → (W1, W2, ..., Wn)と(B1, B2, ..., Bn)をマージした形になる

Nが2000
→ある程度までのゴリ押しは可能
 →最終的な数列を全部探索,をまとめられないか?   →DP?
   →キーは3個に見えて2個,遷移が高速なら可能

DP
→遷移を適切にやればO(1)
→AC

F

Nが100,000
→かなり良い性質がある
 →「無駄な行動」をしない操作列という条件をしないと実は考えるべき操作列が少なくて高速に計算できるタイプの問題?

性質?
→全ての白い頂点を訪れる必要がある
 →全ての白い頂点を訪れるために必要な秒数は?
  →何年か前の国内予選で既出,白い頂点を葉とする部分木にカットして,2*(n-1) - 直径

白い頂点を葉とする部分木にカットする?
→きっちり証明は出来ないけど正しそう

もしかして2*(n-1) - パスの形の行動経路しか考えなくていいのでは?
→反例も出ないしこのぐらい良い性質が無いと解けなそうなので,多分正しい(強気)

2*(n-1) - パスの形の行動経路だとどういうコストになる?
→式変形
→…
→式変形
 →パスのうち白い頂点のmaxを求める問題
  →典型,木DP

→AC

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた

精選過去問→AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ - Qiita, Tasks - AtCoder Beginners Selection

いろんな言語のまとめ→百花繚乱!なないろ言語で競技プログラミングをする資料まとめ - Qiita

既にあるやつ

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた (takeoさん)

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた - D言語の構文と標準ライブラリを使い倒す編 - 矮小 (yousackさん)

(この記事の新規性は)ないです(たまにはブログ記事を書きたかった)

PracticeA - はじめてのあっとこーだー(Welcome to AtCoder

import std.stdio : readf, readln, writeln;
import std.string : strip;

void main() {
    int a, b, c;
    string s;
    readf("%d\n", &a);
    readf("%d %d\n", &b, &c);
    s = readln.strip;
    writeln(a+b+c, " ", s);
}

readfscanfと同じように入力できます。ただし

  • int以外も全部符号付き整数は%d, 符号なし整数は%uで入力(%lldとかはつかわない)
  • \nが無いと壊れる

などの違いがあります。

readln(1行読み込み)は最後に改行文字がくっついてくるのでstrip, chompなどで取り除きましょう

なお,core.stdc.stdioをimportするとC言語scanf, printfが使えるようになります。文字列の扱いが難しいのでおすすめしません

import core.stdc.stdio;
import std.string : strip;

void main() {
    int a, b, c;
    char[] s = new char[100];
    scanf("%d %d %d %s", &a, &b, &c, s.ptr);
    printf("%d %s\n", a+b+c, s.ptr);
}

ABC086A - Product

import std.stdio;

void main() {
    int a, b;
    readf("%d %d\n", &a, &b);
    writeln(["Even", "Odd"][a*b%2]);
}

配列リテラル{1, 2, 3}じゃなくて[1, 2, 3]です

ABC081A - Placing Marbles

import std.stdio, std.string;
import std.algorithm : count;

void main() {
    string s = readln.strip;
    writeln(s.count('1'));
}

s.count(x)xの個数を数えられます

ABC081B - Shift only

import std.stdio;
import std.algorithm : map, reduce, min;
import std.string : split;
import std.conv : to;

void main() {
    readln; //ignore n
    int[] l = readln.split.to!(int[]);
    auto f(int x) { //xが何回2で割れるか返す
        int cnt = 0;
        while (x % 2 == 0) {
            cnt++;
            x /= 2;
        }
        return cnt;
    }
    writeln(l.map!f.reduce!min);
}

高階関数ってやつをやってみます

  • l : 入力した配列です
  • l.map!f : lの各要素にfを適用した配列(のようなもの)です。たとえばl=[8, 12, 40]ならl.map!f = [3, 2, 3]
  • l.map!f.reduce!min : l.map!fの各要素をminを使って畳み込みます,つまりl.map!f = [a, b, c, ...]としてl.map!f.reduce!min = min(a,b,c,... )

ABC087B - Coins

import std.stdio;

void main() {
    int a, b, c, x;
    readf("%d\n%d\n%d\n%d\n", &a, &b, &c, &x);
    int ans = 0;
    foreach (i; 0..a+1) foreach (j; 0..b+1) foreach (k; 0..c+1) {
        int y = i*500 + j*100 + k*50;
        if (y == x) ans++;
    }
    writeln(ans);
}

foreach (i; a..b)for (int i = a; i < b; i++)とだいたい同じです

ABC083B - Some Sums

import std.stdio, std.string, std.conv, std.algorithm;
import std.algorithm : sum;
import std.range : iota;

void main() {
    int n, a, b;
    readf("%d %d %d\n", &n, &a, &b);
    bool ok(int x) {
        string s = x.to!string;
        int t = s.map!"a-'0'".sum;
        return a <= t && t <= b;
    }
    writeln(iota(1, n+1).filter!ok.sum);
}
  • iota(1, n+1) : [1, 2, ..., n]とだいたい同じです。python2でいうと前者がxrangeで後者がrangeです。
  • filter!ok : これも高階関数で,ok(x) = trueとなるような要素だけ残します。
  • sum : sumを求めます(そうだね)。

つまり,[1, 2, ..., n]からokに入力するとtrueになるようなものを列挙して,それの総和を求めるというコードです。

ABC088B - Card Game for Two

import std.stdio, std.string, std.conv;
import std.algorithm : sort, each;
import std.range : array;

void main() {
    readln; //ignore n
    int[] a = readln.split.to!(int[]).sort!"a>b".array;
    int[2] res; //alice, bob
    a.each!((i, x) => res[i%2] += x);
    writeln(res[0] - res[1]);
}

eachでループと同じようなことが出来ます。

ABC085B - Kagami Mochi

import std.stdio, std.range, std.algorithm;
import std.algorithm : uniq;

void main() {
    int n;
    readf("%d\n", &n);
    int[] a = new int[n];
    foreach (i; 0..n) {
        readf("%d\n", &(a[i]));
    }
    writeln(a.sort.uniq.array.length);
}

a.sort.uniqでsortしてuniqueします。

ABC085C - Otoshidama

import std.stdio, std.range;
import std.algorithm : cartesianProduct;

void main() {
    int n, y;
    readf("%d %d\n", &n, &y);

    int ans = 0;
    foreach (p; cartesianProduct(iota(n+1), iota(n+1))) {
        int a = p[0], b = p[1], c = n-a-b;
        if (c < 0) continue;
        int x = a*10000 + b*5000 + c*1000;
        if (x == y) {
            writeln(a, " ", b, " ", c);
            return;
        }
    }
    writeln("-1 -1 -1");
}

公式ドキュメント読んでたらcartesianProductとかいうの見つけたので使います。 cartesianProduct([1, 2], [3, 4]) = [[1, 3], [1, 4], [2, 3], [2, 4]]みたいな感じっぽいです。つまり二重ループが出来ます

ABC049C - 白昼夢 / Daydream

import std.stdio, std.string, std.regex;

void main() {
    string s = readln.strip;

    auto r = regex(r"^(dream|dreamer|erase|eraser)*$");

    if (s.matchFirst(r)) {
        writeln("YES");
    } else {
        writeln("NO");
    }
}

正規表現も使えます。そう,D言語ならね。

ABC086C - Traveling

import std.stdio;
import std.math : abs;
import std.typecons : tuple;
import std.meta : AliasSeq;

bool solve() {
    int T;
    readf("%d\n", &T);
    int bt = 0, bx = 0, by = 0;
    foreach (i; 0..T) {
        int t, x, y;
        readf("%d %d %d\n", &t, &x, &y);
        int dt = t-bt;
        int di = abs(x-bx) + abs(y-by);
        if (di % 2 != dt % 2 || dt < di) {
            return false;
        }
        AliasSeq!(bt, bx, by) = tuple(t, x, y);
    }
    return true;
}

void main() {
    writeln(solve() ? "Yes" : "No");    
}

AliasSeq!(a, b, c) = tuple(d, e, f)C++のtieと同じようなこと(複数同時代入)が出来るっぽいです。

D言語で競技プログラミング

D言語競技プログラミングをやってみたい…でもなかなか踏み出せない…

実はそんな人が相当数居るはず[要出典]なので,宣伝記事を書きます

主な対象読者

Javaを使っている人も対象ですが,基本的にC++よりここがいい!みたいな書き方をします。 また,D言語C++からの移行のしやすさを売りにしています。

なお,この記事には「お前これC++でも出来るんやが」が含まれている可能性があります。 その場合ぜひ教えてください。私はC++も使うので,ぜひ知りたいです。

「お前これも便利やろが」も含まれていると思います。それもぜひ教えてください。

この記事を読んで興味がわきました!

いろいろ出力できる

D言語では,基本的になんでもwriteln(=c++のprintf)出来ます。

例えば,vectorもそのまま出力できます。

import std.stdio;

int main() {
    int[] v = [1, 2, 3]; // vector<int> v = {1, 2, 3}
    writeln(v);
    return 0;
}
[1, 2, 3]

それだけでなく,structも出力可能です

import std.stdio;

struct Edge {
    int to;
    int dist;
}

int main() {
    Edge e = Edge(1, 2);
    writeln(e);
    return 0;
}
Edge(1, 2)

また,structにtoStringという関数を実装すれば,それが使用されます。

import std.stdio;

struct Edge {
    int to;
    int dist;
    string toString() {
        return "I'm edge";
    }
}

int main() {
    Edge e = Edge(1, 2);
    writeln(e);
    return 0;
}
I'm edge

ライブラリ等に適切にtoStringを実装すれば…夢が広がりますね。 segtreeライブラリに,現在の要素の一覧を出力させたり出来ます。

高階関数

D言語では高階関数が使用可能です。これにより,配列などに対する処理がきれいに書けます

import std.stdio, std.algorithm;

int main() {
    int[] v = [1, 2, 3];

    writeln(v.sum); // 1 + 2 + 3
    writeln(v.map!(x => 2*x)); // [2, 4, 6]
    writeln(v.fold!min); // min(1, 2, 3)
    return 0;
}
6
[2, 4, 6]
1

std.algorithm - D Programming Language ここに様々な高階関数が用意されています。

配列外アクセスをすると怒られる

import std.stdio;

int main() {
    int[] v = [1, 2, 3];
    writeln(v[100]);
    return 0;
}

以下のコードは動くでしょうか?当然動きませんし,動くべきではありません。 ですが,C++ではこのようなコードが動いてしまうことが多々あります。 これは経験のある方が多いのではないでしょうか?

このコードを実行すると,以下のようになります。

core.exception.RangeError@B.d(5): Range violation
----------------
??:? _d_arrayboundsp [0x4378c2]
??:? _Dmain [0x43701c]

このように,5行目でRange violation,つまり配列外アクセスをしたというメッセージを残して異常終了します。

D言語ではデフォルトで配列外アクセスのチェックがonになっており,簡単に気づけるようになっています。

もちろんパフォーマンスの心配もありません。 コンパイル時に-releaseと付ければ配列外アクセスはoffになります。

UFCS

D言語にはUFCS(Uniform Function Call Syntax)と呼ばれる構文糖衣があります。 これは,

f(a)
f(a, b, c)

のような関数呼び出しを,

a.f() or a.f
a.f(b, c)

のように書ける,つまり第一引数を外に出せる+引数が一つならカッコを消せる,というだけの機能です。

とてもシンプルな機能に見えますが,これが非常に強力です。

例えば,

int main() {
    vector<int> v = {1, 1, 4, 5, 1, 4};
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // v = {1, 4, 5}
    return 0;
}

これは,座標圧縮のコードです。

これをD言語で書くと

import std.stdio, std.algorithm, std.range;

int main() {
    int[] v = [1, 1, 4, 5, 1, 4];
    v = array(uniq(sort(v)));
    writeln(v);
    return 0;
}

となります,begin/endが消えてるのは,C++のようにiteratorではなく,rangeと呼ばれるものがベースになっているからです。

これにUFCSを使うと,

import std.stdio, std.algorithm, std.range;

int main() {
    int[] v = [1, 1, 4, 5, 1, 4];
    v = v.sort.uniq.array;
    writeln(v);
    return 0;
}

となります,v -> sort -> uniqと,自然な順番(感想には個人差があります)でソースコードが書けているのがわかるでしょうか。

このように,UFCSを使うと,ソースコードを自然に書け,メソッドチェーンと呼ばれる記法が実現できます。

プロトタイプ宣言がいらない

プロトタイプ宣言がいりません,後方の関数も参照可能です。

import std.stdio;

int collatz(int i) {
    if (i == 1) return 0;
    if (i % 2 == 0) return 1 + even(i);
    else return 1 + odd(i);
}

int even(int i) {
    return collatz(i / 2);
}

int odd(int i) {
    return collatz(i * 3 + 1);
}

int main() {
    writeln(collatz(100));
    return 0;
}

このように,互いに参照し合う再帰関数もプロトタイプ宣言無しで書くことが出来ます。 (ちなみに,このコードは何をしているコードでしょうか?)

細かいの

// void mainと書けます(return 0がいらなくなります)
void main() {
    int sm = 0;
    // rep(i, n)はいらないです
    foreach (i; 0..10) {
        sm += i;
    }
    assert(sm == 45);
    sm = 0;
    // 逆順もできます
    foreach_reverse (i; 0..10) {
        sm += i;
    }
    assert(sm == 45);

    // longは必ず8byteです,typedef long long llとはオサラバ
    assert(long.sizeof == 8);

    assert(2 ^^ 4 == 16); // 累乗演算子があります
    assert(10 ^^ 9 + 7 == 1_000_000_007);


    long f(int x) { // 関数の中に関数が書けます,再帰関数も書けます
        if (x <= 1) return 1L;
        return f(x-2) + f(x-1);
    }
    assert(f(0) == 1 && f(1) == 1 && f(2) == 2 && f(3) == 3 && f(4) == 5);
}

競プロ 言語調査

随時更新

☆ = 0.5★

名前 ジャッジ対応 速度 使用者数
C++ ★★★ ★★★ ★★★
Java ★★★ ★★ ★★
C# ★★ ★☆
D(DMD) ★★
D(LDC) ★★☆
Rust ★☆ ★★★
Go ★★
Python ★★★ ★★

C++

王道、大鉄板、これが使えないジャッジは競プロサイトにあらず

ジャッジ速度使用者数全てで他を寄せ付けない

困ったらコレ

Java

コレが使えないジャッジは(ry

C++より使用者が少ない理由は2つあると思ってて、

  • 遅い。JVMで動いてるからどうしようもないね。でもAtCoder等なら定数倍ヤバはもう出ないので平気っちゃ平気?インドワクワク系は…
  • コードが長くなる、いちばん有名なのはプリミティブ型をラッパしなきゃいけないこと(Integer, Long, Double…)

C

chokudaiさんが使っていることで有名

visual studioの補完が強いらしい?

あとLINQも軽く調べるとかなり便利そう

これも仮想マシンで動いていて、かなり速度に問題があるイメージだけど、 仮想マシンやめるC# Nativeとかいうプロジェクトがあるっぽい?

かなり未来に期待できそう、今現在では微妙感がぬぐえず

D(DMD)

僕は好きです。

何故かプロコン界隈だと、日本でのみ異常な人気がある感じがします。あとGassa

仮想マシンは使ってないけどそもそもコンパイラが微妙なので遅いです

D(LDC)

D言語コンパイラが2種類あるんですが、こっちはLLVMベースなのでとにかく速いです。

対応ジャッジはAtCoder以外見たことないです。

おわりです。

Rust

かなりホットなイメージです

速度もC++並というイメージが有る

実は殆ど書いたこと無いのでイメージで物を言っています

Go

プロコンで使うのきつくない?僕はきついと思います。

Python

C++の次に人気なイメージが有る

当然ながらとても遅いが、まあ速度が問題にならないなら

Kotlin

ICPCにぶち込まれた言語、メインスポンサーって凄いなって思いました。

JVMで動いている以上Javaより速くなることはなさそう?でもKotlin Nativeとかあるらしいし、これもどうなるでしょう

少なくともICPC WFの問題は全部Kotlinで通せることが保証されるんじゃないでしょうか(メインスポンサーは凄いため)