JAG Summer 2018

Japan Alumni Group Summer Camp 2018 Day 2

A - 10^N+7

• 以下の条件を満たす最小の正整数を答えよ
  • 17で割ると$x$余る
  • 107で割ると$y$余る
  • 1000000007で割ると$z$余る

全通り試しても知れている。試す際はループ回数が少なくなるよう、$z$ からはじめ、1000000007ずつ加算して17と107の余りを確認する。

一応、2数なら機械的に求める方法がある。17と107に絞って考えると、

答えをnとおく
107k + y = n
5k + y = n mod 17
mod17で5の逆数を探すと、7
k + 7y = 7n mod 17

x = n mod 17
k + 7y = 7n = 7x mod17
k = 7(x-y) mod17

これによりkを求め、nを求める。

B - Coins

• 1,5,10,50,100,500円硬貨が無限にある
• 関数 $f(x)$ は、$x$ 円を硬貨で支払うことができる最も少ない枚数を返す
  • $f(18)$ なら、$1+1+1+5+10$ の5枚で支払うのが最小なので、5を返す
• $N$ が与えられたとき、$f(x)=N$ となるxは何通りか

500円以上の部分は500円硬貨で支払うことになる。

1円,10円,100円は0～4枚、5円,50円は0～1枚しか使えないので、500円以外の硬貨は使っても14枚まで。

0～14枚の場合のパターン数を求めておくと、$0～min(14,N)$ のパターン数の合計が答え。

C - Equiangular

• 正 $N$ 角形のいくつかの頂点を結んで等角多角形はいくつ作れるか
• 合同な図形は1つと数える

等角 $m$ 角形は、正 $m$ 角形からどれかの辺を平行移動を繰り返して作れる。 だが、平行移動した先にも $N$ 角形の頂点がちゃんとあるか、と考えると難しい。

ここは視点を変えて、「結んだ頂点はいくつ先か」に着目する。

頂点に時計回りに数字を振った時、1と3を結ぶと「2点先」である。

正 $N$ 角形からいくつかの頂点を結んで $m$ 角形を作る時、頂点の角度は両側の頂点がそれぞれ「何点先」かに依存する。

例えばある頂点について、左側の頂点が $a$ 点先、右側の頂点が $b$ 点先で、為す角が $\theta$ だとする。

その時、左側の頂点を中心に考えると、右側の頂点（つまり↑の頂点）が $a$ 点先、角度が $\theta$ であることは確定で、左側の頂点を決めなければいけない。これは、$b$ 点先しかない。

これを連鎖的に考えると、「順に何点先を拾っていくか」の列は $[a,b,a,b,...,a,b]$ か、$[c,c,...,c]$ の2パターンしかない。

この列はいずれも合計が $N$ となるように決める。

よって、$N$ の約数を列挙すると、

• 約数自体が $c$ に相当するため1通り
• 約数を $a+b$ （どちらも1以上）に分解するパターン数で $(c-1)/2$ 通り

正1角形、正2角形は無いことに注意しつつ、以上を数え上げればよい。

F - Point Sequences

• 2次元平面上の点を考える
• 3つの $N$ 点列 $\{a_0,...,a_{N-1}\},\{b_0,...,b_{N-1}\},\{c_0,...,c_{N-1}\}$ がある
• 点 $d_0$ が与えられる
• $d_{i+1}=$ 線 $a_ib_i$ と $c_id_i$ の交点 $(i=0,1,...,N-1)$
  • 線分では無く、両側に無限に続く線で考える
• 以下の場合、交点が存在しないのでそれ以上 $d_{i+1}$ を定義できない
  • $c_i=d_i$
  • $a_ib_i$ と $c_id_i$ が平行
• $d_i$ を定義できる最大の $i$ を求めよ
• $1 \le |a,b,c 各点のxy座標|, |d_0 のxy座標| \le 1000$
• $1 \le N \le 10^6$

• 誤差と戦う小手先のテク - みさわめも
• 有理数とか有限体とかのはなし - Qiita

誤差の問題と見せかけて（もちろんそれもあるが）オーバーフローの問題。

座標を求めるの自体は先頭から順番にやればよいが、$10^6$ 回も繰り返すと累積誤差は倍精度でも簡単に1の位にまで及んでくる。

よって、分子と分母を別々に持って分数として正確な演算を行うテクニックがまず考えられる。 Pythonでは、自分で実装せずともずばりfractions.Fraction型が使える。

しかし、例えば以下のような点の配置では、

A(-1000,1000)  |              B(1000,999)
               |
---------------+----------------
               |
C(-1000,-1000) |              D(1000,-1000)

交点が(約400万,-1000)となり、更に同じようにすると交点のx座標を毎回約2000倍することが可能である。オーバーフロー不可避。

ここで終了条件を考えると、2線が交点を持つかどうかはABとCDの外積が0かどうかを判定すればよい。

大小比較はできないなど制限はあるが、一致判定のみなら、MODを有理数に拡張した概念を使えるらしい。へぇ。割り算は逆数をかける。

ただ、実際の座標を縮約しているので、上手い具合にハマってしまうと誤判定が生じる。生じる条件は理解できていない。

• MODを複数使って誤判定の確率を下げる
• 実行時間を考え、間に合う限り大きなMODをとる