buyoh.hateblo.jp

残念な競技プログラミング参加者

AtCoder Regular Contest 044 - C ビーム

少しだけヒントを見てしまったが,面白かったので解説を書く.

arc044.contest.atcoder.jp

概要

レーザを避けるために必要な最小移動距離を求めよ.

続きを読む

yukicoder No.550 夏休みの思い出(1)

想定解とは違うけれども大丈夫そうなので解説を書いてしまった.

問題概要

三次方程式を解け.

解は整数であることが分かっている.

submission

続きを読む

yukicoder No.545 ママの大事な二人の子供

問題はこちら. - No.545 ママの大事な二人の子供 - yukicoder

コンテスト中に半分全列挙のアルゴリズムを調べ,書きなぐってAccept通したので,その考え方を書きます.

問題文

  • N 個のアイテムがある.
  • i 番目のアイテムをA君に渡すとA君はa_iポイント喜ぶ.
  • i 番目のアイテムをB君に渡すとB君はb_iポイント喜ぶ.
  • 適切に分配することで,2人の喜び度合いの合計の差をなるべく小さく抑えたい.

制約.

  • N は小さめだが,全探索は厳しい([tex:109]オーダー).
  • 喜怒哀楽が激しく,ポイントによる動的計画法が使えない.([tex:1010]オーダー)
続きを読む

scheme / commonLispで解く競技プログラミング (1)

lispをもう少しだけ詳しくなりたかった.

Lispってなに?

  • とても古い言語
  • C言語と比べてとてもシンプルな言語.
  • emacsLispとかで息してる言語.

Lisp言語を選ぶメリット

  • ないと思います.
  • オレオレ言語を作りたいとき,Lispライクな言語設計にすると,とても実装が楽.
    • 共通設計

commonLispってやつを選べばいいのかなー?

知識度

  • B3の講義でやった
  • carとかcdrとかどっちがどっちか忘れた
  • ループやってない,再帰だけ
  • 割と調べまくってます
続きを読む

yukicoder No.533 Mysterious Stairs

前日にtesterしました.

f:id:m_buyoh:20170623205251p:plain

問題概要

No.533 Mysterious Stairs - yukicoder

  • N段の階段がある.
  • 1回の飛躍で1step,2step,3stepずつ登れる.
  • 同じstep数を連続して使えない
  • N段目に到達するパターン数を出力せよ.

基本解法

4つの状態が考えられる.

  1. まだジャンプしていない.
  2. 1段ジャンプしたので,次は1段ジャンプ出来ない.
  3. 2段ジャンプしたので,次は2段ジャンプ出来ない.
  4. 3段ジャンプしたので,次は3段ジャンプ出来ない.

0の状態はスタート時以外では発生し得ないので,1回ジャンプした状態を初期状態とすることで,0の状態を排除出来る.

あとは残り3つの状態について,どう遷移するのかを考えればいい.

今,i段目に居るとして,

  • i+1段目にジャンプできるのは状態2,状態3.
  • i+2段目にジャンプできるのは状態1,状態3.
  • i+3段目にジャンプできるのは状態1,状態2.

f:id:m_buyoh:20170623211537p:plain:w200 f:id:m_buyoh:20170623211540p:plain:w200 f:id:m_buyoh:20170623211534p:plain:w200

これをコードとして書けばAccept.

ll solve_MLE(int n) {
    vector<array<ll, 4>> dp(n + 4);

    dp[1][1] = 1; // 1jump で 1step 登る.次は 1jump は使えない.
    dp[2][2] = 1; // 2jump で 2step 登る.次は 2jump は使えない.
    dp[3][3] = 1; // 3jump で 3step 登る.次は 3jump は使えない.

    for (int i = 1; i < n; ++i) {
        // +1jumpする.
        dp[i + 1][1] = (dp[i + 1][1] + (dp[i][2] + dp[i][3])) % MD;
        // +2jumpする.
        dp[i + 2][2] = (dp[i + 2][2] + (dp[i][1] + dp[i][3])) % MD;
        // +3jumpする.
        dp[i + 3][3] = (dp[i + 3][3] + (dp[i][1] + dp[i][2])) % MD;
    }
    return (dp[n][1] + dp[n][2] + dp[n][3]) % MD;
}

時間計算量はO(N),空間計算量もO(N)

改良1

  • 問題制約を確認すると,Nは100万.
  • つまり,上のプログラムでは400万×8byteをメモリに載せる.
  • これを改善できないか?

