2021年 1月 11日

まえがき

新年あけましておめでとう.

Screenshot from 2021-01-11 03-26-47

精進をシナイトレートが下がりますね…

傾きが大きい(正の方向に)ところが2箇所あるじゃないですか,

そこ,レート上がってますよね.

それ以外はコンテストだけによる精進scoreの上昇なんですが,レートが停滞or 下がってますね.

健康管理

食べたもの - 食パン - ホットケーキ - ポテトチップス - ポテト - 牛乳 - コーヒー

今日解いた問題

ABC188 F-+1-1x2

[DFS,深さ優先探索,数字操作,メモ化再帰]
これ難しくないですか.難しいですね.

(解説ではないです)

km*pさんの解説記事を読んだのですが,x->yにするとき,yの方が小さいならば,-1の操作だけしかしなくて良い.というのも忘れちゃいけませんね.
まあここではy->xにすることを目指すので,y < x のときは +1の操作だけでxにする.ってことですね.

今, y -> x にするにあたって使える操作は3つ

+1する
-1する
/=2する

で,なんか,公式の解説で

k回(k>=2)回1を足してから2で割るよりも,k-2回1を足してから2で割り, 1回1を足した方が、同じ結果で操作回数が少ない(1を引くときも同様)

って言ってるんですけど,これがよく理解できませんでした.
まぁこれ,k>=2とかいう条件あるけど,これk=2のときって,2回1を足してから2で割るよりも,0回1を足してから2で割り,1回1を足した方が良い.って言ってるんですよね.
つまり,『1を足す(1を引く)前に割れやカスぶち殺すぞ』って言ってるんですよね.(間違いない)

で,これぶっちゃけ,はぁ?なんでやねん?お前が死ねやカス.って思うじゃないですか.

そこで俺は考えました(能ある鷹は脳を使うので)
まず,値AをBにしたいです.今,(A+K)/2 = Bになるとします.(このときの操作は,K回1を足して2で割るのでK+1回)

次に,もう一つBにするための方法として,
(A+(K-2))/2 +1 = B (K-2回1を足した後に2で割って, 最後に1を足す)があります.

え,2個目の方法は本当にBになってるのか確認したい?任せろ.
(A+(K-2))/2 +1 = (A+(K-2)/2 + 2/2) = (A + (K-2) + 2) / 2 = (A+K) / 2= B (1個目の操作方法と一致した)

ね,一致したね.

じゃあ,操作回数を数えようK-2回1を足した後に2で割って, 最後に1を足す) なので,K-2 + 1 + 1 = K なので,K回の操作回数が必要ですね.

ここで確認,1つ目の操作方法は,K回1を足して2で割る(操作回数はK+1)

2つ目の操作方法は,K-2回1を足して2で割って1足す(操作回数はK)

お~!確かに操作回数減ってるね!!

ってことで,A->Bにするための操作方法として次はK-4回1を足した後2で割って2を足して見ようか

(A+(K-4))/2 + 2 = (A+(K-4) + 4) / 2 = (A+K)/2 = B
これの操作回数はK-4 + 1 + 2 = K-1回ダ!!(2つ目の操作方法より更に1回減った!!)

まあ,こんな感じで,何となく+1する操作をするよりも先に,割る2をしちゃえ.って言うのが感覚でつかめたと思う
(俺は数学がわからないから感覚で理解できればそれでいいや)

ってことで,操作方法の優先順位は

Aから値Bにを大きくしたいなら,B-A回の+1操作
2で割れるなら2で割る
(2で割れないなら)
1. +1をしてから2で割る
2. -1をしてから2で割る
この2つの内,より早くxになれる方を採用する

で多分okです.

ll x;
map<ll, ll> memo; // memo[i] := i から xにするときの操作回数をメモ
ll dfs(ll y){   // y -> x のときの操作回数の最小値を返す
  if(memo.count(y)) return memo[y];
  if(y <= x) return memo[y] = x - y;
  // ここから先は, y > x の場合
  memo[y] = y - x;
  if(y % 2 == 0){
      memo[y] = min(memo[y],1+dfs(y/2));
  } else {
      // +1 してから/2 と -1 してから /2
      memo[y] = min(memo[y],dfs((y-1)/2) + 2); // +1と/2の操作なので+2回ぽよ
      memo[y] = min(memo[y],dfs((y+1)/2) + 2);
  }
    return memo[y];
}

まあなんか,計算量とか再帰の呼び出し回数とか,頭が壊れるから,強くなってからでいいや…

memo[y] = y - x;は,-1だけでxにするときの操作回数やね

なんでこれが必要なのかは分からない!!

あとがき

精進しないとレートが下がる...

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)

草体にぼ日記

だらだらと

2021年1月11日　日記