hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

ARC-E を全部解いたので 10 問選んでみた

この記事は Competitive Programming (1) Advent Calendar 2018 の 17 日目の記事として書かれました。本来なら日本で執筆する予定だったんですが、飛行機運が悪すぎて機内でスマホを使って記事を書いています。限界すぎる。

先日、2018 年 12 月 17 日現在で公開されている ARC-E を全て埋めたので、個人的にオススメの問題を 10 問ピックアップして紹介していきたいと思います。自分の好みが原因でジャンルが偏ってるんですが、まあお許しください・・・。

以下ネタバレを含むので、注意です

絶対に落としたくない問題

以下で紹介する問題は、たしかに難しいけれどもコンテスト中に絶対に落としたくないと感じる問題です。(主観ですが) 他でもよく出てくるような考察を必要とします。

Snuke Line (ARC068, 700 点)

この問題は、条件を少し言い換えるだけでかなり見通しが良くなります。ただし言い換えた後も工夫しないと想定解法の計算量にはたどり着かないでしょう。これは自力で思いつきたい問題です。

N! / K 番目の単語 (ARC047, 旧 ARC-C)

よくある問題設定ですね。ここで使う考察は他の問題でもよく出てくるので、是非一度トライすると良いと思います。

キャンディーと N 人の子供 (ARC059, 800 点)

おそらく 800 点の中では簡単な方だと思います。少し高速化しないと AC は取れませんが、他に比べればそれほど難しくはありません。

Meaningful Mean (ARC075, 600 点)

これもよくある設定の問題です。わかってしまえばかなり素直に解くことができますが、自力でこのアプローチを思いつくのは難しいかもしれません。上位勢を目指すなら絶対に外せない枠になるでしょう。

考察重視の問題

以下で紹介する問題はいわゆるアドホック系で、考察寄りの問題です。筆者はこういう系統が一番苦手なのですが、数をこなして考察力をつけるしかないのでしょうかね・・・?

Papple sort (ARC088, 800 点)

問題設定自体は非常にシンプルです。解法も分かればかなりシンプルなものですが、考察力がないと導くのは難しいと思います。普段から考察がちゃんとできているかで明暗が分かれそうな問題です。

Ball Coloring (ARC073, 700 点)

個人的にかなり苦労した問題です。考慮すべき状態の数がそこそこ多いので、その全てを考えきれるかが大きなポイントです。このようにいくつかの場合に切り分けるような問題は解くのに時間がかかりますが、地道にやっていくしかありませんね・・・。

GraphXY (ARC089, 900 点)

グラフの構築問題です。構築系はアドホックな考察が必要とされることが多いと感じていて、これもその一つです。まずは解説を見ずに、じっくり考えてみることをお勧めします。

高度典型を養う問題

以下で紹介する問題は、「このテクニックは自分が知る限りだとこの問題でしか練習できないし難しいけど、大事だよな〜」と思った、いわゆる高度典型の問題です。ARC-E にはたまにこういう問題も混じっているので面白いです。ただ、解くまでに無限時間かかるんですけどね・・・。

Smuggling Marbles (ARC086, 1000 点)

部分点解法は操作に関する簡単な特徴をつかむことで比較的楽に解くことができます。ただし、満点解法はそうはいきません。詳しくはご自身で解説を読んでいただきたいのですが、なんと部分点解法のアイデアを変えずに高速化することで解くことができます。ここで使うテクニックは自分の知る限りではこの問題でしか見たことがないのですが、上位勢からすると典型とのことなので、類題はいくつかあると思われます。たぶん。

NarrowRectangles (ARC070, 1000 点)

この問題は、自分が ARC-E を埋める際に最後の砦的存在になっていた問題で、解くまでに相当時間がかかりました。

問題設定は非常にシンプルで、慣れていれば部分点解法も容易に思いつきますが、満点解法は関数の性質をうまく利用しなければならず、思いついたり実装したりするのは至難の業です。いつかこのような問題を本番中に解きたいものですね。

MUL (ARC085, 700 点)

言わずと知れた有名高度典型です。この問題をきっかけに、某テクニックを知った方も多いのではないでしょうか?最近でいうと CODE THANKS FESTIVAL G 問題で、これに似た考察で解けるものが出題されました。

というわけで、ARC-E から 10 問ピックアップしてみました。当然この 10 問だけ取り組んでも不十分で、やはり全部解くと良いと思います (害悪)

ここまで読んでくださりありがとうございました。来年の今頃には ARC-F が全部埋まってればいいんですが、できているかなあ。

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

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

問題概要

日本語なので原文を参照してください → 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 さんとラーメンに行った。ラーメンは活力。

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

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 さんが見てくれた。強い人たちの考察を間近で見れて、圧倒されました。実装も早いし知識も豊富だしバグ直すのも早いし、さすがですね・・・。

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

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

終了後

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

まとめ

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