ARC 098

いつもはvmware+linux+vscodeで出ていたんだけど,今回はwindows+wsl+clionで参加(したかった)

F

お金を配りながら移動していく,ただし移動するときには頂点ごとにしきい値がある
→サンプル1を書いてみて想像をする
 →どうやらお金はありすぎて困ることはない
  →二分探索?

二分探索できるのでとりあえず二分探索してみる(logは定数なため)
→最初のお金Zが決まるから可能か?を求める
 →お金を配ると結局どうなる?
  →移動可能範囲が狭まっていく
   →移動可能な範囲が狭まっていくなか,うまく全部の頂点を辿れるか?
    →ものがstrictに減っていく時は逆から考えると良い(一般に減らしていくより増やしていくほうが簡単なため)

ゴールから考えるとどうなる?
→最初のお金が決まっているため最後のお金も当然決まる
 →お金を頂点から回収していって,だんだん移動可能範囲が増えていく
  →どうやら多項式にはなった(TLEだけど)

どうやらゴール位置が重要っぽい
→例えばゴール位置を決め打つと簡単に計算できるか?
 →priority_queueとか使って探索していくとうまくやると行けそう
  →じゃあどうやって複数のゴール位置についてやる?
   →ゴール位置が複数あると,複数位置からじわじわ探索が広がっていって,衝突したらmergeみたいな雰囲気がありそう
    →データ構造をマージする一般的なテク?

制約もそれっぽいし,解法はデータ構造をマージする一般的なテクだろうと想像がつく
→log 3個?
 →流石にデマパートはlog 2個からは落とせなそう(なんか隣のやつをsortして持っておくみたいな操作が必要そう),じゃあ二分探索やめるしかない?
  →二分探索やめるか

二分探索をやめる
→最初に持っている額を決め打てない
 →最初は0円スタートで,足りなくなるたびに適時無からお金を生成する感じで

まとめる
→ゴールから考える
→最初は0円スタート
→それぞれの頂点について,「もしこの頂点がゴールだったら?」を並列にシミュレーションする感じ
 →シミュレーションそれぞれについて,できる限り進めて,進まなくなったら「無からお金をいくら生成すればシミュレーション進みます」を計算してpriority_queueに突っ込む,それが最小の額だけ無からお金を生成して,シミュレーションを進める
  →これを繰り返せばなんとかなりそう,色々大変だけど計算量もなんとかなる?
   →AC

C

累積和流行ってる?

D

0いるか?僕はいらないと思います

E

えー全然わからない,おわりです →よく考える
 →最大と最小の両方に自由度があるのなに?
  →よくみるとN=2000
   →最大か最小どっちか固定して,それぞれO(N)に違いない,自由度1ならなんとかなるだろ

どっちを固定したい?
→最大固定はよくわからないけど,最小固定はうれしさがある(部分列にいくつかの要素を含められないという条件になるため)

最小を固定してみる
→いくつかの要素が取れなくなる
 →要するに数列が分解される
  →いくつかの数列が与えられる,取り除いたやつの最大値を最小化

可能かどうかの判定は?
→数列の要素数から簡単にわかる

最大値の最小化は?
→そもそも最小値は絶対取り除けるんだから,最大値の最小化もクソもなくないか?
 →[1], [100, 100, 100, 100]とかになると1を取れなくなるのか
  →連結成分ごとに取り除ける個数が決まっていて,そのなかではかなり自由?(APC Dを思い出すなあ(唐突な宣伝))
   →正しそう

AGC 024

E

解けません,全然解けません,おわりです

D

問題の理解が大変

とりあえず最小値を求めないといけない
→AGCで無向木の意味不明な性質を求められたらとりあえず直径に注目しろという法則があり
 →(直径+1)/2色は絶対必要なことがわかる
  →なので(直径+1)/2色で塗り分けられることがわかる(理由: AGC)

最小値は求まったので(求まったとは?)葉の個数を数えればいい
→よくわからないよくわからない
 →サンプルを実際に書いて眺める
  →なんか深さiはa_i分木みたいなのを作る?
   →ちょうど答えがいい感じのサイズ(250)になったので,正しい(強気)

F

読解が大変
→高速ゼータ変換部分列版をしろという問題
 →高速ゼータ変換を一般化した論文があるんですが,それだとうまくいかない
  →そもそも何がしたいのか?
   →文字列が1個あったとき,部分列を1回ずつ列挙する方法は?(ここで経由する状態がシンプルだといい)
    →普通に先頭から0か1をとっていけばいいですね
     →AC

A

A問題なのにサンプルの出力にUnfairが無いため,Unfairを出力することはない

とりあえず適当に手で試す
→ああ-1倍されるのか
 →AC

B

AtCoderでこれと似たような問題で,残すやつに注目するとLISという問題があったはず
→残すやつに注目すると?
 →ああ単調増加
  →AC

C

二次元平面(X: i, Y: a_i)を想像する
→階段がはやせる,階段しかはやせない
 →階段をはやして数列を作れるか?
  →a[i]より2以上a[i+1]の方が大きかったらダメ,あとa_1 != 0でもダメ(こっちはサンプルからわかる)
   →これを満たしていれば作れる,作り方も自然なので数えるのは簡単
    →AC

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と同じようなこと(複数同時代入)が出来るっぽいです。