競プロでグラフの問題を解く時に考えてみること

• 頂点v-u間への操作を考える時、グラフを木にできるなら根rを定めて、v-r,u-rに分けて考えてみる
  • v-uのLCAをpとして、v-uへの操作はv-p,u-pに分けることができる。p-rへの操作を二回しているとみなしてv-r,u-rに分けてみる。「二回操作すると戻る」タイプの場合はp-rへの操作がなかったとみなせるので、v-uへの操作をv-r,u-rへの操作と同一視できる
  • https://atcoder.jp/contests/agc014/tasks/agc014_b

Macでvscodeからdockerに接続して開発する

コンパイラを作ろうと思った

低レイヤを知りたい人のためのCコンパイラ作成入門

けどMacは微妙にアセンブラの仕様が違うので、別途開発環境を用意した方がいいらしい。とりあえずdockerインストールして使ってみたけどvimじゃ辛い。vscodeがdockerコンテナに接続して開発できるようになったらしいので試してみる。ほぼ備忘録。

この辺を参考にした

Dockerで立ち上げた開発環境をVS Codeで開く! - Qiita

Developing inside a Container using Visual Studio Code Remote Development

インストール

dockerとvscode insiderをインストールする。dockerでファイル共有の設定が必要と書いてあったけど、Usersディレクトリがデフォルトで指定してあったのでそのまま。別の場所にコードを置いている場合は指定が必要かも。

接続する

レポジトリにDockerfileを含めて開発していく方法もあるみたいだが、すでに起動しているコンテナに接続もできるよう。Attach to Running Containerから指定したらできた。

その他設定

vscodeが初めてだったので設定したこと。dockerに接続することには以下関係ない。

• C/C++のextension設定
• tasks.jsonでmake testが走るようにする

コンテナへの接続がrootで行われていてユーザの変更ができないため、新しいファイルを作るとrootになっちゃうし、gitの設定も使えないのでこの辺は今後なんとかしたい。

ABC125 C - GCD on Blackboard

atcoder.jp

値の列に対して二項演算を実行していって値を計算したい。そして、一つ抜いた時の値を計算したい。 この問題で言えば、gcdを実行していくが一つ抜いた時のgcdを高速に計算したい。

この時二項演算が結合則を満たすと、どこから計算していっても良いので左から計算していった配列と右から計算していった配列を用意することで1つ抜いた値を高速に計算できる。わかりにくいので足し算を例にとって説明してみる。値の列

al = [a_1, a_2, ... , a_n]

が与えられたとする。a_i以外を足し合わせた値を高速に計算したいが引き算は使えないとする。足し算はどこから計算していっても大丈夫なので、まずは左からの累積和

ll[i] = a_1 + a_2 + ... + a_i

と右からの累積和

rl[i] = a_i + a_(i+1) + ... + a_n

を計算しておく。こうするとll[i-1]+rl[i+1]でi番目を抜いた値を計算できる。この方法は結合則を満たせば足し算以外でも(gcdでも)使うことができる。

ARC097 D - Equals

atcoder.jp

UnionFindの例題としてみたのでUnionFindを使うことは分かっていた状態だったけど解くことは出来なかった。。。 ので思いつく為に必要なことをまた考察してみる

• 場所iと値p_iを同一視する
• x,yのスワップをUnionFindに突っ込めば良さそうな雰囲気というところまで考えられたのにダメだったのはこの辺に理由がある気がする
• 順列を、1からN(の列)からp_1からp_Nへの写像であるという見方が効きそう
• 上記の延長でx,yのスワップも考えられる
• 交換しなくてもいいあみだくじなイメージ

ABC122 D - We Like AGC

atcoder.jp

ABC122は出れなかったけど、出てても解けなかった。解説見てもすぐには理解出来なかったし。。 DPというのはまぁそうだろうなという感じだけど、その後の考察がだめだ。今後はDPな気がするけどうまく考えられない時にはメモ化再帰で解くことも検討してみる。

この記事ではメモ化再帰でやってみようと思った時の流れをシミュレートしてみる。

1. とりあえず再帰で全パターン網羅するやつを書いてみる

def dfs(cur, s):
    if cur==n:
        if re.search(r"(AGC|ACG|GAC|AG.C|A.GC)", s):
            return 0
        else:
            return 1
    res = 0
    for c in "AGCT":
        res = (res + dfs(cur+1, s+c))%MOD

    return res

2. 直前4文字だけ見ればいいことに気付く

気付けるかは分からないが、、 4文字見た時点で判定ができるので、最後に正誤を判定するのではなく枝刈りするような形にしている。 回答見る前にAGC以外のパターンとしてACGやGACがあることは分かっていたが、A*GCやAG*Cもだというのは気付いてなかったのでそこもハマりそう

def dfs(cur, s):
    if cur==n:
        return 1
    res = 0
    for c in "AGCT":
        if not re.search(r"(AGC|ACG|GAC|AG.C|A.GC)", s+c):
            res = (res + dfs(cur+1, s[1:]+c))%MOD

    return res

3. メモ化

ここまでくればcurとsでメモしていけばいいことは分かりやすい

エクサウィザーズ 2019 C - Snuke the Wizard

atcoder.jp

消滅していないゴーレムを数えるのではなく消滅するゴーレムを数えよう、というところまでは思い至ったのだけど結局解けず。解説見て一発で理解出来て悔しかった。

とうことで、どんな事を検討していたら解けたか考えてみる

• 1クエリで最悪10**5箇所に更新がかかるので、全てをシミュレートするのは無理。よって、各場所に何体ゴーレムが残るかを計算するのではなく、残るゴーレムの総数を直接計算するはず。
• 残るゴーレムではなく、落ちるゴーレム(補集合)を考える。
• 例えば左から落ちるやつ/落ちないやつを列挙してみる。
• 系列が途中で切り替わる(今回なら左から落ちるやつ、落ちないやつの切り替わり)なら、切り替わり地点を探して数を計算する。
• 切り替わって元に戻らないなら二分探索で探せる。

こんなところか。今回落ちるやつは手でシミュレーションしてたけど落ちないやつの判定まではしていなくて、それで途中で落ちる/落ちないが切り替わって戻らないというのが気付けなかった感ある。

追記

二分探索で切り替わるところを探したけど、呪文を後ろから見ていくという方法で切り替わる部分を探すことができる。

エクサウィザーズ 2019 C - Snuke the Wizard - ツバサの備忘録

二分探索だとシミュレートにO(Q)、切り替わる点を探すのにO(log(N))かかるが、こっちだとO(Q)だけで計算できて早い。実際pythonだと二分探索だと1800msくらいかかってギリギリだったが後ろから見る方式だと500msくらいだった。

いずれにしても落ちる/落ちないが途中で切り替わることに気付けないとだめ

XOR の性質

ABC121-Dが競技中に解けなかったので、XORの性質について調べて追記していく。コードはpython。

基本

「^」で計算できる。

a = 1
b = 2
c = a^b # 3

整数をビットごとに考えて、aとbで0/1が異なる場合に1それ以外は0となる。

性質

1. 0とXORを取っても値は変わらない

a = 12
b = 0^a # 12

2. 自分自身とXORを取ると0となる

a = 12
b = a^a # 0

3. 左右を交換できる

a = 12
b = 5
a^b == b^a # True

4. 自身にプラス1した数とXORを取ると1になる

a = 12
b = a+1
c = a^b # 1

5. 数の集合の中でXORを取るときには桁ごとに考えていい

足し算のように繰り上がりしないので、桁ごとに答えを考えていくことができる。

6. a==a^b^b

2よりb^bの部分は0で、1よりa^0はaであることから導ける