AtCoder Grand Contest 051 (Good Bye rng_58 Day 2) A,B問題メモ

AtCoder Grand Contest 051 (Good Bye rng_58 Day 2)

コンテスト前におさけをのむとひらめきりょくがあがります。(代わりにその他の全能力が下がります)

A - Dodecagon

問題

  • 1辺が1の、正三角形と正方形のタイルがたくさんある
  • タイルを隙間無く敷き詰めて、1辺の長さが $d$ の正十二角形を作る並べ方が何通りあるか $\mod{ 998244353 }$ で求めよ
  • $1 \le d \le 10^6$

解法

こういうのは制約のある部分=外周から埋めていくのがセオリー。
フリーハンドで図を書いて試すのが難しいが、がんばる。CAD使えたら強そう。

直線部分は、正方形を置いたら隣に正三角形は並べられず、逆も然りなので、片方だけをずっと敷いていくしかない。
逆に角は、正十二角形の1つの内角が150°なので、正方形と正三角形を置いたらちょうど埋められる。

【下辺が直線になるように敷き詰めたい】

     ↓この30度の隙間は埋められない
×: □△

○: □□□  or  △▽△▽△  しかない

【角を埋めたい】

□▷
 ↑ここが150°となり、ちょうど正十二角形と合う

どこか1個の角に正方形と正三角形を置き、埋められない角が出来ないように外周を連鎖的に決めていくと、 辺ごとに正三角形と正方形を交互に敷き詰めると綺麗に埋まり、逆にこれしかないことがわかる。

その時、内側にはまた十二角形が出来るのだが、正三角形を敷き詰めた辺のみ $d-1$、正方形を敷き詰めた方は $d$ のままという形になっている。

内側の十二角形は同じ理屈で外周を交互に敷き詰めることで埋められて、さらに内側には同じように、正三角形を敷き詰めた辺のみ長さの1減った十二角形ができる。

$(d,d)→(d-1,d)→(d-2,d)→(d-2,d-1)→\ldots→(0,0)$ というように、どちらかを1減らしながら $(0,0)$ になるまでの経路数と考えられ、二項係数 ${}_{2d}C_{d}$ と一致する。

回転させての重複を除いて、この半分が答え。

Python3 小さいサンプルでの実験コード

Python3 解答コード

寄木細工の職人さんとか、経験的に知ってたりするのかな。

B - Bowling

問題

  • 広い空間に、ボウリングのピンを置く
  • $A,B,C,D$ の4人が、それぞれ →,↗,↑,↖ 方向からこれを見る
  • 重なっている後ろのピンは見えない(厳密には問題ページ参照)
  • それぞれから見える本数を $a,b,c,d$ とすると、$d \ge 10 \max(a,b,c)$ となるような配置を1つ構築せよ
  • 置ける本数は $10^5$ 本まで

解法

ボウリングで1-5や2-8など縦に2つ並ぶように残った形は真正面から狙いたくなるが、その場合本当に真正面から当てないと前のピンに弾かれて後ろが残りやすい。 なるべくナナメから狙った方が許容範囲が広い。

$A$ と $D$ だけ考えると、少なくとも10本は必要。

A→  ○○○○○○○○○○
                         ↖D

$C$ を考慮に加えると、$A$ から重なって見えている2本が $C$ からも重なって見えることはないので、10行に増やして対処する。
その際、$D$ からは増やした行を含めて全て重ならないように、行の間を十分空ける。

     ○○○○○○○○○○
     ↕10行
     ○○○○○○○○○○
     ↕10行
A→  ...
     ↕10行
     ○○○○○○○○○○
              ↑C        ↖D

更にこの大きな塊を10回 ↗ 方向に繰り返すと、それが答え。 使うピンの本数は1000本。

Python3

本数最小化チャレンジ

どうも、⊿ の形が強いらしい。$A,B,C$ からは2本、$D$ からは3本見える。

これをフラクタルのように(重ならないように多少ずらしつつ)繰り返すと、

  ⊿      A,B,C: 4本
⊿⊿      D    : 9本

      ⊿
    ⊿⊿  A,B,C: 8本
  ⊿  ⊿  D    : 27本
⊿⊿⊿⊿

と、$A,B,C$ は2倍、$D$ は3倍になっていく。よって6段階目に64 vs 729 となり、比が10倍を超える。

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2020/1227_agc051.txt · 最終更新: 2020/12/28 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0