AtCoder Beginner Contest 284、A問題
AtCoder Beginner Contest 284、A問題、Sequence of Strings、問題文、N個の文字列Sがこの順番で与えられます。
逆順で出力してくださいですね。
S1、S2…、SNと与えられるので、SN…、SN-1…、最後はS1。
入力例がNが3、開業区切りで高橋、青木、スヌケ、出力例はスヌケ、青木、高橋ですね。
やっていきますか。
Nイコールイントのインプット、空のリストを作りましょう。
Lイコール、空リスト、フォーアインレンジ、N、L.Append、インプット、プリント、
Lイコール、Lのカッコ、ダブルコロン、ダブルコロン、マイナス1、これで逆順になるので、プリント、アスタリスク、Lでいいはず。
これ開業区切りって言ってるけど、空白区切りでも出せるのかちょっと試しにやってみましょうか。
救急車が来てる。
ACしたのでB問題いきます。
B問題、マルチテストケース図、問題文。
この問題は1つの入力ファイルに複数のテストケースが含まれる問題です。
初めに整数Tが与えられます。
T個のテストケースについて次の問題を解いてください。
N個の整数数、A1からANがあります。
このうち奇数は何個ありますか?
TとNが100までなので、これも4分でって感じかな。
整数列がT回与えられるんだ。
各テストケースは、はいはいはい。
N個の数列、AっていうのがT回分与えられるんですね。
なるほどね。
なんかちょっと変わり種ですね、B問題にしては。
なのでとりあえず一番最初はTイコールイントのインプット。
で、4Yインレンジ、T、T回やります。
Nイコールイントのインプット、
Aイコールリストのマップのイント、インプットドットスプリット。
Aが10の球状まで、数列の中の数字は10の球状まであるけど、
数列の数自体は100個だから、
マックスとっても1万回の試行回数なので、
シンプルに4AインAで奇数をとっていけばいいですかね。
リストAをとった後にCNTイコールゼロでとっておいて、
この4文が終わったらスプリントCNTでいけるはず。
2、1、5、0。OKですね。
はい、提出してみましょうか。
B問題、マルチテストケース図
はい、ACしたのでC問題いきます。
C問題、カウントコネクテッドコンポーネント、コンポーネンツ。
問題文。
頂点に1からNの番号が、辺に1からMの番号がついたN頂点M辺の単純無効グラフが与えられます。
辺Iは頂点UIと頂点VIを結んでいます。
グラフに含まれる連結成分の個数を求めてください。
グラフに含まれる連結成分の個数。
注釈。
単純無効グラフとは単純で辺に向きのないグラフのことを言います。
一方通行じゃないってことですね。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことを言います。
他の頂点、他の辺が被っていたり、自分から自分にというぐるっと回った線がない。
あるグラフの部分グラフとは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことを言います。
グラフが連結であるとは、グラフに含まれる全ての頂点同士が辺を経由して互いに行き来できることを言います。
連結成分とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものを言います。
グラフに含まれる連結成分の個数を求めてください。
入力例1は出力2。
与えられるグラフに含まれる連結成分は次の2個です。
頂点123および辺12からなる部分グラフ、頂点45および辺3からなる部分グラフ。
やり方は全然実装はできないんですが、
多分ユニオンファインドの親の数を答えろということですよね。
ユニオンファインドをググってみようかな。
パイソン、ユニオンファインド。
これをちょっとコピペして、
セームナンバー、ルート、グループカウント。
結局何を求めたらいいんだこれは。
親の数っていうのはセームか。
ファインド、セーム、ユニオン。
パイソン、ユニオンファインド。
親の数、要素数を取得する。
解体語、結合、サイズ。
親の数、どうすりゃいいんだ。
結局どういうコードを書いたらいいのかがわからずじまい。
nmイコールマップインプットドットスプリット。
n頂点m辺。
だからlイコール空のリストかけるnプラス1個あるのかな。
これはゼロインデックスか。
canonlyconk。
何これ。
list not int to list。
二重リスト空のリストを作ろうとしたんですが、
nプラス1を括弧でくくんないといけないかな。
できたね。できたけど数が出てないな。
解説見ますか。
C問題、カウントコネクテッドコンポーネント
パッと思いつかないな。
まずこの問題では単純無効グラフ連結成分のような少し聞き慣れない単語が登場しますが、
これはグラフ理論と呼ばれる分野の専門用語です。
この問題は用語の意味に注釈をつけていますが、
競技プログラミングではグラフ理論の用語が時々説明なしに登場します。
より多くの問題を解けるようになりたい人は、
少なくともGoogle等の検索エンジンを利用して用語の意味を素早く把握できる能力を身につけましょう。
さて、連結成分の個数を求める方法を考えます。
頂点Vを一つ選んだ時にVを含む連結成分に含まれる頂点の集合は、
深さ優先探索や幅優先探索のようなグラフ探索アルゴリズムを利用すれば調べることができます。
はじめ、すでに訪問したかを管理するN要素の配列Visitedをフォルスで初期化。
答えの値を管理する変数暗数を0。
iイコール1からnの順に次の操作を行う。
Visited iがtrueなら何もしない。
フォルスなら頂点iを含む連結成分をDFSやBFS等で求め、連結成分に含まれる全てに頂点Vについてtrueにする。
暗数に一応加算。
はいはいはいはい。
はいはいはいなんだけど、
BFS、DFSもちょっと実装がまだよくわかってないんだよな。
あ、また別解としてUnion Findと呼ばれるデータ構造を使う解法もあります。
やっぱりリーダー親の数を調べてますね。
この辺のアルゴリズムを落とし込みたいけど、
他の方の答えを見てるだけじゃ身につかないですね。
YouTubeで3分くらいにまとめてアットコーダーの解説というか、
答えと一緒に解き方の解法をゆっくりで解説してくださってる方がいるんで、
それもちょっと見てはいるんですが、
やっぱり自分で書いていかないと手になじまるんですかね。
ちょっと時間あるときにC問題、D問題とかも自分で模写できるようにしていこうかなとも思いつつ、
時間が取れたらって感じですかね。
ではまた次回。お疲れ様です。