hogecoder

tsutaj 競技プログラミングの記録

DDCC 2019 予選 D: チップ・ストーリー ～黄金編～

AtCoder 数学

数学的な知見がいっぱいあったので備忘録です。

問題概要

日本語なので原文を参照してください → D: チップ・ストーリー ～黄金編～ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder

解説

この問題を解くには、いくつかの数学知識が必要です。

桁和と剰余の関係

唐突ですが、桁和と剰余には以下のような関係があります。

  • 非負整数 N を m 進数で表した際の桁和が s であるとする。このとき、 N \equiv s \pmod{m-1} が成り立つ。

なぜこのようになるか見ていきましょう。以下、 N は k+1 桁であるとし、 N の i 桁目を d_i と表現することにします。

まず、条件より以下の 2 つの式が成立します。

  1. d_k m^{k} + d_{k-1} m^{k-1} + \cdots + d_0 m^{0} = N
  2. d_k + d_{k-1} + \cdots + d_0 = s

式 1 から式 2 を引いてみます。さらに、等式の両辺を整数 p で割ったあまりは当然等しいので、 (m-1) を法として考えます。すると、以下のようになります。

d_k (m^{k} - 1) + d_{k-1} (m^{k-1} - 1) + \cdots + d_0 (m^{0} - 1) \equiv N - s \pmod{m - 1}

ここで、以下の性質を用います。

  • m^{x} - 1 \equiv 0 \pmod{m-1}

つまり、 m^{x} から 1 減じたものは m-1 を法として 0 と合同であるという主張です。これは m \equiv 1 \pmod{m-1} であることから m^{x} \equiv 1^{x} \equiv 1 \pmod{m-1} が分かり、あとは移項すればさきほど示した式になります。

この性質を使うと、 0 \equiv N - s \pmod{m-1} であることが言えるので、最初に示したかった N \equiv s \pmod{m-1} が示せました！

中国剰余定理

さて、もとの問題では 「 m 進数で表現した時の桁和」が入力として与えられていたので、これを利用して「求めたい整数 n を (m-1) で割った余り」が何であるかは求めることができます。しかし、実際に知りたいのは「整数 n が何であるか」です。これはどのようにして求められるでしょうか？

実はこの問題の場合はヒントが多いので、例えば 2, 3, 5, 7, 11, 13, 17, 19 で割った余りが一致する数 x を全探索で探し、更に x + 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 k を全探索しても正解することができるようです。今回はこのような全探索の解法ではなく、色々と使える数学の道具である中国剰余定理を紹介します。

m_1, m_2, \ldots, m_k を、どの 2 つの m_i, m_j (i \neq j) を取っても互いに素であるような整数とする。このとき、任意の a_1, a_2, \ldots, a_k に対して、

  • x \equiv a_1 \pmod {m_1}
  • x \equiv a_2 \pmod {m_2}

\vdots

  • x \equiv a_k \pmod {m_k}

を満たす整数 x が、 m_1 m_2 \ldots m_k を法として一意に存在する。つまり、 0 \leq x \lt m_1 m_2 \ldots m_k の範囲に条件を満たす x が一つだけ存在する。

本記事では紹介だけにとどめます。証明については [1] [2] を参考にしてください。この定理を利用すると、進数 m が素数であるものに関して中国剰余定理を適用し、条件を満たしているかチェックすることで解くことができます。

参考になるページ

定理そのものの証明に役立つページです。中国剰余定理を証明するときにベズーの等式が必要になるので、そちらの証明は [2] を参考にしてください。

[1] 中国剰余定理の証明と例題（二元の場合） | 高校数学の美しい物語

[2] 一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語

中国剰余定理を解くアルゴリズムが紹介されているページです。

[3] 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

[4] Garner のアルゴリズムと多倍長整数演算 - kirika_compのブログ

[5] 任意modでの畳み込み演算をO(n log(n))で - math314のブログ

CODE FESTIVAL 2018 参加記

大会参加記

CODE FESTIVAL 2018 に参加しました。予選は 2 年前から参加していましたが、3 度目の正直で今回やっと初めて本戦に参加できました。感想をいろいろつづります。

予選

予選 A で解けるタイプの DP が運良く出たので、通過しました。予選 B が結果的に早解き勝負になったことを考えると、 A で通ってよかった・・・。

0 日目 (前日)

前泊をしないと当然間に合わないため、前日から移動した。交通機関の遅延などもまったくなく、特に問題なく宿までつけてよい。

同じく前泊していた ixmel さんとラーメンに行った。ラーメンは活力。

