結果

問題 No.1465 Archaea
コンテスト
ユーザー ID 21712
提出日時 2026-05-25 02:51:30
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 934 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,372 ms
コンパイル使用メモリ 278,260 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-25 02:51:49
合計ジャッジ時間 15,305 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var n,k int
	Scan(&n,&k)
	dp := make([]int, n+1)
	for i := range dp {
		dp[i] = 1e9
	}
	dp[1] = 0
	for i := 1; i < n; i++ {
		if i*2 < len(dp) {
			dp[i*2] = min(dp[i*2], dp[i]+1)
		}
		if i+3 < len(dp) {
			dp[i+3] = min(dp[i+3], dp[i]+1)
		}
	}
	if dp[n] <= k {
		Println("YES")
	} else {
		Println("NO")
	}
}

/*
考察

K回ちょうど、とかだったら
N = 2^y + 3 * ( x[1] * 2^y + x[2] + 2^(y-1) + ... + x[y]*2^1 + x[y+1]*2^0 )
から
(N - 2^y) / 3 = x[1] * 2^y + x[2] + 2^(y-1) + ... + x[y]*2^1 + x[y+1]*2^0
N >= 2^y
(N - 2^y) ≡ 0 (mod 3)
K = y + x[1] + x[2] + ... + x[y] + x[y+1]
で
(N - 2^y) / 3 >= K - y
で
x[y+1] = K - y を割り当てたあと不足分をx[1]のほうから貪欲に埋めていくとかで、できそうな？

質問のとこで0回以上K回以下と書いてあるから
普通に1から操作繰り返す動的計画法で求めるぽそう


*/
0