1年生でも(多分)解ける！ABCのD問題(ABC231編)

はじめに

おはこんばんにちは 紙幣と申します。

この記事は Kogakuin Univ Advent Calendar 2021 24日目の記事です。

adventar.org

競プロ要素が皆無だったので最終日目前にしてテコ入れのために記事を書いてます。他にもやること沢山あるんだけど。助けてくれ。

さて、実は去年のKogCoderではLT会と称して各々発表会するみたいなことをやってたんですが、そん中で私は1年生向けにABCのD問を(工学院大学情報学部の)1年生が知ってる知識だけで解説する、ということをやってました。具体的にはプログラミングの授業で扱われるC言語、その中でも序盤に習う入出力、配列、if文、for文、while文、あたりがわかってれば工夫次第で解けちゃうようなD問題をなるたけわかりやすく解説しようって感じのやつです。で、記事のネタも無いし今回はそれを記事って形にして外部公開でやっちゃおうって感じです。これを読んでる競プロを始めるのが怖い*11年生もこの機会にぜひ挑戦してみてね。

なお、上記の通りガチ初心者向けという前提で書いていくため競プロ慣れてる人だと解説が冗長に感じられるかと思います。ご了承ください。

そもそもAtCoderとかABCってなあに

ここでAtCoder自体の解説入れて1年生に優しい素振り見せようかと思ったけど書くのダルくて萎えた、一昨年のyudegakiさんのこちらの記事をご覧ください。

yudegaki.hatenablog.com

わかりやすい記事だなあ！

でABCってなあにって言いますと、AtCoder Beginner Contestの略でして、AtCoderのサイトで行われてる初心者向け競プロコンテストのことです。最初は2問解けたらいいな～くらいの気持ちで挑んでみてね。

D問題ってなあに

最近のABCでは毎回A～Hの8問用意されてます。D問はその4問目ってことですね。基本的にAが一番簡単で後ろにいくほど段々難しくなっていきます。8問中4問目なのでそれなりに歯ごたえがある難易度です。

ちなみに、これは去年やってた企画(?)が元になってるという話は先程しましたが、当時はA~Fの6問構成でした。当時のD問は現在のE問に該当するそうです。現在のD問は当時のD問よりちょい簡単めくらいだとか。それにあたって今回の記事もD問じゃなくE問に変えるべきか悩みましたが、当時の企画では基本的にD問の中でも簡単めの問題を扱ってたので、それならDのままでも変わらんかってことでD問でいかせていただきます。あとむずい問題扱うと解説長くなって書くのダルいし

D - Neighbors

さて、ようやっと本題です。問題を解いていきましょう。今回扱う問題はパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)より、D - Neighborsです。

atcoder.jp

ちなみに、当然ながら以下はこの問題の解説なのでネタバレ無しで自力で挑んでみたい方は挑戦してから以下の文を読むようにしてくださいね。

さて、問題文や制約はこの通りです。

問題文

$1$ から $N$ の番号がついた $N$ 人を横一列に並べる方法のうち、以下の形式の $M$ 個の条件全てを満たすものが存在するか判定してください。

• 条件：人 $A_i$と人 $B_i$は隣り合っている

制約

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1\leq A_i < B_i \leq N$
• $(A_i,B_i)$ は相異なる

出典: D - Neighbors

これだけだとわかりづらいですね。そういうときは入出力例を見てみましょう(引用するのダルくなってきたので自分でページ開いて見てみてください)。入出力例を見るとなんとなくわかったと思います。例1は言われた組み合わせを全て満たした上で横一列に並べられるのでYes、例2では人4が3人と隣り合うことになっていますが横1列に並ぶときには2人までしか隣り合えないのでNo、ということですね。

……ってことは同じ人が3回以上出てきたらNoにすればいいだけじゃん！簡単！！

…………ということではありません。例えば以下のようなケースもNoです。

4 3

1 2

2 3

1 3

同じ人が2回までしか出てきていませんが、1の隣に2、2の隣に3、3の隣に1、とループ状になってしまっています。これでは1列に並ばせることはできませんね(競プロあるある、テストケースに出てこない箇所のトラップに引っかかる)。

けど他にNoのケースは考えられませんね。つまり

• 3人以上の相手と隣り合う人がいる
• ループ状に並ぶ必要がある人達がいる

この2つのどちらかに当てはまればNo、どちらにも当てはまらなければYesです。ではどうすればこれを見分けられますか？というところが本題になってくるわけです。

さて、ここで見方をちょっとだけ変えてみましょう。ここまで問題文通りに「人を並べる」ことを考えてきましたが、人を点に置き換えてみます。すると以下のような図がイメージできます。

点1,2,3,4

次に隣り合うという条件を点を線でつなぐことに置き換えてみましょう。すると例1,2及び先程挙げたループ状になってしまうケースはそれぞれこのように図示できます。

入出力例1

入出力例2

ループ状になっちゃうケース

つまり「条件で提示された線を全て用いた上で全部の点を一筆書きで1回ずつ通ることはできるか」という問題にできます。並び替えという面倒な操作を無視できますね。こうして見ると数学的に解けそうな気になってきますね。Noの場合の条件はそれぞれ以下のように書き直せます。

• 3つ以上の点と結ばれた点がある
• 複数の線が組み合わさってループ状になっている

