ACL Beginner Contestを始める
ACL Beginner Contest、A問題、リピートACL問題文、整数Kが与えられます。
文字列ACLをK回繰り返して繋げることで得られる文字列を出力してください。
例えば、Kイコール3ならば、ACL、ACL、ACLを出力してください。
そのままですかね。
Kイコールイントのインプット、プリント文字列ACLかけるKでどうでしょうか。
ACしたのでB問題に行きます。
B問題、インテジャープレファレンス問題文。
すぬけくんはA以上B以下の整数が好きです。
高橋くんはC以上D以下の整数が好きです。
どちらもが好きな整数は存在しますか。
10の18乗。
イエス。あとはノート出力せよ。
A以上B以下、C以上D以下の整数が好きです。
だから、ABCDをとりあえずもらいます。
ABCD、Macのイントのインプット、ドットスプリット。
A、Bの制約とC、Dの制約がそれぞれ別なので、
If、だからBがCより小さいか、
AがDより大きいかだともうアウトなのでプリントNO。
そうじゃなかったら入ってるからプリントイエスでいいんじゃない?
だめ?簡単すぎる?理屈。
ちょっとテストケース見てみましょうか。
入力例1はイエスが出たらOK。
イエス。
入力例2はNOが出たらOK。
NO。ということで一回提出してみましょうか。
もしかしたらORじゃなくてANDでif文組んだ方がいいかもしれないけど。
あーACしましたね。OK。
じゃあC問題いきましょう。
都市と道路の連結
C問題コネクトシティーズ。問題文N個の都市1番からN番までとM個の双方向道路1番からM番までがあります。
都市Iは都市AIと都市BIを結びます。
その結果は以下の操作を0回以上行うことができます。
道路で直接結ばれていない2つの異なる都市を選び間に道路を作る。
操作を終えた後、どの都市からどの都市へも、場合によっては複数回道路を辿ることで到達できるようになっていなければいけません。
全部繋がってないといけない。
目的を達成するため、最低何個の道路を作ればよいですか。
制約10万なんだ。10万なら法文というか、あれなんだっけ。
深さ優先探索とか長さ優先探索とかいうやつ。
FPSじゃなくて。
それを使いそうな感じの問題文ですね。
NMであとはAB。
さっきのB問題を流用しましょう。
NMイコールマップのIntのインプットスプリット。
都市Aのリストと都市Bからのリストを作っておきます。
ここはインレンジ。
NとMは何?N個の都市とM個の双方向道路。
だから入力例1はNが3、Mが1。
与えられるABは1個だけ。
だから法文はレンジMですね。
5文字のABイコールマップのIntインプットドットスプリット。
道路Iは都市AIと、
この入力例だと1個目の道路が都市Aの1と都市Bの2を繋いでいる。
中古と和だ。
空の文字列の中にもう1個空を作らないといけないね。
空のリストをインレンジ。
N個の都市があると。
Bも同じくインレンジ。
N個の都市。
これでいけてる?
ちょっと確認。
いけてますね。3つからのリストが20リストになってます。
これがどうなってんだ?
最初に都市が3つあり、都市1と都市2の間に道があります。
すのけくんは例えば都市1と都市3の間に道を作ることによって目的を達成できます。
道を作った後、1と2の間、1と3の間、2と3の間を両方の道を通ることで旅行できます。
どっかしらが繋がっていればOK。
だから…
むずい。
大文字Aの小文字A-1。
大文字Bの小文字B-1。
これはどうなってんだ?
都市が3つあり、都市1と都市2の間に道があります。
都市1と都市2の間。
都市1と都市2。
だから…
AとBをそもそもマイナス1にしておくか。
A-1。
B-1。
リストAのA番目にAppendB。
リストBのB番目にAppendA。
下から何?っていう感じだけど。
プリントABで確認。
入った。入ったが…
えー、こっからだな。
いやー、ちょっとわかんないな。
解説見るか。
公式解説。
このようにACLを用いると非常に簡単に実装することができます。
ACLって何?
C++なので公式解説は一旦置いておいて、ユーザー解説。
この問題設定をパッと見てUnion Findが真っ先に思い浮かんだので途中考察がしにくいのだが、
都市と道路を長辺と向こう辺と捉えると向こうグラフとして考えられる。
条件のどの都市からどの都市へも到達可能が連結であるということに言い換えられる。
みたいなところから思い浮かんでほしい。
すでに存在する向こう辺で連結部分に分けたとする。
連結成分に分けたとする。
全体を連結にするにはその連結成分を繋いでやる必要があるが、
ある2つの連結成分を繋ぐのに必要な辺は1つで十分。
よって連結成分数がgrp個であれば。
grp。
それを1つにするにはgrp-1個の辺を追加すればいい。
向こうグラフから連結成分数を抜き取るにはユニオンファインドを使うといい。
アトコーダライブラリーではDSUとして実装されているのでそれを使うとスムーズ。
なんかわからないことを調べようとしたらわからない言葉で構成されてるみたいな感じでした。
もう1個解説あったのでそっち読んで今日終わりにしようと思います。
問題は以下のように言い換えることができます。
n頂点m辺の向こうグラフGがあり、
i番目の辺はai番目の頂点とbi番目の頂点を結んでいます。
Gを連結にするために最低でも何本の辺を追加する必要があるでしょうか。
この問題を解くにあたり連結成分の数に着目します。
例えば連結成分が1個の場合すでに条件は満たされているため答えは0です。
また連結成分が2個の場合、2つの連結成分から1つずつ選んだ頂点の間に辺を追加することで条件が満たされるので答えは1です。
このように考えると異なる2つの連結成分から1つずつ頂点を選び、
その2頂点を結ぶ辺を追加することで連結成分の数が1減ることがわかります。
よって答えはGの連結成分の数-1となります。
頂点-1ってことかな。
ユニオンファインドを使う場合、ユニオンファインドとは各グループをそれぞれ1つの木として見なし、
2頂点が同グループかを2頂点が属する木の根にあたる頂点が同じかで判定するデータ構造です。
C++の場合、addCoderAllもしくはaddCoderDSUをインクルードすることで使えるACLのDSUを用いると容易に実装できます。
ファルシのルシがコクーンでパージーみたいになってる。
ユニオンファインドそのものの説明としては以下のページにあるスライドが参考になります。
ということで別記事があるので、もし気になる方いらっしゃったら見てください。
こっちですね、最初に言ってたやつ。
深さ優先探索や幅優先探索を使う場合、DFSやBFSと呼ばれる手法です。
BFSは頂点iから可能な限り進み、進めなくなったら1つ前の頂点に戻り進めるか判断するという頂点を調べるアルゴリズムです。
実装は最期関数を用意すると良いでしょう。
BFSは頂点iから1つの辺で行ける頂点を列挙、2つの辺で行ける頂点を列挙という風に頂点を調べるアルゴリズムです。
実装はqなどを用意すると良いでしょう。
9で合ってるのかな、これ読み方。
くえくえ、くえうえ。
どちらの場合でも最初の処理を呼び出した回数が連結成分の数に当たります。
ということでちょっと、実装例がC++で書かれているので、
一応Pythonの方の提出結果、他のユーザーさんの提出も見つつ、
落とし込めそうなら自分の中に落とし込もうかなと、
ちょっと収録外で勉強しておこうかと思います。
ではまた次回。お疲れ様でした。