buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

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

2019/02/15 追記:

コードが動かなくなっていたので,書き直しました.

#316677 No.4 おもりと天秤 - yukicoder

math@knapsackを使ったバージョンも載せます.

#316679 No.4 おもりと天秤 - yukicoder

Kuinとは?

プログラミング言語「Kuin」

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

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

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

yukicoder No.4 おもりと天秤

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

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

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

コード

入出力の部分だけ読めれば良いです.

https://yukicoder.me/submissions/207708

func main()

    ; おもりの数
    var n: int
    ; おもりの重さ
    var ww: []int
    
    var ww_str: [][]char
    
    ; = STDIN読み込み ============
    
    ; 文字列を読み込み,整数に変換してnに格納する
    ; 何故か参照として渡す仕様に注意
    do cui@input().toInt(&n)
    ; 文字列を読み込み,半角スペースで区切ってww_strに格納する
    do ww_str :: cui@input().split(" ")
    
    ; 配列wwの動的確保
    ; # は,インスタンス生成を表現する.
    do ww :: #[n]int
    
    ; forループ.cntはブロック名.変数ではないので代入不可.
    for cnt(0, n-1)
        ; ww_str[cnt]を整数に変換して,ww[cnt]にセットする.
        do ww_str[cnt].toInt(&ww[cnt])
    end for
    
    ; = 以降,動的計画法 ============
    
    var dp: []bool :: #[10001]bool
    
    do dp[0] :: true
    for i(0, n-1)
        var w : int :: ww[i]
        for c(10000, 0, -1) {逆順ループ}
            if (dp[c])
                do dp[c+w] :: true
            end if
        end for
    end for
    
    var sum: int :: 0
    for i(0, n-1)
        do sum :+ ww[i]
    end for
    
    {
    if (sum%2 = 1 | dp[sum/2] = false)
        do cui@print("impossible")
    else
        do cui@print("possible")
    end if
    }
    ; 横に長くなってしまい,改行したいときは | を使う
    do cui@print(
    |   (sum%2 = 1 | dp[sum/2] = false)
    |   ?("impossible", "possible")
    | )
    
end func

コメント以外の補足など.

  • cuiライブラリを使うが,インポートはコンパイル時(?)に自動的にされる.
  • 文は必ずキーワードから始まる.代入,関数呼び出しの場合はdoを付ける.
  • listならforEachがある.

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

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

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