buyoh.hateblo.jp

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

Kuin で 競技プログラミング(yukicoder No.4 おもりと天秤) の問題を解く

※解き方の解説はしません.

Kuinとは?

プログラミング言語「Kuin」 - Kuina-chan

「Kuin」は、簡単で高速な実用プログラミング言語です。

割と前から存在している言語で,競プロ界隈にもKuinの話題が流れている*1ようです.

しかし,Googleで検索した*2ところ,競技プログラミングの問題を実際に解いた記事はありませんでした*3

yukicoder No.4 おもりと天秤

https://yukicoder.me/problems/no/4

問題概要:daveを授業に集中させろ.

*1:本人も言及https://twitter.com/kuina_ch/status/913934988927578112

*2:2017/10/05に「競技プログラミング Kuin」で検索

*3:ほとんどのジャッジ環境がLinuxであり,2017/10/05現在Windows環境でのみ動作するKuinの導入がほぼ不可能であるため.

続きを読む

AtCoder Regular Contest 028 - B 特別賞

別解法シリーズ.別解で通すのは楽しいよ.

問題

arc028.contest.atcoder.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)になりました.