bobuhiro11's diary

ABC 173 E - Multiplication 4

06 Jul 2020

提出したコード

コンテスト後追加されたテストケース after_contest01.txt でコケた。 それ以外は自力で通ったので考察の詰めが甘かった。 まず、(A)答えが負となる場合と(B)答えが非負となる場合で場合分けをする。 (A)の場合には、絶対値の小さい順に貪欲にとればよい。(B)の場合を考えていく。まず、キューを2つ用意しておく。

  • 非負な値を降順にソートしたもの(例:9 6 5 2 1 0 0)
  • 負な値を昇順にソートしたもの(例:-8 -7 -3 2)

単純に、負数同士の積は正という性質を使う。 $K$が2個以上残っている場合には、2つのキューからそれぞれ2つの値を取り出して、大小比較をする。 例えば、$9 \cdot 6 = 54 < -8 \cdot -7 = 56$ であれば、負数のキューから2つ値を取り出せばよい。 一方で、非負なキューのほうが大きい場合には、非負のキューから1つ値を取り出せばよい。 繰り返しになるが、非負なキューから取り出す場合には、1つの値だけでよいことに注意する。 https://twitter.com/shirakia/status/1279773457413074944で例が言及されている。after_contest01.txtもこのケースに該当しそう。

そのあとは、非負なキューからとる場合は1つずつ、負なキューからとる場合は2つずつのペアとして、取り出していけばよい。 (B)の計算途中で、どうしても答えを正数にすることができない場合には、(A)の結果を答えとする。


ABC 172 F - Unfair Nim

05 Jul 2020

提出したコード

前提知識として、Nimというゲームであることを知っておくと良い。Nimには必勝法があり、すべての山の石の数 $A_i$ についてXORをとり、その結果が0以外であれば、その手番の人が最適な動きを取れば必ず勝つ。 必勝状態であるXOR != 0で手番が回ってきたとき、ある山からある数の石をうまく取り除くと、XOR = 0の状態に遷移できる。 逆に、XOR = 0の状態からは、どんな選び方をしても、必ずXOR != 0 の状態(必勝状態)に遷移してしまう。 ターンの経過に伴って石の数の合計は減っていくので、必ずゲームは終わる。 Grundy数というらしい。

これをふまえて、考察を進める。「1番目の山から0個以上$A_1$個未満の石を2番目の山に移すことで …」とあるので、先頭二つの山についてのみ考えればよいことがわかる。なので、これ以降$A=A_1$、$B=A_2$、$X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$とする。また、”移す”という操作を$A$を$a$、$B$を$b$に変更すると言い換える。そうすると、以下の条件を満たしつつ、できるだけ$a$を大きくすればよい(”移す”石の数が最小)ということになる。

\[a + b = A + B = S \\ a \oplus b = X \\ 1 \leq a \leq A \\\]

これは桁DPによって解くことができる。$dp_{i,j,k}$を、下から$i$桁目まで見たときの$a$の最大値とする。 ただし、一つ上の桁に対して繰り上がりがある場合は$j=1$、$i$桁目まで見たときに$a$が$A$を上回っていれば$k=1$とする。 50桁くらいまで見れば十分。

提出コードにコメントをつけておく。初期値は以下の通り。

rep(a, 2) {
  ull b = a ^ (X & 1); // b は a から決まる
  ull carry = a & b;
  ull _sum = a ^ b;
  if (_sum != (S & 1)) continue; // そもそも合計がS出なければスキップ
  ull over = a > (A & 1);
  chmax(dp[0][carry][over], a);
}

dp[i][j][k]からの遷移は以下の通り。配るDPなので i + 1 桁目について見ていく。

rep(i, M-1) rep(j, 2) rep(k, 2) rep(a, 2) {
  if (dp[i][j][k] == -1) continue;
  ull ni = i + 1;
  ull b = a ^ ((X >> ni) & 1); // b は a から決まる
  ull _sum = (a + b + j) & 1;  // 合計を計算する場合には下の桁からの繰り上げを考慮する
  ull _carry = ((a + b + j) & 2) > 0; // ni+1 桁目に対して、繰り上げがあるかどうか求める
  if (_sum != ((S >> ni) & 1)) continue; // そもそも合計がS出なければスキップ
  ull over;
  if (a >  ((A >> ni) & 1)) over = 1; // ni桁目まで見たとき、a が A を上回っているかどうか求める
  if (a <  ((A >> ni) & 1)) over = 0;
  if (a == ((A >> ni) & 1)) over = k;
  chmax(dp[i+1][_carry][over], dp[i][j][k] | (a << ni)); // dpを更新
}

自力では解けなかった。解説動画が分かりやすくて本当に助かっている。


KVM TLB Shootdown Preemption メモ

01 Jul 2020

KVM FORUM 2018 で発表されたTowards a more Scalable KVM Hypervisorについてのメモ。

[PATCH v8 0/4] KVM: X86: Add Paravirt TLB Shootdown

ゲストOSはOSレベルの同期機構であるTLB shoot downやRCUの処理において、ホストOSのスケジューラの影響を受ける。ベアメタル環境であればすぐに完了する操作であっても、仮想環境上ではその遅延を無視することができなくなる。

TLB(Translatoin Lookaside buffer)は仮想メモリアドレスと物理メモリアドレスのマッピングをキャッシュするために使われる。あるCPUがそのマッピングを切り替えたとき、その以外のCPUでTLBをflushしなかればならない。これを TLB shoot down と呼ぶ。

