プログラムレベルでの wifi 接続方法

github.com

python で良さそうなライブラリがあった.

コードを流して読むと大体何をやっているのか分かった.

  1. _detectDriverメソッドを呼び出す
    • このときに各OSのWireless Driverをwhich コマンドから検索して見つかったものを選択するようにしている.
  2. 接続処理も各OSのWireless Driverに従ってコマンドを実行する.

Linux系だとnmcliが使われるのかなと思ってnmcliの内部実装に興味が湧いたので少し読んでみた.

そもそもでnmcliNetworkManagerのクライアントのコマンドラインで内部処理はNetworkManagerを読めば良さそう.

NetworkManagerについては

github.com

ここを見れば良さそうだ.これを読み解いていくのは流石に骨が折れるので,読み進めて知見を得ることができたらまたメモする.

Leetcode : 629. K Inverse Pairs Array

leetcode.com

問題概要

長さ n の順列を考える.反転数が k となる数列を数えなさい.

考察

一番愚直だと思われる解法は n! 通りの数列の反転数を計算し,kとなるものを数え上げるというものである. この計算量は O(nlogn*n!) であるがこれは明らかにTLEする.

部分問題に切り分けることを考える.1 から n-1 までの数字を用いて作る数列に n を追加することを考えると漸化式を立てれそうな気がする.

dp[n][k] := 数列の長さが n で 1 ~ n の数字で構成される数列において反転数が k となる数

とすると

dp[n][k] += sum_{i=0}^{n} dp[n-1][k-i]

