0.はじめに
昼間にやっていた東京工業大学のもちらっとやってみましたが
ちょっと無理でした・・。
気を取り直してABCに挑戦しましたが
実装にてこずった感じになりました。
３問正解もレートは下がってしまいました。
1.A - Rightmost
最初一番左かと思って作り始めてから右側ということに気づきました。
A問題らしい簡単な問題でした。
https://atcoder.jp/contests/abc276/submissions/36223973
2.B - Adjacency List
難易度急上昇。
絶対TLEとはおもいつつ
最初は10000×10000の枠を作って
道路のある組には1をセットして
枠をもとにアウトプット。
としたらやっぱりTLEでした。
素直に、表L[出発都市][到着都市配列]を作り
道路情報をもとに到着都市配列に追加していき
最後に都市数と到着都市配列を順に表示。
で、できました。
今となっては最初なぜ枠を作る方式にしたのかが謎なくらい
後者の方が楽でした・・。
https://atcoder.jp/contests/abc276/submissions/36237269
3.C - Previous Permutation
最初は全く分からなかったのですが、例題２や自分でExcelに
4桁のケースを列挙して書いたりしてやっと以下にたどり着きました。
（解説等にはちゃんとした考え方や説明があるかもしれませんが見ていないので
独自の解釈となります・・・）
考え方
・辞書順昇順の順列の変遷
1)辞書順最小順列は、1～Nが昇順に並んでいる状態
最大順列はN～1と降順に並んでいる状態
例(4桁)辞書順1番目(最小)：1234
2)辞書順2番目の順列は、N番目の数字とN+1番目を
入れ替えた状態。
→下2桁で降順
例(4桁)辞書順2番目：1243
3)辞書順3番目の順列は、下3桁内でで2番目に大きい数字を
下3桁の先頭にもっていき、それ以外の数字を昇順にする
→下2桁での入れ替えが終わったので3桁目を巻き込んで入れ替えする
例(4桁)辞書順3番目：1324
4)辞書順4番目の順列は、N番目の数字とN+1番目を
入れ替えた状態。
→下2桁で降順
例(4桁)辞書順2番目：1342
と、下の桁から順序を入れ替えて下の桁の入れ替えが終わったら
１つ上の桁を巻き込んでまた順序を入れ替えていく。
これを踏まえると、与えられた順列Pの辞書順1個前の求め方
（もしかしたら条件分けしなくてもいけるかもしれませんが実装の都合上
分けました）
条件１）N番目の数字よりN+1番目数字が大きい(下2桁が降順)の場合
→N番目の数字とN+1番目数字を入れ替える(下2桁を昇順にする)
条件２）条件1以外の場合
(1)順列Pを先頭からチェックし、一番右側にある昇順の組(chg)と
その直前の数値(PREA)を探す
例題２の場合）
9 8 6 5 10 3 1 2 4 7
→chg：1 2 4 7 PREA：3
→順列9 8 6 5 10 3の先頭でこの後の順列は下4桁を入れ替えていく状態
(2)chgの中でPREAの次に小さい数字(2)で
順列PのPREAを置き換えchgの2を3に入れ替え昇順に並べて(7 4 3 1)
9 8 6 5 10 2 7 4 3 1
→(1)で順列9 8 6 5 10 3の先頭だったので、9 8 6 5 10 2の最後の
順列を求める
考え方がまとまってからの実装にてこずったけど
ACだった時の達成感は半端なかったです。
https://atcoder.jp/contests/abc276/submissions/36256844
4.D - Divide by 2 or 3
C問題解けた時点であと15分くらいしか残っていなかったので
時間内には解けませんでした。
与えられた数列の一番小さい数字に合わせていく感じかなーと
解説を見たところ、最大公約数に合わせて考えるようでした・・。
考え方
1)数列aの最小公倍数を求める
Python3.8の関数だと２個ずつしかできないのでこんな感じで。
(TLEになるかと思いましたが意外と高速で計算してくれるようでした。)
import math
N=int(input())
A=list(map(int,input().split()))
g=0
for i in range(N):
g=math.gcd(g,A[i])
2)数列aの各数値を、g(最大公約数)で割った後
２と３で割れるだけわりつつ割った回数をカウントしておく。
割ったあとの数字が最終的に1であればＯＫ
1以外＝2と3で割っていってもgにならない時には
回答を満たせないとして、”-1”を表示して終了
3)2)でカウントした割った数を表示して終了
せめて30分位ないとD問題に取り掛かる気力がわかないなと思いました。
（30分あれば解けるとは言っていない）