buyoh.hateblo.jp

競プロ参加記録.開設したばかりなので暫くお待ちください.

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

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

続きを読む

Python3の勉強をyukicoderでやる

pythonは正直あまり好きな言語ではなかったのですが,numpyが魅力的すぎるため,競技プログラミングで少し勉強してみました.

大学の講義内容がさっと手元で動かせないんですよね.octaveは重すぎるし.

記事を書いている人の前提知識度

昔に少しだけ書いたことがあります.簡単なゲームを作りました.

notepad.exe [WP]no.014 python独習

『なんかブロックをインデントで判定してる』『タプルとかリストとかの概念がある』という雰囲気は覚えてますが, 実用面は全く忘れました.

solve

No.268 ラッピング(Easy) - yukicoder

  • http://yukicoder.me/submissions/174424
  • 昇順,降順ソートしたい問題.
  • Python2とPython3でかなり違うらしい.input()ですら違いがある.
  • aa.sort()でリストをソートできる.reverse=Trueと指定すれば逆順になる.
    • 辞書っぽい引数の指定面白い
    • 破壊的.破壊出来ないリスト(例:10行目)に対してソートしたい場合,sorted(arr)をやる.
  • range(N)は,Rubyでいう(0...N)みたいなもの
  • print aという記法はPython3では使えない.

No.136 Yet Another GCD Problem - yukicoder

  • http://yukicoder.me/submissions/174503
  • Kは2に固定して良い.あとは全ての組み合わせを全探索する.
  • PyPy3がRuntimeError.math.gcdを使うにはバージョンが足りないらしい.
    • Python3は通った.
    • import mathすると使える.
  • 割り算をすると,例え整数同士でもFloat型になる.
    • int(nm)でキャストできる.
  • maxは普通に関数として使える.Rubyみたいなインスタンスメソッドではない.

No.80 四角形を描こう - yukicoder

  • http://yukicoder.me/submissions/174509
  • 思考停止全探索.xとyを適当に全部回す.
  • if x*2+y*2>l : continueみたいな書き方ができる.HSP*1っぽい.
  • 提出コードからは消したけれども,プログラムを中断させたいときは,import sysしたうえでsys.exit()する.
    • うっかりsys.exitと書くと終了しない.

No.204 ゴールデン・ウィーク(2) - yukicoder

  • http://yukicoder.me/submissions/174566
    • 途中で実装方針を変えたため無駄な記述がある.
  • D日すべて使う必要があるかどうかが問題文・テストケースから分からない・・・と思ってたら『最大』って書いてあった.
    • test13.txtを見れば分かるように,D日すべて使う必要は無い.
  • 有給休暇を挿入する始点xを全探索する.
  • input()は改行文字を含まない.
  • ++var+ + varとして解釈される.もちろんvar++はエラー.
  • strのi番目の文字はstr[i]として取り出せるが,書き換えは出来ない.
    • 文字列の部分書き換えをするには,str[:i]+'o'+str[i+1:]と書く必要がある.
  • Ruby同様,文字列の掛け算ができる.
  • 文字列の範囲に-1を指定すると,末尾を指定したことになる.Rubyと同じ.

No.77 レンガのピラミッド - yukicoder

  • http://yukicoder.me/submissions/174570
  • 理想のピラミッド△を作っておいて,差分を求めることでコストを得ることができる.あとは全探索.
    • 予めブロックが足りるかどうか判定したうえで,『ブロックを除去する』を1コスト,『ブロックを積む』を0コストとして計算.
  • sample5.txtのように,フィールドは無限大に広いものとして考える必要がある.しかし,制約から199で抑えて良い.
    • 提出コードではaa+=[0]*100という感じで無理やり増やしてる.
  • sum(aa)で総和が取れる.
  • 0Falseとして解釈される.

No.290 1010 - yukicoder

  • http://yukicoder.me/submissions/174571
  • http://yukicoder.me/submissions/174573
  • 00,11,0101,1010が存在するかどうか調べる.
  • 存在するかどうか調べるために,正規表現を使う.
    • import reをしておく.正規表現リテラルなんてものは無い.
    • r'str'と書くと,\エスケープしなくなる.
    • re.match(r,s)を使うと,先頭からのマッチしか判定しない..*を加えるか,re.search(r,s)を使う.
      • re.search(r,s)なら場所が分かる.ただし,先頭マッチ時は0が返ってFalse扱いになるので,Noneと比較する.

*1:HotSoupProcessor

4ACした(21ACする:その2)

次の未だ解いていない問題をターゲットに13AC(21-8)する.

  • yukicoder☆2(コンテスト中を除く)
  • yukicoder☆3,4
  • AtCoder ARC C(コンテスト中に解けなかったものだけカウント)
  • AtCoder ARC D,E,F
  • AtCoder AGC B,C,D
  • codeforces 不問(A問題でもカウント.英語補正)
  • codeIQ ☆3以上

問題名はリンクになっており,クリックすると問題ページに飛べます.

No.41 貯金箱の溜息(EASY) - yukicoder

  • http://yukicoder.me/submissions/174158
  • 1円以外の通貨は111111の倍数なので,111111で割っても同じ問題で考えることができる.
  • 割った後の値は105ぐらいまで落ちるので,普通の動的計画法が使える.
  • …はずだが,その部分がうまくできず,解説見た.
    • (111円を1個,222円を1個,111円を1個.という数え上げも含めてしまう…で悩んでた)

Problem - C - Codeforces

No.102 トランプを奪え - yukicoder

  • http://yukicoder.me/submissions/174234
  • nim
  • 愚直に出来ず工夫がいる.カードの枚数を4で割った余りとしても良いことに気づく必要がある.
    • 弱体化デバフを掛けてメモ化再帰して解く問題は少なくないっぽい

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder (ノーカウント)

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder

  • http://arc074.contest.atcoder.jp/submissions/1299054
  • 最大流問題.初めてF解いた.
  • 解説と若干異なって見えたので,詳しく書く.
  • 『今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプする』を『今乗っている葉と同じ行,列に移動できる廊下がある』と読み替えたい.
  • Mを足場の数とする.頂点数2HW+H+W,辺の数5M
  • 全てのセルのそれぞれ(y,x)に2つの頂点U_{(y,x)}V_{(y,x)}を割り当てる.
  • 各行に頂点R_{y},列に頂点C_{x}を割り当てる.
  • もしtex:(y,x)]に足場があるなら,
    • U_{(y,x)}からV_{(y,x)}へ流量1の辺をつなぐ.
    • V_{(y,x)}からR_{y}V_{(y,x)}からC_{y}へ流量infの辺をつなぐ.
    • R_{y}からU_{(y,x)}C_{y}からU_{(y,x)}へ流量infの辺をつなぐ.
  • V_{S}からU_{T}への最大流量を解く.