上のコードをもう一度見てみると,iより小さい要素には一切アクセスしないことが分かる. アクセスしない領域なら,再利用するべきでしょう.

配列の参照先をずらすんじゃなくて,配列の値をずらしましょう,という仕様です.

ll dp[4][4];
ll solve(int n) {

    dp[0][1] = 1; // 1jump で 1step 登る.次は 1jump は使えない.
    dp[1][2] = 1; // 2jump で 2step 登る.次は 2jump は使えない.
    dp[2][3] = 1; // 3jump で 3step 登る.次は 3jump は使えない.

    for (int i = 1; i < n; ++i) {
        // 1jumpする.
        dp[1][1] = (dp[1][1] + (dp[0][2] + dp[0][3])) % MD;
        // 2jumpする.
        dp[2][2] = (dp[2][2] + (dp[0][1] + dp[0][3])) % MD;
        // 3jumpする.
        dp[3][3] = (dp[0][1] + dp[0][2]) % MD;

        // dp配列をずらす.
        for (int u = 1; u <= 3; ++u) {
            for (int v = 1; v <= 3; ++v) {
                dp[u - 1][v] = dp[u][v];
            }
        }
        
    }
    return (dp[0][1] + dp[0][2] + dp[0][3]) % MD;
}

以上の改良により,時間計算量はO(N),空間計算量はO(1)になりました.

改良2

現在のdp配列の状態をx,次のdp配列の状態をyと表現すると,上のプログラムでやってることは次のように表現できる.

  • y_{1,1} = x_{1,2} + x_{1,3}
  • y_{1,2} = x_{2,2}
  • y_{1,3} = x_{2,3}
  • y_{2,1} = x_{3,1}
  • y_{2,2} = x_{1,1} + x_{1,3}
  • y_{2,3} = x_{3,3}
  • y_{3,1} = 0
  • y_{3,2} = 0
  • y_{3,3} = x_{1,1} + x_{1,2}

  • どうやら,y_{2,1}y_{3,1}y_{3,2}は要らなさそう. しかも,見るからに連立方程式なので,行列の形で書ける.

f:id:m_buyoh:20170623205005j:plain

6x6行列をAとすると,

  • 1段目に居るときのdp配列の状態{\boldsymbol s_1}=(1,0,0,1,0,1)^T
  • 2段目に居るときのdp配列の状態{\boldsymbol s_2}=A{\boldsymbol s_1}
  • 3段目に居るときのdp配列の状態{\boldsymbol s_3}=A{\boldsymbol s_2}=A^2{\boldsymbol s_1}
  • N段目に居るときのdp配列の状態{\boldsymbol s_N}=A^{(N-1)}{\boldsymbol s_1}

つまり,A^{(N-1)}が計算できれば良い.

累乗計算は愚直にやると線形時間掛かってしまうが,O(\log N) で解く手法が編み出されている.

以上の改良により,時間計算量はO(\log N),空間計算量はO(1)になりました.

多項式時間で計算できる最小頂点被覆問題(最小点カバー)について

読み返してみて,なんだか読みにくい……後日追記・修正するかもしれません.

最小頂点被覆問題ってなんぞ?

こんな感じの問題.

辺集合E,頂点集合Vから成るグラフGが与えられる.
頂点集合S⊆Vを考える.
全ての辺e∈Eが,Sに含まれる頂点に接続している時,SはグラフGの頂点被覆と呼ぶ.

集合Sの大きさが最小であるようなグラフGの頂点被覆Sを求めてください.

頂点集合に重みw:V \rightarrow \mathbb{Q}^+が割り当てられている場合があります. この場合,\sum_{v \in S}w(v)を最小化します.

また,この記事では,『与えられたグラフは単純グラフである』と仮定します.

計算機理論の勉強をする時に,NP完全の1つとして頂点被覆問題の例を挙げることが多いです.

競プロで役に立つの?

出題しました.

No.479 頂点は要らない - yukicoder

ネタばれが嫌いな人は先に解きましょう.

ナップサック問題と同様に,制約によって解き方が変わるので,トレーニングにはなるかな?

続きを読む

7か月GitHubのContributions埋めをしました

GitHubのプロフィールページの下の方にあるやつ

https://i.gyazo.com/54af416ff5154e4993871d2c51ba87d0.png

他の方がやっているのをブログで見て,自分もノリで始めていました.

続きを読む