では改めてこれをプログラムで実現するにはどうすべきでしょうか。

まず、与えられた情報をどのような形で変数に保管するかについても色々なケースが考えられます。条件をそのまま記録する、つまり先程の図形における「線」の情報を保持しておくことも考えられますが、これだと例えば3つ以上の点と結ばれた点がないか確認する場合に全ての線を調査して調査したい点が出てきた回数を調べる必要があります。これでは点が増えたとき面倒そうですね。

ということでそれぞれの点に繋がってる点の情報を記録するのがよさそう……？

これでもできなくはありません。しかしこれでも面倒なことが1つあります。それはループの検証です。例えば以上の図からループが無いか確認するためには点2から点1へ辿り、点1から点4へ辿り、……と繰り返さねばなりません。この図では複数の点に渡る長い線が1本しかないのでいいですが点や線の数が増えると検証がどんどんめんどくさいことになっていきます(とはいえ頑張って実装すればいけなくはないけどね、今回の問題だとNの値も小さめだし*2 )。

と、ここであることに気が付きませんか。それぞれの点の「状態」という観点で見てみましょう。以下のA,B,Cの3種類に分類できませんか。

A.線の途中になっている点(=2つの点と結ばれている点)

これらの点はもうこれ以上他の点と繋げません。

B.まだどの点とも繋がっていない点

これらの点はA以外の相手であればどの点とでも繋がれます。

C.線の端っこになっている点(=1つの点と結ばれている点)

これらの点は当然Aの点と繋がれない他、その線の反対側に位置する点とも繋げてはいけません(例えば2は5と繋がるとループ状になってしまいNG)。

……おわかりいただけたでしょうか。「どの点と繋がっているか」の情報が必要なのはCだけです。それも途中に通った点は関係なく、もう一端の相手がわかればよいのです。その他の点に関しては自分がAかBかがわかれば十分です。つまり、必要な情報に絞ると以下のように示せます。

自分の点の分類を記録した上でCのときはペアとなる相手の情報を記録するだけです。これであれば以下のように最初全ての点をBとしてそこから線を1本ずつ増やして更新していくだけで検証できます*3。

判別方法もわかって終わりが見えてきましたね。ではこの点を繋ぐ更新の処理について考えてみましょう。例えば以下の図について、5と8を新たに結ぶ場合を考えるとこうなります。

まず5と8は当然Aになりますね。問題は2と6です。直接結んだわけではないのにデータが書き換わっています。ここをどう実装すれば……。

……とまあ大半の方は察しているかと思いますが、この2と6、それぞれ元々5と8の相手として情報が記録されていました。それを使えば簡単に実装できそうですね。しかも書き換えた後の値も6と2、つまり元々8と5に記録されていた値を書き込むだけなので尚のこと簡単に実装できそうです。

次に先程の図から更に6と7を結ぶケースを考えてみると以下のようになります。

6がAになるのは先程と同様です。問題は7です。7は状態BだったのがCになりました。これをどうやって実装しましょうか。

ここで2を見てみましょう。2の相手は7になっています。状態Bの点と繋いだときはその点自体の値に書き換えなければならないようです。条件分岐がめんどくさそう……と思った方もいるかもしれません。しかしこれが実は実装を楽にするチャンスでもあります。先ほどと同じ実装でこの処理を実現したいなと考えたとき、点7に「相手は7」という情報が入っていたら都合よく実装できそうですね。

……あれ？別にそうしても問題なくね？

でもってそう考えたらBとCの区別要らなくない？

そう、状態Cのときに相手が自分自身になることはありません。つまり状態Bのときは自分自身の値を入れておくだけでBとCの見分けがつけられる上に同一の処理で実装ができるようになります。そうすると今まで状態A,B,Cと分けてきましたがAとそれ以外の2つに分けるだけで十分になります。更に言えばAのときは存在しない点の値、例えば-1等の値を入れておけば「繋がっている相手」の情報だけでA,B,Cの状態が管理できます。つまり以下の図のようになります。

ここまで来れれば後は本当に実装するだけです。実装するとこのようになります*4。

https://atcoder.jp/contests/abc231/submissions/27963119

なおこの提出はC++で行われていますが最初のinclude周りと入出力以外はCとほとんど同じなので読めるかと思います。入出力に関してはcinをscanf、coutをprintfに置き換えて読んでみてください。

おわり

というわけでド初心者向けの解説をやってきました。このブログ内でちゃんとしたプログラミングの話するの初めてでは……？

競プロは色んな知識を要求されそうで難しそう……って敬遠していた人もいるかもしれませんが、初歩的な知識しかなくても発想次第で解ける問題もあるんだよってことがわかってもらえたかなと思います(もちろん知識が必要な場面もあるけど)。これをきっかけに競プロの面白さをわかってもらえたら幸いです。それでは。

*1:ばっかお前……俺がついてるだろ(音ゲーマーにしか伝わらないネタ)

*2:プログラミングの世界では10^5なんて小さい方です

*3:このようにデータを順に更新していく手法を動的計画法(DP)と呼びます。競プロではかなり重要な考え方です。DPについて詳しく知りたい人はこちらの記事がわかりやすくてオススメです→動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

*4:この提出プログラムはめちゃくちゃコメント書いてますが解説用に書き込んだだけなので普段はこんなにコメント書いてません。悪しからず。