TechFULの中の人

TechFULスタッフ・エンジニアによる技術ブログ。IT関連のことやTechFULコーディングバトルの超難問の深掘り・解説などを毎週更新

参加者目線で見る 第35回TechFUL Coding Battle

はじめまして、TechFULでアルバイトをしている某競技プログラマです。(ハンドルネームは伏せさせていただきます...)

 

まず、前回のTCBの結果ですが、なんと理論上の最高得点である858点を記録した方が3人も出て、とても驚いています!(ちなみに、記事の執筆者は10問目の作問者です)

 

今回のブログでは、解説スライドでは書きにくい、「参加者目線で第35回TCBを見るとどのように見えるのか」をサクっと解説していきます。前回のTCBで難しい問題にどうアプローチすればいいか分からなかったという方や、全問正解まであと一歩というところまで迫ったが解ききれなかったという方を読者の対象としています。

各問題についての詳しい解法は、解説スライドを参考にしてください。

 

1問目:折れ線グラフ

判定自体は $(y_2-y_1)=(y_3-y_2)$ かどうか判定するだけなので簡単だが、 Yes/No がどちらが何を意味するのか取り違えないように注意する。

2問目:今、何問目?

実は入力の数さえ分かってしまえば、その後の入力は最終的な出力に影響しない。プログラミングコンテストにおいて、実は受け取っても使わなくてよい入力が含まれる、というケースは一定数存在する。

 3問目:グラフィック

ぱっと見て一般の場合で解くのは難しそうなので、制約に目を向ける。すると、制約が $1000$ 以下という項目が多く見受けられるので、全探索が適用できないかという考えに移る。全探索を実装すると、正解することができる。

4問目:くじ引き屋

この問題の数列 $a$ も、(2問目同様)実は答えに影響しない入力である。受け取った入力を使わないのは少々勇気が必要だが、自分の解法に自信をもって突き進もう。

5問目:環を探せ!

プログラミングコンテストにおいて木の性質に関する問題はかなりいろいろ存在するが、その中でも有名なテーマのひとつが「木に $1$ 本辺を追加すると、ちょうど $1$ つサイクルができる」というもの。さらに、「木に $1$ 本辺を追加したグラフは、サイクルに木が繋がった形をしている」という事実も有名である。よって、グラフから次数 $1$ の頂点をどんどん消していけば最後にサイクルだけが残る、という算段が正しいことがわかる。詳しくは解説参照。

ちなみに、木が与えられて、そこに $1$ 本辺を追加するのでその時にできるサイクルの長さはいくらか? という問題を $Q=2 \times 10^5$ 回程度解く...という問題も解くことができ、こちらもかなり有名問題である。(最小共通祖先問題の話題になる)

6問目:Techダンジョン

この問題では、 $H \times W$ は最大で $10^{10}$ となってしまうが、 $N$ は最大でも $2000$ となることに注意する。

また、 $H \times W$ のグリッドの左上のマス $(1,1)$ から右下のマス $(H,W)$ まで、辺で接するマスを伝って移動するときに、次が成立する。

すべての $2 \le i \le H+W$ を満たす整数 $i$ について、 $x+y=i$ であるマス $(x,y)$ のうち、ちょうど $1$ つを通って移動することになる。

 これによって、各財宝を $U_i+V_i$ の昇順にソートしておけば、移動可能な全ての経路は前から後ろ方向に向くので、実装が簡単になる。

もし $H \times W$ の最大値が小さければ、 $dp[i][j]=($マス $(i,j)$ まで到達した時点での解 $)$ という動的計画法の方が実装が簡単になる。特に、 $N$ が大きいと今回の問題の解法ではたいていの場合実行時間制限に間に合わない。

7問目:Time Traveler

もし、時代が $1$ つであれば、最短経路問題そのものである。なので、時代が $2$ つになっても同じ解法を適用できないか...?と考える。すると、「タイムトラベルを使う前の、 $2021$ 年の都市 $i$」「 $21XX$ 年の都市 $i$」「タイムトラベルを使った後の、 $2021$ 年の都市 $i$」 という $3N$ 個の頂点で最短経路問題を行えばうまくいくことが分かる。しかし、この問題は過去に類題を解いたことがないと、自力で思いつくのは少し難しいかもしれない。

8問目:FULくんの迷路

これは「最小カット問題」を知っていないと自力で正解するのは困難を極めると思われる。ただ、もし知っていてもどう使えばいいか分からない...ということにはよく陥りがちである。今回の場合、単純に考えるとグラフの頂点にあたる「各マス」をふさぐ、という操作が行われるので、「辺」の話である最小カット問題にどうにか持っていかなければならない。そこで、同じマスにあたる頂点を $2$ つ用意して、片方は入口、片方は出口のように取り扱うことにする。すると、「あるマスをコスト $1$ で塞ぐ」ということは「入口を表す頂点から出口を表す頂点に張ったコスト $1$ の辺を切断する」と言い換えられる。

「頂点を $2$ 倍にして入口/出口のように扱う」というのは頻出テクニックである。

7問目と8問目では、「位置が同じであるが意味が異なるという状況を、グラフ上の別の頂点で表して問題を解く」という根本的な発想が同じなので、上級者が見ると「同じ問題に見える」という感想も聞かれるかもしれない。

9問目:有向全域木

「有向グラフ上で、たどりつけるかどうか」というフレーズに出会ったら、(知っていれば)真っ先に強連結成分分解が思い浮かぶと思う。すると、全ての頂点に辿りつくためにはトポロジカル順で一番最初に来る強連結成分にしかその資格がない、ということは簡単に分かる。なので、あとはシミュレーションで判定してもよく、他に「強連結成分のうち、その成分に入る有向辺が無いもの」があるかどうかで判定してもよい。

ちなみに、無向グラフ版の解法に、「二重辺連結成分分解」があるので、知っておいて損はないだろう。

10問目:庭師Techちゃん

ここまでの問題と打って変わって、ぱっと見ではアルゴリズムは分かりづらい。ひとまず、できる木に含まれる各素因数の個数の偶奇だけが重要なので、それをうまく取り扱うことを考える。すると、適当に根をとった時の部分木 $(N-1)$ 通りについて、上側と下側を考えれば $2(N-1)$ 通りを調べ尽くせる、ということが分かる。そこで用いるのが木dpだ。木dpは部分木関連の操作に強い。

あとは操作を高速化していくが、ここで「$N \times$ (素因数の種類数) が $10^9$ 程度かつ、着目するものが偶奇なのでbit演算で高速化できないか?」と考えを進めると解説スライドのbitsetの方針に、「全体で処理しなければならない素因数の個数の合計は $10^6$ 個以下では?」と考えを進めると解説スライドのマージテクの方針に進むことになる。TechFULでは、各問題の実行時間制限が $5$ 秒あるので、少し定数倍が重い実装になってしまってもある程度正解できるので、自信をもって実装を進めたいところ。

 

と、こんな感じでしょうか。もし自分が参加者だったらだいたいこんなことを頭に思い浮かべながらコードを書いていきます。よく「どうやって問題を解き進めてるのか分からない」と聞かれるのですが、その答えを少しでもこの記事から読み取っていただけると嬉しいです。

 

ちなみに、第36回のTCBが2021年5月19日(水)から23日(日)にかけて開催されます。

是非、ご参加ください!

techful-programming.com