モダンなOSでは、TLB shoot down はパフォーマンスクリティカルな箇所として位置づけされ、この処理によって遅延が発生しないようチューニングされている。TLBのflushはすぐさま完了するという前提で、IPI(Inter Processor Interrupt)で実装されている。Remote CPUのTLB flushの完了は busy wait で待っているため、ベアメタル環境とは相性が良い。一方で、仮想環境ではvCPUが別のゲストに横取りされたり、実行がブロックされたり、ということが起きるため、長時間にわたって busy wait が継続することになる。

この問題は、準仮想化TLB shoot down によって解決できる。準仮想化TLB shoot down では、動作していないvCPUに対する操作を遅延させておいて、次回そのvCPUが起動するときに、KVMがTLB flushを担当する。特にオーバコミットされた環境で顕著なパフォーマンス向上が見られる。

ゲストとホストどちらからも参照できるメモリ領域に「あるvCPUが preempt されたかどうか」を示すフラグを用意しておく。pv_mmu_ops.flush_tlb_others関数は、アクティブなvCPUに対してはIPI経由でTLB Flushの通知を送り、そうでないvCPUに対してはKVM_VCPU_FLUSH_TLBフラグを付与しておく。その後、KVMはKVM_VCPU_FLUSH_TLBフラグがついているvCPUを起動する際に、INVVPIDを発行する。VM数が増えるに従ってこのチューニングの効果が顕著に現れる。


Civilization VI 初心者のメモ

30 Jun 2020

一度Civilization VIを友人とやった結果、どうやらこのままだと勝てそうにもないので、ちょっと調べてみる。 このゲームは選択の連続なので、仕組みを知らずになあなあで進めてしまうと勝つのは難しそう。 あくまでも初心者が自分のために書いていくメモなのであしからず。 詳しく知りたい方は CIVILIZATION VI wiki を見てください。

まず、マップオプションから、グリッド、資源アイコン、算出アイコンを表示するよう設定しておく。 都市そのものを強化するリソースが、食料と生産力。食料を増やすことで人口が増え、生産力を増やすことで区域・建造物の生産につながる。生産力は、労働者が鉱山を作ることで得られる。ゴールド・科学力・文化力は、市場(商業ハブ区画)、図書館(キャンパス区画)、円形闘技場(劇場広場区画)から得られる。

序盤の戦闘に有利なアステカ、アメリカ、シュメール、ヌビア、ローマ、クリー、インカが、初心者に向いている。 初期配置に癖のあるヌビア、エジプト、マリ、ロシア、カナダ、イギリス、インドネシア、スペイン、ノルウェー、オランダ、フェニキア、マオリなどは難しい。また、宗教メインな文明や、特殊なプレイングが必要な文明も向いてない。 ドイツが扱いやすいそうに感じる。固有区域ハンザが単純に強い。区域はハンザ>キャンパス>商業ハブくらいで立てていく。

序盤は、斥候、労働者、戦士、開拓者で進めていく。 都市が川や湖に隣接していると住宅+3なのでよく吟味する。ユニットの中ではチャリオット(のちの戦車)、弓兵(のちの野戦砲)が強い。 丘陵地帯は生産力が強力なので、そこを狙って都市を作る。 都市を作った後は、市民管理で手動で人をどのタイルに配置するか決めることができるので、定期的に見直すと良い。 労働者はむやみに使わず、必要な時まで眠らせておけばよい。 市民+2の住宅が必要で、それを下回るとペナルティが発生して、都市の成長が妨げられる。 交易商は強力なので、作れるタイミングなら優先して作る。 太古の遺産はピラミッド、アポロン神殿が強い。 それ以降の時代では、ペトラ、コロッセオ、アルハンブラ宮殿、チチェン・イツァ、 グレート・ジンバブエ遺跡、紫禁城、ポタラ宮、アルセナーレ・ディ・ヴェネツィア、ビッグベンが強い。

戦争中は勝つまで兵の増強をやめない。相手も兵の生産に集中しているはずなので。 遠距離攻撃する場合は、移動力が1以上残っていれば攻撃可能なので、ヒットアウェイで戦う。

その他

  • 最初期の探索は重要
  • 都市で役割分担
  • 都市数ペナルティがないので、単純に大量に都市を作ると強い
  • 都市の人口は住宅数に制限されるため、食料よりも1人口あたりの生産力重視
  • 3つの山岳があれば、キャンパス区画を作る
  • 丘陵と鉱山で早期生産
  • 遺産は奪う
  • 高級資源は売りつける

ABC 171 F - Strivore

25 Jun 2020

提出したコード

解説を漁ってみると、どうやらアルファベットを適当に$K$回挿入したあとの 長さ$N+K$の文字列の中で、$S$の各文字の位置が固定されていると考えればうまくいくということだった。 そう考えると、あとは長さ$N+K$の文字列で$K$文字をどうやって挿入していくかだけを考えれば良い。

入力例1を使って考える。

  • S = “oof”
  • N = len(“oof”) = 3
  • K = 5

例えば、位置1に’o’、位置3に’o’、位置5に’f’をおいてみる。 また、長さ$N+K$の文字列を先頭から見たときに”oof”がはじめて登場するのがこれらの位置ということにする(条件1)。 このとき、位置0には’o’以外の25種のアルファベットを挿入できる。 逆に、位置0に’o’を挿入するのは、条件1を満たさないのでダメ。 同様にして、位置2にも’o’以外の25種のアルファベットを挿入できる。 また、位置4にも’f’以外の25種のアルファベットを挿入できる。 位置6と7に関しては、特に制約がないので、26種のアルファベットを挿入できる。

まとめると、’f’の位置$j$が$N-1 … N+K-1$まで移動したとき、 2つの’o’が取れる位置の組み合わせは${}_j C _{N-1}$ となる。

また、25種のアルファベットを挿入する位置は$j - (N-1) $個、 26種のアルファベットを挿入する位置は$(N+K-1)$個、となる。

つまり答えは$\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$となる。