Kuin で 競技プログラミング(yukicoder No.4 おもりと天秤) の問題を解く
2019/02/15 追記:
コードが動かなくなっていたので,書き直しました.
#316677 No.4 おもりと天秤 - yukicoder
math@knapsackを使ったバージョンも載せます.
#316679 No.4 おもりと天秤 - yukicoder
Kuinとは?
「Kuin」は、簡単で高速な実用プログラミング言語です。
- オブジェクト指向言語.
- 2D,3D描画を標準でサポート.
- 2017/9/17に完成版としてリリース.
割と前から存在している言語で,競プロ界隈にも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
コメント以外の補足など.