AtCoder Beginner Contest 188 C,E,F問題メモ

C - ABC Tournament

問題

  • $2^N$ 人でトーナメントを行う
  • トーナメント表で左から $i$ 番目の人のレートは $A_i$ で、各試合では $A_i$ が大きい方が勝つ
  • 準優勝する人が左から何番目の人だったか答えよ
  • $1 \le N \le 16$
  • $A_i$ は全て異なる

解法

やってることが、まんま最大値を求めるセグメント木の初期化だったので、ついそれ貼ってしまった。

よく考えたら左半分と右半分の最大値勝負でいける。

Python3

E - Peddler

問題

  • トポロジカルソートされた $N$ 個の都市と $M$ 本の有向道路が与えられる
  • 都市 $i$ では、金が1kg $A_i$ 円で売買されている
  • 行商人が、好きな都市で金を1kgだけ買い、そこから道路を辿って行ける他の都市で売る
  • 行商人が得ることのできる最大利益(売却額-購入額)を求めよ
  • $2 \le N \le 2 \times 10^5$

解法

先頭から考えてもいいんだけど、後ろから考えた。

  • $DP[i]=$ 都市 $i$ から到達できる都市($i$ を含めて)の中で、最も高く売れる都市の売却額

こうして後ろから $i$ を埋めていく。

都市 $i$ で買ったときの最適な売却額 $S_i$ は、都市 $i$ から直接道がつながる都市 $j_1,j_2,\ldots$ の中で、最も $DP[j]$ が高いもの。(無い場合は0とでもしておく)

よって、ここで買った場合は $S_i-A_i$ 円の利益を手にすることができる。

また、$DP[i]=\max(A_i, S_i)$ として更新しておく。

各都市についてこれを調べ、最も利益の高いものが答え。

買った都市と別の都市で売らないといけないので、$DP[j]$ の情報を取得する→利益を求める→$DP[i]$ を更新する という順番に注意。

Python3

F - +1-1x2

問題

  • 以下の操作を繰り返して、整数 $X$ を $Y$ にする最小手数を求めよ
  • 操作
    • $X$ に1足す
    • $X$ から1引く
    • $X$ を2倍する
  • $1 \le X,Y \le 10^{18}$

解法

少し前に、より操作の種類が増えた類題がAGCで出題されていた。(LINK

愚直には整数の値をそのまま頂点とした幅優先探索やDijkstraで解けるが、$X,Y$ が大きすぎるのでアウト。

ここで操作の性質に着目すると、「2倍してから+1を2回」するくらいなら「+1してから2倍」した方が絶対によい。
したがって、「一度2倍する操作をしたら、そこからは+1,-1は連続しては使わない」ということがいえる。

これにより、操作を大幅に限定することができる。

しかし、それでも最初に2倍する操作までは何回足したり引いたりすればいいかわからない。

これは、操作を逆から考えることで求めることができる。

  • $Y$ から1引く
  • $Y$ に1足す
  • $Y$ を半分にする(割り切れる場合のみ)

こうすると、以下の2種類の操作で、$Y$ を必ず約半分にできる。

  • $Y$ が偶数の時、半分にする
  • $Y$ が奇数の時、+1または-1してから半分にする(2通りに遷移する)

そして、$Y$ が十分 $X$ に近づいたら、そのときの $|Y-X|$ が「最初に足したり引いたりすべき回数」となる。

まぁ、「十分近づいたら」といっても厳密にどのタイミングかわかりづらいので、「とりあえず訪れた $Y$ があったら毎回 $|Y-X|$ を計算しといて、その中の最小値が答え」としてよい。 調べるのは $X \le Y$ の間だけでよくて、最大でも $\log_2{10^{18}}=60$ 回程度でたどり着ける。

調べることになる状態数を考える。

$Y$ が奇数の時に2通りに遷移するので、最悪の場合 $2^{60}$ 回程度になる?とか一瞬思ってしまうが、このときに遷移する2つの状態は隣り合っているので、多くがかぶる。

例えば、$Y=63$ とすると、

63 → (31, 32) → (15, 16) → (7, 8) → (3, 4) → (1,2) → 0

というように、2で割った回数が同じ数字は、たかだか2つしかない。よって調べる状態数はせいぜい120通りくらいしかない。

Python3

programming_algorithm/contest_history/atcoder/2021/0110_abc188.txt · 最終更新: 2021/01/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0