https://twitter.com/_TTJR_/status/1063384924575678465

明日は朝早いのでさっさと寝る。

1 日目

起床と朝食を AC して幸先が良い。いざ UDX へ！

恒例 (なのかな？) のオープニングムービーで自分の ID が流れて胸熱だった。本戦に来た感が出て良いですね。開会式が行われた後、早速コンテストへ。どうやらパーカーのボーダーは 1400 点 (前から 4 完以上) らしい。去年の THANKS ではあと 1 問通せず逃したけど、今年は獲得していきたい！！

コンテスト

注意: ネタバレを多く含みます

基本的に前から解いていくことに。というわけで A をやるも WA (は？) よく考えたら 2540 は偶数なんですよね、初見さん？ 直して AC (09:09)

続いて B をやる。計算自体は単純だけど誤差が明らかに怖い。試しに普通に double で計算したら WA (それはそう)。あぁこれもしかして x \times 10^{-y} (x \in \mathbb{R}, 1 \leq x \lt 10, y \in \mathbb{Z}^{+} ) の形で管理すればいいのでは？めんどいなあ、と思いつつ実装。AC (35:19) 解説でも言われてたけどこんなことしなくてももっと楽に処理できますね、反省。

C を見る。なんか面倒だけど難しくはなさそう。一次関数を殴りたいお年頃なので CHT で殴って AC (58:32)

あと 1 問でパーカーだなぁと思いつつ D を見たけど普通に難しい。真ん中を固定してやって K (←文字の種類数) 一つオーダー落ちないかなぁとかいろいろ考えたけど (しかもそれで解けるらしんだけど) わからず。これはだめ。とりあえず次を見る。

E を見る。どう考えても DP だと筋が悪いので他の解法を考える。サンプルを実験すると、なんか区間 min をしまくれば良い感じだったので遅延セグ木で殴る。AC (88:02) どう考えても遅延セグ木いらないんですよね・・・さっきから殴ってばっかじゃないか？

F を見たけどむずかしそう。順位表見てもあまり解かれてない。困ったなあ 〜しばらく虚無タイム〜

G がそこそこ解かれているので見る。サイズが小さいグループには数が大きいものを割り当てたら得だよな・・・みたいに考えてたら降順ソートからの DP が生えた。これ 3 乗っぽいけど枝狩りできるよなぁと思って書いたら通ってウケた (153:56)

余った時間でもう一度 D を考えるもやっぱりわからない、そのままコンテスト終了。

結果は 37 位 / 100 でした。レートの割には健闘したのかもしれないけど、解きたかったものが解けなかったのは悔しい。でもパーカーとれたのはかなり嬉しかった。

各種コンテンツ

AI battle が行われていた。1 週間でここまで実装できるんですね・・・。

あとはルービックキューブとかマリオカートとかあったけどあまり見ていない。コネクションビンゴを早々に 1 行埋めてあとはひたすらおしゃべりしてた。

りんごの挑戦状、初めてみたけど面白かった。栃木には栃木さんが多いらしい。

チームリレー

本戦初参加だったので当然チームリレーも初参加でした。自分は Team D でした。

前半を自分と tsukasa_diary さん・enjapma さん・omochana2 さん・xxkiritoxx さんで分担して、さらに怒髪さんが前半全体を統括、そして後半を DEGwer さん・maroon さん・satashun さん・dnk さんが見てくれた。強い人たちの考察を間近で見れて、圧倒されました。実装も早いし知識も豊富だしバグ直すのも早いし、さすがですね・・・。

https://twitter.com/_TTJR_/status/1063766025437499392

結果は優勝！なんと A5 宮崎牛をゲットしました。競プロをやっていると高級肉が食べられる、最高。

その後懇親会で楽しんで、全日程終了。あっというまでした。

終了後

https://twitter.com/_TTJR_/status/1063789421877547008

その日にあったばかりのてんぷらさんとサシ飲みをした。懇親会後だけど普通にがっつり飲み食いした。たのしかったー

まとめ

本戦はやっぱりアツかった！来年もこどふぇすで会いましょう！！！！！！

競技プログラミングで黄色になるまでにやったこと

目標とか

先月末に、めでたく AtCoder 黄色になりました。

きのう、ふと「黄色になりました記事書いてないなぁ」と思って雑に呟いたら、書いてくれという圧力声援を感じたので、記していこうかなと思います。記事の特性上自分語りしかありませんが、それでも良い方はお読みいただければと思います。

続きを読む