`となる.

これでは O(n3) となるが,まだTLEする.そこで上のdpを高速に計算する方法を考える.

遷移を見ると,規則性が見えて累積和を取ることによって O(n2) に落ちる.

ソースコード

コメントの部分が O(n3) の解法です.

class Solution {
    
public:
    int kInversePairs(int n, int k) {
        static long long dp[1024][1024];
        static long long conv[1024];
        
        for(int i = 0; i < 1024; i++) {
            for(int j = 0; j < 1024; j++) {
                dp[i][j] = 0;
            }
        }
        
        // 長さ1の数列で反転数=0の数
        dp[1][0] = 1;
        
        // 右からiを挿入したときの反転数.
        for(int i = 0; i < 1024; i++) {
            conv[i] = (i*(i+1)/2);
        }
        
        long long mod = 1e9 + 7LL; 
        
        // i: 長さiの数列
        for(int i = 1; i <= n; i++) {
            // a: 今の反転数(上限はk)
            /*
            for(int a = 0; a < min(conv[i], 1001LL); a++) {
                // j: 右からj番目に(i+1)を挿入する
                // 例) 
                // [1 2 3 4]
                // j = 0: [1 2 3 4 5], j = 1 : [1 2 3 5 4], ...
                for(int j = 0; j <= i; j++) {
                    if(a+j > k) break;
                    //printf("[i=%d] : next: %d: j= %d, conv[j] = %d, dp[i][a=%d] = %d\n", i, a+conv[j], j, conv[j], a, dp[i][a]);
                    
                    dp[i+1][a+j] += dp[i][a];
                    dp[i+1][a+j] %= mod;
                    
                }
            }
            */
            long long cnt = 0LL;
            for(int j = 0; j < min(conv[i], 1001LL); j++) {
                cnt += dp[i-1][j];
                if(j-i >= 0) {
                    cnt -= dp[i-1][j-i];
                }
                //printf("[i=%d] : j=%d, conv[j] = %d, cnt = %d\n", i, j, conv[j], cnt);

                dp[i][j] += cnt;
                dp[i][j] %= mod;
            }
        }

        return dp[n][k];
    }
};

所感

こういう問題をバグなく高速に通せるようにしておきたい.

第12回 JOI 本選 : Tower of JOIOI

概要

長さ N の 'J' 'O' 'I'の文字しか含まれない文字列 S が与えられる.

i < j < k において

  • s[i] = 'J' and S[j] = 'O' and S[k] = 'I' または
  • s[i] = 'I' and S[j] = 'O' and S[k] = 'I'

を満たす (i, j, k) の数の最大を求める.ただし,一度使った i, j, k は使うことができない.

考察

制約から O(nlogn) か?となる.

サンプルを試しながら性質を分析する.

  • IOIJOIにおいて,Oは共通の用途(真ん中)で使われることが分かる.
  • Iは左か右かの2通りの用途がある.
  • Jは左の用途しかない.

最初はdpっぽく解けるのかなぁと思ったけど部分問題に落とし込むことができなくなってこれは違うなと思った.

サンプルを試すと JO の次の Iに関して注意して考えると良さそうな気がしてくる.いろんな例で試してもあまり自明に思えないので,これは間違いっぽいということが分かる.

今は前から見ることばかり考えてたけど,後ろから I と O を決定すると,それより前のJを貪欲に使っていけそうなことが分かる.

ここまで考えて行き詰ったので解説を見る.

なるほど二分探索で右側のIの数を固定するのか,となって終了した.

ソースコード

http://joi2013ho.contest.atcoder.jp/submissions/1440781

所感

考察は良さそうなところまでいってる気はするけど,最後の詰めが出来ない. 最初の制約から計算量を推測するところで二分探索の可能性を頭の中に残しておくべきだった.

あと実装力が全然足りてないので,変な実装をして O(N2) になってたのも残念すぎる.

問題文からはそう見えないけど解答がクエリっぽいなと思った(今見ている添字の前の状態しか見る必要が無いので).

2015年 大問3 (2)

院試で面白い問題があったのでメモ.

問題文

ある集合  A が与えられる.この  A の冪集合を  P(A) と表す.  P(A) 上の二項関係  R_{P(A)} を次のように定義する.

{
R_{P(A)} = \{ (a,b) \in P(A) \times P(A) | (a \subseteq b) \wedge (\forall c \in P(A))
[ ( (a \subseteq c) \wedge (c \subseteq b) ) \rightarrow ( (c=a) \vee (c=b) ) ] \}
}

 |A| = n の時, |R_{P(A)}| を求めよ.

方針

 n=2 の時で考えると,以下の図のような組み合わせが得られる.

f:id:t-tatsukawa:20170720015100j:plain

上の図から,今見ているグループと次のグループの積を足して, a=b となる要素を全て足したら答えが求まりそうに思える.

これは間違いである. |A|=3, A=\{0,1,2 \} で検証すると, \{ 2 \} \{ 0, 1 \} には推移しない.

しかしここから,次グループに推移する数を求めれば答えが求まりそうなことが分かる.

ではどのようにして考えればいいだろうか.

集合に含まれている  A の元を1, 含まれていない元を0としてビットで表現する.すると以下の図のような結果が得られる.

f:id:t-tatsukawa:20170720015743j:plain

よって次のグループに推移する数は  n-i 個ある.

解答

{ \displaystyle
2^{n} + \sum_{i=0}^{n-1} ((n-i)\cdot nC_i )
}

所感

いや,はてなブログmarkdown記法の数式の挙動が意味不明すぎて,組み合わせすら満足に書けないのは許してください. 本番でこれ解くなら  n=4 ぐらいまで実験しないと最初の方針で考えそうで怖い.

この性質を使えば何か問題できるかなぁ.

ICPC 2017 Domestic : F リボンたたみ

問題文

https://storage.googleapis.com/icpcsec/icpc2017-domestic/contest/all_ja.html#section_F

概要

細長いリボンを  N 回畳む操作を行う.この時畳む方向を選択することができる(左から右を L,右から左を R とする).  N 回畳むと  2^{N} 個マスができる.ある特定のマスにマークを付けるとする. 初期状態のマークの場所と最終状態のマークの場所が与えられるので,それらから畳んだ方向の系列を求めるというもの.

解法

各マスを  (x, y) で表す.また,次のような座標系で話を進める.

 k 回目の畳む操作の時は, 2^{n-k} \times 2^{k} のマスとなる.

f:id:t-tatsukawa:20170718102419p:plain

題意より,最終状態の  (x_n, y_n) = (0, y) が与えられる.ここから L と R の操作を戻すことによって得られる  n-1 回目の畳む操作の状態を考える. このとき,L と R の y 座標の値は等しくなる.これは, k 回目の状態に関しても同じことが言える.感覚としては以下の図のような感じになる.

f:id:t-tatsukawa:20170718102428p:plain

さて, k 回目の畳む操作によるマーク座標の遷移について考える. 畳んだ後は一番左下のマスが  (0, 0) となるように移動させる.

これは以下のような場合分けで考えることができる. 操作前のマークの位置を  (x_k, y_k) とする.

  1.  2^{n-k-1} > x_k のとき
    • 操作 L:
      • x_{k+1} = 2^{n-k-1} - x_k - 1
      • y_{k+1} = 2^{k} + (2^{k}-y_k)
    • 操作 R:
      • x_{k+1} = x_k
      • y_{k+1} = y_k
  2.  2^{n-k-1} \leq x_k のとき
    • 操作 L:
      • x_{k+1} = x_k-2^{n-k-1}
      • y_{k+1} = y_k
    • 操作 R:
      • x_{k+1} = 2^{n-k}-x_k-1
      • y_{k+1} = 2^{k}+(2^{k}-y_k)

先程述べた y 座標の場所が変わらないということが遷移式からも分かる.

現時点でのマークの x 座標, y 座標の値と次の y 座標の値が分かれば LR の選択が決定する.

よって,最初に y座標の値を後ろから求め,初期状態  (x_0, y_0) = (x, 0) から順番に  (x_k, y_k) を更新しながら LR を求めれば良い.

ソースコード

実際に提出してないので間違っている可能性はあることに注意.

入手力データが更新されたので検証して正しい解が得られることを確認した.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    int64_t x, y;

    while (cin >> n >> y >> x)
    {
        if(x == 0 and y == 0) {
            break;
        }

        x--, y--;

        int64_t x_l = 1LL;
        int64_t y_l = 1LL;

        for (int i = 0; i < n; i++)
        {
            y_l *= 2LL;
            x_l *= 2LL;
        }

        vector<int64_t> Y(n + 1);
        Y[n] = y_l - y - 1LL;

        for (int i = n - 1; i >= 0; i--, y_l /= 2LL)
        {
            if (y_l / 2LL > Y[i + 1])
            {
                Y[i] = Y[i + 1];
            }
            else
            {
                Y[i] = y_l - Y[i + 1] - 1LL;
            }
        }

        for (int i = 0; i < n; i++, x_l /= 2LL)
        {
            if ((x_l / 2LL) > x)
            {
                if (Y[i + 1] == Y[i])
                {
                    cout << "R";
                }
                else
                {
                    cout << "L";
                    x = x_l / 2LL - x - 1LL;
                }
            }
            else
            {
                if (Y[i + 1] == Y[i])
                {
                    cout << "L";
                    x = x - x_l / 2LL;
                }
                else
                {
                    cout << "R";
                    x = x_l - x - 1LL;
                }
            }
        }

        cout << endl;
    }
}

所感

こういう考察系が苦手なので解いた.

とりあえず一番弱いサンプルの遷移図を書いて考えるが,  O(2^{N}) の解法ばかり浮かんできてそこから進まなかった. そもそもリボンを折った時の各マスの状態すら間違えるし酷すぎる.

規則性もいくつか見つけたが上手く使うことができず.

初期状態 → 終了状態 から制約を付けることが難しいなぁと思う.y の偶奇によって x の値が変わるのでそれを使うのかな?というところまで分かったがそこから進まず.

考察系問題集とかが欲しい.

ABC 067

abc067.contest.atcoder.jp

久しぶりに参加した.

順位は 21th で早解きが苦手になっていると感じた.

残念なことにレーティングの更新対象ではないレーティングを持っているということすら忘れていた.

所感

A問題

A, B, A+Bに対してmod 3取ってやれば良い.

B問題

ソートする.

C問題

累積和.

D問題

与えられているグラフが木なので,フェネックとすぬけくんを結ぶパスは一つだけ存在する.

最適な行動とは書いているが,塗る頂点を最大化するように各自行動するので,フェネックとすぬけくんの間のパスに関してどれだけ多く塗ることができるかを考えれば良い.

これは幅優先探索フェネックとすぬけくん交互に塗ることができるマスを広げていけば良い.

この問題で,一般グラフが与えられた時はどうすればいいんだろうかと思った.

橋となるような辺を潰していくようにすれば,連結成分の頂点を得ることができるが,その連結成分への橋がいくつあるかにもよるし一意に定まらない気がする.

ARC 078: F - Mole and Abandoned Mine

問題概要

arc078.contest.atcoder.jp

頂点数  N ,辺の数  M の無向グラフ  G が与えられるので,頂点 1 から頂点  N へのパスが一通りになるように辺を取り除く.

ただし,辺を取り除くにはコストがかかるため,取り除いた辺のコストの総和が最小となるようにする.

解法

辺を取り除くのではなく,辺が無い状態から頂点 1 から頂点  N へのパスが一通りになるように辺を追加し,辺を追加するコストは取り除くコストと同じだとして追加した辺のコストの総和を最大化することを考える.

最大化した解を  x とすると,元の問題の解は  (全ての辺のコストの総和) - x で求まる.

 x はdpで求めることができる.

次のようなグラフを考える (辺のコストは記していない).

f:id:t-tatsukawa:20170717051835p:plain:w500

解が以下のようなグラフになったとする.青色で囲まれているところをターミナルと呼ぶことにする.

このターミナルに含まれる辺は橋(取り除くと連結では無くなるような辺)となる.

緑色で囲まれている頂点集合は,各ターミナルに接続されている連結成分を指す. この連結成分はあるターミナルとは互いに素で,ターミナルと一辺で接続されている. なので,連結成分の頂点同士の辺は全て追加すると良い(最終的に最大化に持っていくため).

この連結成分の頂点同士の辺を全て追加した時のコストは前処理で計算できる.

f:id:t-tatsukawa:20170717045355p:plain:w500

dpの式は以下のようになる.

 dp[S][t] := Sに含まれる頂点を用いており,ターミナル tを見ているときのコストの最大値

更新は以下のように考えれば良い.

ターミナル  i を見ている時,隣接していて  S に含まれてない頂点集合の中から次のターミナル候補  j S の補集合の各部分集合に対して更新式を立てることができるのでそれを計算すれば良い.

f:id:t-tatsukawa:20170717051832p:plain:w500

ソースコード

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int MAX = 16;

int dp[1 << MAX][MAX];
int costs[1 << MAX];
int G[MAX][MAX];

int main() {
    int N, M, a, b, c, all_costs = 0;

    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        a--, b--;
        G[a][b] = G[b][a] = c;
        all_costs += c;
    }

    for(int i = 0; i < (1 << N); i++) {
        for(int j = 0; j < N; j++) {
            for(int k = j+1; k < N; k++) {
                if(!((i >> j) & 1)) continue;
                if(!((i >> k) & 1)) continue;
                costs[i] += G[j][k];
            }
        }
    }

    for(int i = 0; i < (1 << N); i++) {
        for(int j = 0; j < N; j++) {
            dp[i][j] = -INF;
        }
    }

    for(int i = 0; i < (1 << N); i++) {
        // set to terminal 0
        if(i & 1) {
            dp[i][0] = costs[i];
        }
    }

    int mask = ((1 << N) - 1);

    for(int S = 0; S < (1 << N); S++) {
        for(int i = 0; i < N; i++) {
            // select terminal i in S
            if(dp[S][i] == -INF) continue;
            // create a sets "sup" that is sub S
            int sup = (~S) & mask;
            int sub = sup;

            for(int sub = sup; sub; sub = ((sub-1) & sup)) {
                // select terminal j in "sub"
                for(int j = 0; j < N; j++) {
                    if(!((sub >> j) & 1)) continue;
                    if(G[i][j] == 0) continue;

                    dp[S|sub][j] = max(dp[S|sub][j], dp[S][i] + G[i][j] + costs[sub]);
                }
            }
        }
    }

    cout << all_costs - dp[(1<<N)-1][N-1] << endl;
}

所感

解説通りの解法だと思うのでアレ. 厳密な証明とか計算量の計算とかできてないので見直してみる.