文字列問題の解法
トヨタ自動車プログラミングコンテスト2023Ⅳ、AtCoder Beginner Contest 311、A問題、1stABC、問題文、ABCからなる文字列Sが与えられます。
SはABCをすべて含むことが保証されます。
Sを左から1文字ずつ見ていったときに、初めて次の条件を満たした状態になるのは、左から何文字目まで見たときですか?
ABCがすべて1回以上出現している。
入力例1、Nは5、SはACABB、出力例は4。
左から4文字目までに、Aは2回、Bは1回、Cは1回出現していて条件を満たします。
3文字目以前では条件を満たさないので、答えは4です。
なので、Nイコールイントのインプット、Sイコールインプット、フォーアインレンジN、その前に変数ABCをフォルス3つでとっておきます。
この間、回し続けます。
CNTイコールゼロ。
LIFSのCNTイコールイコールAだったら、Aイコールフォルスというのを3つ作ります。
LIFSのCNTイコールイコールBだったら、Bイコールフォルス。
elseCをフォルスにします。
CNTプラスイコール1で、ラストはプリントCNTプラス1でいけるはず。
ちょっと長くなったのでコードテストで試してみます。
入力例1は4が出たらOK。
インデックス数プラス1ですね。
全部出た状態。5が出た。4だね。
CNTプラス1を消します。
そうか、最後CNTプラス1しちゃってるからここでもう自動的になってますね。ループが切れるまでに。
入力例2は3。OK。入力例3は17。17OKですね。提出していきます。
もうちょっとシンプルなコーディングがありそうですが、とりあえずこれで。
はい、閉鎖しましたのでB問題いきます。
日程調整の難しさ
B問題。バケーショントギャザー。問題文。
1からNまでの番号がついたN人の人がいます。
N人の人の今後D日間の予定が与えられます。
人Iの予定は長さDの文字列SIで表されて、SIのJ文字目がOならばJ日目は暇であること。
丸なら暇、×ならそうでないことを意味します。
D日間のうち全員が暇であるような連続する何日かを選ぶことを考えます。
選べる日数は最大で何日ですか?
ただし選べる日が存在しない場合は0日と答えてください。
TRPGの日程調整とかですね。
タクシュラが私の知り合いには多いので、なかなか揃わないことが多いです。
さあ、やっていきましょう。
NとDがあって、N分Sの文字列が与えられる。
N、Dイコール、マップ、イント、インプットドットスプリット。
さて、丸の数が多い、できるだけ多いところを選びなさいですね。
全員が暇な日を選んでください。
マックス100人のマックス日数も100日。
なので20ループで取れそうな気はしますね。
まずリストを入れましょうか。
ここからのリストを入れて、
インプット、4iインレンジN人。
一応プリントLしておいて。
二重リストというか、リストの中にも入れましたね。
○○それぞれの日程を。
4iインレンジDだね。日数の方が先ですね。
CNTイコール0。
4jインレンジN。
変数ちょっと変えようか。
4dayインレンジDにして、
4manインレンジN。
で、どうしようかな。
if Lの②のdayが×だったら、
アンサー用意しとくか。
4文の前にアンサーを定義しておいて、
もし×があったら、もうこの時点で
アンサーイコールマックスの
アンサーかCNTでとって、
ブレーク。
else…
elseいらないね。
これ4文がそのままブレークしちゃうとダメだな。
だから縦で見て、
×がある日はもうカウントしなくて、
丸だった場合をどうするかですね。
だから、
okイコールtrue。
4dayインレンジDの中に、
CNTイコール0。
okイコールtrueを入れておいて、
20ループ。
4manインレンジN。
で、if Lのこの人のこの日が×だった場合、
okイコールfalseにして、
アンサーイコールマックスの
アンスCNTにします。
で、
if okだったら、
CNTプラスイコール1なんですが、
4文の中にCNTを入れるのは間違いですね。
アンサーとCNTを4文の外に
00で定義しておいて、
で、プリントアンサーかな?
プリントマックスアンサーかCNTかな?
ちょっとわかんなくなってきたな。
入力例1は2が出ました。
ok。
入力例2は1が出たらok。
2が出たな。
2が出ちゃダメだな。
リセットしてないですね。
×が出てきたら、
CNTイコール0にします。
入力例1もう1回見ますね。
今日のやつ難しいな。
入力例3は0。
入力例4は7。
入力例5は5。
入力例多いな。助かるな。
5。
入力例は全部クリアしたので提出していきます。
有効グラフの探索
ACしましたので、C問題いきます。
C問題、Find It。
問題文。
N頂点N辺の有効グラフがあります。
グラフだ。
I番目の辺は頂点Iから頂点AIに伸びます。
I≠AIであることは制約より保証されます。
同一頂点を複数回含まない有効閉路を1つ求めてください。
なお、この問題の制約下で答えが存在することが示せます。
同一頂点を複数回含まない有効閉路。
この問題では、有効閉路とは以下の条件を全て満たす頂点の列Bであるとします。
M≥2
BIからBI≥1に辺が伸びている。
BMからBM≥1に辺が伸びている。
I≠JならばBI≥BJ。
何を言っているんだ。
入力例はMとAが与えられるので出力はMとB。
Mは出力する有効閉路の頂点数であり、BIは有効閉路のI番目の頂点である。
入力例1、7、6、7、2、1、3、4、5。出力例1、4、7、5、3、2。
7、5、3、2、7は確かに有効閉路になっています。この入力に対応するグラフは以下の通りです。
7、5、3、2。
有効閉路、同一頂点を複数まとまない。
ん?2、7、5、3、4、1、6。
Aは何をしている?
I番目の頂点Iから頂点AIに伸びます。
順番ですね。
1、インデックス0番目の数字は、
0番目が6と書いているので、1個目の頂点は6という点に続いています。
2個目は7なので、2番目は7に続いています。
3番目は2なので、3と2が繋がっています。
別の頂点数。
独立している。ぐるっとループになっている。
双方向。双方向でもOKなんだな。はいはいはい。
わー難しいなこれ。
平行、有効閉路。
平路なので、だから一方方向なのはダメなんだな。
自分はどこかに向かっているし、どこかから自分にも向かってきているやつをカウントしてくださいですね。
一回ちょっとやってみますか。
nイコールイントインプット。
で、Aイコールリストのマップのイントインプット。
ドットスプリット。
で、Lイコール空のリストを作っておいて、
4YインレンジN、
SのI番目、
Lの空のリストかける、
何かしとくか。
4YインレンジNかな。
これ二重リストって空のまま複数個作れたっけ。
作れてるね。
なので、
4YインレンジN、
LのI番目、
ドットアペンド、
SのI番目かな。
これどうなる?
6、7、2、1、3、4、5、
そのまま入るだけだね。
そのまま入るだけなので。
違うね。
LのSI番目だな。
リストインデックスアウトオブレンジ。
じゃあ、
Lの中の二重ループの数を
MAXSの数分取りましょうか。
MAXSかける2ぐらい取る?
あれ?
リストインデックスアウトオブレンジ。
なんでや。
あれ?なんでや。
6、7、
ん?
MAXS分取ったら十分だと思うんですが。
あ、MAXSかける2。
はいはいはい、大丈夫そうですね。
で、何これどうしたらいいんだ?
これあれかな。
ユニオンファインドかな。
親の数を確かめるみたいなことですかね。
ちょっと分かんないな。
解説見るか。
実は以下の手順で答えを見つけることができます。
最初に通った頂点を記録する列Sを用意する。
Sは最初は空である。
その後好きな頂点Vから始め、以下を繰り返す。
SにVが含まれない場合、
Sの末尾にVを追加。
VからAVの辺を伝ってVからAVに移動する。
SにVが含まれる場合、
SイコールX1からV、
Y1からYKであったとする。
何これ。
この時、V、Y1、Y2、YKが答えの一例となる。
ん?
問題の制約より全ての頂点についてそこから出る辺が存在するので、
この手順で必ず閉路を発見できます。
バケットソートの要領で行うことで、
オーダーNでこの問題に正解できます。
バケットソート、初めて聞きますね。
C++で実装してくれているみたいなので。
はい、やってみますか。
からのN、ん?A。
リストAに入れてますね、とりあえず。
で、んーと、フォー文かこれ。
わー、ちょっと分かんないな。
フラグ、フラグV。
プッシュバック。
いや、ちょっと分かんないな。
他の解説。
より簡単な実装。
あ、Python実装であるわ。
公式解説にあるように、頂点を一つ任意に取り、
そこから移動し続けることでサイクルに到達することができます。
ところで、あらかじめサイクル内から始めることができれば、
実装はより簡単になります。
これは最初にN回移動しておくことで必ず達成できます。
また、Aの先頭にダミーを増やして、
1マイナスインデックス度にしておくなどの工夫により、
実装はより簡潔になります。
Pythonの実装例。
短っ。
ああ、そういうやり方もできるんだ。
listMapIntで括弧で括って、
文字列S空白プラスinput.split。
ちょっとそのままコピペというか、
模写してみますか。
nイコールイントのインプット。
aイコールリストのマップの
int文字列0空白プラスインプットで
これを括弧で括る。
で、nowイコール1。
forangeN nowイコールa now。
nowイコールa now。
nowイコールaのnow番目。
あらかじめN回移動する。
bイコールリストのnow。
なんだ、何をやっているんだこれは。
while b0番目がnotイコールa now。
while b0番目がnotイコールa nowの間。
nowイコールaのnow番目。
b.append now。
printlnbのbが答えと書いてますね。
はい。実行641。
問題Cはできてるっぽいですね。
ちょっと何が起きているか確認しようか。
0インデックスじゃなくしているまずaのリストを
なのでnowイコール1。
1インデックスから始まる。
で、forange。
これ何しているの。
nowイコールa nowにしているのは何で。
6,7,2,1,3,4,5。
nowイコール5になるでしょ。
で、bイコールリストで5を入れました。
リストで5を入れました?
a now。
ん?
bイコールnow。
printb。
6が入ってるね。
一周したからってこと?
nowイコールa now。
print nowとaを確認しよう。
nowが
なんかいっぱい6があるな。
6から始まってるね。
6から始まってて
nowイコールa now。
6番目は4だから4が入る。
4から1。
1から6。
ここがループしてるんだ。
6,4,1,6,4,1ってループしてる。
で、そこにループしているものを入れました。
ん?
4,5,6。
while b0。
だから6がaのnowと違う間、
aのnowは最終的に何になる?
aのnowは
1とaのnow。
3になる。
違う、4になってる。
違う間は動き続ける。
んー。
なんとなくわかった気はするけど。
これは思いつかないな。
はい、ではまた次回。
お疲れ様です。