AtCoder Beginner Contest 207 反省
バカみたいな難易度配置のコンテストだったので一応温まったっぽい。
今日はちょっと頭ぽわぽわ気味だった。実装・立ち回りは今月中では一番悪いかもしれない。
結果を鑑みて
1100 58:15
295位となった。Cで手こずり、Dを捨てたり捨てきれなかったりして時間を浪費、脳死添字バグでEを解くのに時間をかけ、実装力のなさでFを落とした。奇跡的に冷えずに済んだ感じ。先週よりは忙しくないはずだが、実装・ムーブのミスが多く、危うく冷えるところだった。
A - Repression
ソートした。
B - Hydrate
可能かどうかを場合分け→二分探索?と踏んだ。
可能かどうかの条件が面倒そう、漏れが出そうに見えて犯罪二分探索するかちゃんと条件考えるか逡巡した。この時間がまず無駄だった。
結局、犯罪二分探索をした。上界を10^100で始めて、結果が10^100なら-1、それ以外になるなら二分探索の結果を出力することとした。どうせ答えは大きくともlonglongに収まるだろうと思うので、これで十分である。操作回数の自明な上界を見積もろうともしたが、これもなんだか面倒に感じてやめた。
今回は変数が4つあったので直観が働きにくかったのかもしれない。
少し時間かかって次の問題へ進んだ。
C - Many Segments
全部閉区間にしちゃおう!と思って、開区間なら内側へ1だけ縮めるのをして、サンプル1が合わなくて10分首をかしげていた。
よくサンプルの説明を読むと、これでは不十分なことに気付いて全体10倍して同様の処理を行なって通した。
この時点で600位くらいだった気がする。かなしい。
D - Congruence Points
問題読む前に順位表からヤバそうな雰囲気を察して、Eを先に読んだ。
この問題に似ていることを思い出し、平行移動不変量である重心座標系を使おうと思った。そこから何故か線形計算量で解けないかとか考えたり誤差を気にしたりして全然実装しなかった。
N≦100なのだし、「円上 格子点」でググったりもして解けそうなオーラもあったが、Fも解けそうな見た目をしていたためFに挑戦して夢破れてしまった。
E - Mod i
まあ二乗のdpが許されているのでそれをするのだが、遷移先の前計算がないと余計なlogが乗ったりしてまずpython系では通らない。
遷移の前計算はmod i 固定で累積和の剰余が同じ数になるものをまとめることによってできる。ここでsetやsortを使う必要はなく、基数ソートで足りる。もっと言えば、実際にソートする必要はなくて剰余ごとに1つのindexを格納するテーブルさえ持てば実装可能で、これは定数倍も小さい。
ここまで進んだはいいが、そのあとのdpで添字ミス(最後に空部分列を追加することを容認してしまっていた。)に気付かずに首傾げてえらい時間経ってしまった。
通した後順位を見てみると200位くらいで、DもFもパッと見取れそうな見た目していたので両方考えつつF重視で行こうとした。
F - Tree Patrolling
次数だけみればいいのかと思ったが、包除原理の計算量がでかすぎるので不適。であれば素直に木dpで、制約などからどうせ二乗の木dpだろと思って、三本の二次元dpテーブルをはやせばいいというところまではすぐに辿り着いた。
しかし、遷移が頭の中でぐちゃぐちゃになって結局解けなかった。
総括
復習は今度やることにしたい。今週もなんだかんだコンテスト練習をしていなかったのがムーブに現れてしまった。どこか自分のレートに対して他人事でふわふわした感情のまま取り組んでいたり、Cで手こずった後に明確に焦りを感じたのにも関わらずリフレッシュに時間を使わなかったのもよくなかった。
コンテスト練習をしないとムーブとリカバリーの勘が鈍るっぽい。典型90のおかげか、解法の勘はよかった。いつでも落ち着いて挑めるようになりたいね。
AtCoder Beginner Contest 206 反省
4連続で温まっていたが今回は冷えた。単独writer回なので仕方ない(?)
典型90を今週は30問近く解いてコンテスト練習をしなかったのだが、実装のミスは少なかったが直観が鈍っていたような感じだった
結果を鑑みて
1500(1) 64:47
405位となった。Dで手こずり、Eで手こずり、Fは解けなかった。
来週月曜まではやや忙しいことがあってまたスランプの入り口に立っているのではないかと危惧している
A - Maxi-Buying
100倍しておけばmath.floor()を使わないでも解ける。
解けるがこわいのでちゃんと境界値は試した。
B - Savings
パッと見て思いついたのが二分探索だったので二分探索した。
コードを書いている途中で全探索が可能なことに気付いた。大してかかる時間は変わらないのでOK
C - Swappable
同じ数をまとめておく余事象的数え上げで良い。
解いて出したあたりで順位表を見た。100位を切っており、良いスピードだった。ここまでは......
D - KAIBUNsyo
貪慾法かなと思っていた。dpするには制約がきつすぎる。
端から順に見ていって数字を入れ替えるなら常に2択だし、選び方によっては手数がかかりすぎたりする。寄与を考えるとか後から保証するやつは難しそう。
困りまくって端から貪欲書こうとして、数字の書き換えの管理をUnionFindでやるとうまくいくことに気付き、UnionFind使うんだったらひょっとしたら連結成分分解がキーで、貪欲は関係なくUnionFindだけで解けるのではないかと直感した。
結局、何も証明していないがUFを投げたら通った。メタ読みに救われた。
ここで時間をかけまくって700位くらいになった たまげた......
E - Divide Both
題意を理解しようとしてみると、互いに素でないx, yのペア(x, y)であってどちらももう一方の約数ではないものを数え上げよという問題であることがわかる。ここまではすぐわかったが、そこから難航した。
余事象を用いて問題を切り分けると、計算量は以下のようになることが予想できた。
全体ペア集合のサイズ計算 O(1)
一方がもう一方の約数であるような(x, y)の個数 O*1
互いに素なペアの個数 O(?)
互いに素なペアの個数を求められればよくて、これはいかにも典型問題っぽいので number of coprime pairs みたいな文言でぐぐるとhttps://codeforces.com/blog/entry/65229…がみつかった。
メビウス関数で区間coprime pairsを計算するのは初めてだったのでバグらせたが、なんとか通すことができた。
この時点で350位くらいだった。
F - Interval Game 2
制約はヒントだったのだが、制約から連想したのは掃き出し法だった。そこから、区間というアイデアを捨ててグラフにする方向で進んだ結果、解くことはできなかった。grundy数を絡めれば Green Hackenbush に似た感じになることに気付いてどうにかならんかと考えていた(木ではないのでより難しいバージョンになる)
ワーシャルフロイド嘘解法を書いて出したが、当然WA
そのままコンテストは終わった。
総括
検索ムーブは結構よくなってきている。しかし今回は直観がうまく働かなかった。素因数・約数系の包除が苦手気味なのが今回のコンテストに響いた部分もあった。
典型90やるのもいいがコンディションの確認・向上のためにもコンテスト練習はしたほうがよさそう。
*1:R-L)log(R-L
AtCoder Beginner Contest 205 反省
今回はコンテスト前まで体調が終わっていて、ウォームアップの問題を解いていなかった。前回の分は書いていないが、黄パフォだった。内容について軽く触れると、ABCDFの5完で、順位表から得た情報でDとFを通して何とか冷えずに済んだ感じだった。ほぼまぐれ。
結果を鑑みて
1600(1) 85:54
239位となった。EとFは何となく解けるオーラがあったので両方同時に考えていた結果、Fだけ通してしかも時間がかかったという結果になった。とはいえ立ち回りはマシになってきていると思う。
A - kcal
writerにサーバルがいるので誤差問題かと勘繰ってしまった。関係なかった。
B - Permutation Check
len(set(a))を見るだけで良いことがすぐにわかるが、2重ループを許す制約なので少し不安になった。通りはした。
この時点で順位表を見た。100~200位くらいだったと思う。
C - POW
どちらもC乗なのでAとBだけ見ればいいだろと思ったが、よく見るとA, Bが負の数も許容されている。Cが奇数かどうかで場合分けをした。一応、A=0のときとかがコーナーになっていないだろうかとチェックしていた。まあ指数関数なので問題ない。
この時点でも100~200位くらいだったと思う。いいペースで解けていた。
D - Kth Excluded
答えの二分探索を考えてあげると、その値が何番目になるのかはさらに二分探索でわかる。最近解いたARCの問題で、ある数についてのある計算値から数が昇順何番目になるかが推測できるという問題があった。これを思い出したおかげで解法がわかった。
出してからジャッジの進みがやけに遅いことに気付いたが、TL3secだったので通った。このとき、実行時間制限が3secだったことを把握していなかった。今回は通ったが、場合によっては定数倍高速化が必要になった可能性もあるので気をつけよう。
この時点で50位くらいだった。安心して次に進めた。
E - White and Black Balls
インラインDPっぽいなあと思いつつも遷移がよくわからず、よく考えないままFを見に行ったらめちゃくちゃ二部マッチングっぽいので投げてみたが何だか通らず、EとFは同時進行で考えていた。
残り30分くらいになってやっとカタラン数との明確な関係性に気付けたが、対称位置のアイデアを思いつかず、解けなかった。単純な幾何で対称位置をとるのはよくやる操作だが数え上げでやることになるとは......
F - Grid and Tokens
見てすぐ最大二部マッチングだと思ってmaxflowを投げたが通らず、残り20分までうんうん唸りながらEとFを同時進行していた。
通らなかった理由は行へのコマの割り当てと列へのコマの割り当てを別々にやっていたから。この場合、行への割り当てで用いなかったはずのコマを列に割り当てたりすることができてしまう。解決案としてこの2回のフローを重ねていっぺんにやる構造を考えていた。最終的に残り20分くらいで行とコマと列のサンドイッチみたいにすればいいことに気付けた。サンプルのおかげでコマの頂点は倍にしなければならないことにも気付けた。(このくらいは自分で気付こう!)
総括
Dまで解いてE捨ててFに行ったムーブは悪くなかったが、通らなかった時にどちらも捨てきれずにどっちつかずな進行をしたのはよくなかった。今回はEもFも解けそうな問題に見えたことがこのどっちつかずムーブの原因でもあるが、効率の良くないムーブなので考えものである。精神が安定しているときはこのムーブを取っても良いが、今回の後半のようにやや焦りを感じながら2つ以上の問題を考えるのは若干無駄なので自分の状態に応じてさっさと切るかどうするか決めたほうが良いのかもしれない。
AtCoder Beginner Contest 203 反省
今のところそこまで調子は悪くない。忙しくなる前に黄色に戻れるといいが。今回は開始1時間前から緑水青の3問を解いていた。開始5分程度での体感時間は実際の2倍程度だった。良い時は5倍くらいになることはあるが、比較的良い集中ができていたと思う。
結果を鑑みて
2100(1) 84:46
93位となった。遅めの全完という感じだが、パフォーマンス2400だった。全体的に考察よりも実装が足を引っ張った印象だった。
A - Chinchirorin
if文で列挙した。xorでできると言われてびっくりした。確かにそうだ。
B - AtCoder Condominium
全列挙して実際にintとみなして総和を取る方法と数学をする方法がある。いつもであれば全列挙を選ぶが、今回は数学する方を真っ先に選んだためO(1)で解くことになった。この問題にはコーナーケースらしいものは感じられなかったので、サンプルを合わせるとすぐに提出することができた。
C - Friends and Travel costs
流し読みすると最短経路問題かなあという気分になるが、よくみるとシミュレーションするだけっぽいので普通に組んで提出。実装の問題だが、わずかにミスしやすいポイントを作ってしまった。提出前に気付いたので良かったが、できるだけ場合分けの多い実装は避けるよう日頃から心がけるべきだろう。
この辺りで順位表を見ると、200位未満であった。悪くないスピードなので焦らず進むことができた。
D - Pond
難儀した。3分くらい考え、トイレに行ったら解法がわかった。解法を二分探索と決め打たないとなかなか気付けない問題だった。Median of Medians を解いていれば典型と言えるかもしれないが、その上で二次元累積和を要求するのは400点にしては難しすぎではないかと思う。
判定関数で「何を判定させれば良いか」正確には不等号の向きなどで詰まって時間を使った。サンプルがいくらやっても合わず、焦って順位表を確認したりもした。この行動は結果的には良かった(みんなも事故っていたので安心できた)が、基本的には焦燥を加速させるだけなので好ましくない。
実のところサンプルの合わない本当の原因は二次元累積和の添字ミスだった。累積和配列になぜか単調性がないことに気付いて直すことができたが、この問題には30分近く費やしてしまった。
二次元累積和はスニペットにして良いかもしれない。
E - White Pawn
ソートしてごちゃごちゃやるとかデータ構造とか色々解法のとっかかりはあったが、最初にインラインdpの方針を取ることにした。これはおそらく、問題を見てすぐにたどり着ける点は多くてM+1程度しかないということに気付けたため。
Counterでdpを書き、dpの更新はキューにためておいて一括更新する形をとった。詰まったのは、Xが縦、Yが横だったこと。チェスのマスの読み方は(縦, 横)なのかもしれないが、それなら(Y, X)にしてほしい。これのせいで2~5分は溶けている。条件はよく確認しよう。
そんなこんなで20分ほどかけてAC。順位は100位ちょっとだったので余裕を持って先に進むことができた。
F - Weed
まず、解けそうなオーラを感じ取った。時々、コンテスト中に問題文から解けそうな雰囲気を感じとることがある。そういう時、大概解ける。とはいえ今回解けたのはたまたま気付きが連鎖しただけだったが。
まず、ソートして高い草から除いておくべきではないかという気になった。よく考えると低い草を除くのも寄与が大きい場合がありそうだった。状況に応じて真ん中も...... と考えると、貪欲の線は薄い。
二分探索で高橋くんの操作回数をまず決定することを考えた。「後から保障する」アイデアでうまくいく気がした。判定関数を考えていると、二分探索する必要性がわからなくなった。
次にdpを考えた。一次元で済まそうとしたが無理だったのでN*Kのdpを書いていた時、そういえば高橋くんの操作回数は少なく済みそうだということに気付いた。思い出しただけかもしれないが。そこで思い切って 持つ状態と、求めたい値の立場を逆転 させて解くことができた。
dpの遷移を決める際の二分探索パートで上界の設定をミスってて1ペナした。すぐ気付いて再提出した。大して順位は変わっていない。
総括
冷静に問題を解くことができていたと思う。ただ、今回は偶然に愛された部分が多く、立ち回り、実装上の注意など課題が残る。
とりあえずまあ1900には戻れたようでよかった。
エイシングプログラミングコンテスト2021(AtCoder Beginner Contest 202) 反省
久しぶりにまた書いている。ゴールデンウィークから先週末くらいまでひどいスランプに陥っていて半月で150近くレートを溶かしてしまった。
結果を鑑みて
1500 43:21
Eで時間をかけすぎてしまったようだ。とはいえ2100ほどのパフォーマンスなのでレートは上がる。スランプは脱せていると良いが。
A - Three Dice
21から引けば良い。やるだけ。
B - 180°
反転するとどう見えるのか書いてあるので、その通りにやる。うっかり変換のし忘れがないかちょっとヒヤヒヤしていた。
C - Made Up
読んでもよくわからない感じだったが、C_jに注目してみるとテーブルにまとめてしまえばいいような気がした。この解法で正解なのだが、いかんせん問題文がよくわからなくて雰囲気で実装した。サンプルは合っていたので出した。
ここで順位表を見る。300位くらいなのでそこまで早いわけではなかったが置いてけぼりにされているわけでもないので特に心持ちの変化はなかった。ただ、自分としては結構すいすいといたつもりではあった。
D - aab aba baa
まず階乗進数に思いを馳せたが、文字は2種類なのでもう少し簡単だろうと思った。
AもBも小さいので全列挙できるかな?と思ったけど60C30を考えて真顔に。
組み合わせが計算できるなら、その値を参考に貪欲に構築できるなと思った。試しに60!までテーブルに保持したが時間はかからなかったのでこの方針で解き始めた。辞書順K番目の文字列を出力する問題でバグらせなかったことはないので、落ちたらやだなあと思いながら出したら通ってびっくりした。
E - Count Descendants
最初すぐには解法が浮かばなかった。木DPで集計してクエリに答えるタイプだろうと推測した。集計できる感じではないので、ダブリングでも使うのかなと思って考えていたがこれもよくわからなかった。
部分木クエリに読み替えて深さの小さい頂点から木に出現させていく(?)手法を取ればクエリソートしてオイラーツアーを区間木に載せることでとりあえず解けそうなことには気付いた。実装が重いので想定解ではないだろうと思ってこの実装に踏み切るのに逡巡したが、仕方ないのでこの方針をとった。
40分あたりでACしたが、この時点で2150くらいの推定パフォーマンスだったので方針を間違えて時間をかけすぎてしまったのだと解釈した。実は今回の実装は想定解通りで、単に自分が悩みすぎていただけだったのだ......
F - Integer Convex Hull
普通に諦めていたが、一応解こうとしてみた。
3点選んでその内部に入る点を見つけるのはO(N^4)で可能。三角形の面積の関係を使った。
辺を共有する三角形同士を連結することで凸包を作る方針で行った。辺を共有する三角形同士を無向グラフ上で連結させると、グラフは木になるように思えた。
そういうわけで木DPしていたが、値の伝播が難しく、「無理だなあ」と思っていたらコンテストが終わった。
総括
Dくらいまでいいペースで解けていた。ライブラリをちゃんと整備して木→オイラーツアー列をパッとできるようにしておけばもう少し速く自信を持ってEを解けたのではないかと思う。全体的にあまり焦りは感じなかった。
スランプは概ね抜けたのではと思ってはいるが懸念もある。Eを解いている時に頭にもやがかかるような感覚に陥った。今回は大して支障はなかったが、俯瞰することを見失って大冷えするときは大抵こういう感覚を味わうので(ここ2〜3週間はずっとこうだった)まだ油断はできない。
ZONe プログラミングコンテスト ネタバレ 答え
これの答えを書いていきます!よろしくおねがいします!
1問目
rot13をやれと書いてありますね!
"ZONe"という文字列の個数を数えればいいので、pythonであればcount関数が使えそうです!
print(input().count("ZONe"))
というコードで正解できます!
2問目
算数をやれと書いてありますね!
UFOに電波が届かないとき、電波が一個の障害物に当たっていることになります。逆も成り立ちますね!
距離d、高さhの障害物に電波が当たらないようにするためには、少なくとも
H-D(H-h)/(D-d)
以上の高さから電波を発する必要がありますね!
N,D,H=map(int,input().split());res=0
for _ in range(N):d,h=map(int,input().split());res=max(res,H-D*(H-h)/(D-d))
print(res)
というコードで正解できます!
3問目
やれと書いてありますね!
「答えをxにできるか?」という判定問題を考えるのが定石ですね!
2人を既に選んだ時点で、(パワー, スピード, 根性)など、特定の複数のパラメータがチームに足りないとき、足りない部分のパラメータの最小値が最大の人を選ぶのが最適ですね!
ところで、3人目に限らず、ある特定のいくつかのパラメータに絞ってみた時に最適な人をチームに入れるのが正しそうですよね!
そこで、5つのパラメータの任意の組み合わせ31通りについて、各パターンでパラメータの最小値が最大の人を先に選んでおくと、チームはこの31人から3人を選ぶのが良さそうですね!
from itertools import combinations as np
N=int(input())
a=[tuple(map(int,input().split())) for _ in range(N)]
aa=[]
res=0
def plt(x,pd):
res=10**9
for i in range(5):
if i in pd:res=min(res,x[i])
return res
for c in range(1,6):
for pd in np([i for i in range(5)], c):aa.append(max(a,key=lambda x:plt(x,pd)))
for pd in np(aa,3):res=max(res,min([max(pd[0][i],pd[1][i],pd[2][i]) for i in range(5)]))
print(res)
このコードで正解できます!
さいごに
全部解くことができました!いかがでしたか?
ZONeの進化には今後も目が離せませんね!
ZONeエナジー プログラミングコンテスト “HELLO SPACE” 反省
久しぶりにまた情けない冷え方をした。ZONe飲んでからコンテスト出たんだしちょっとくらい色つけてくれてもいいんじゃないの〜?
結果を鑑みて
1000 35:52
853位となった。ABC級で水パフォを出したのはかなり久しぶり。学業やバイトを気にしなくてはいけなくなる時期は決まってとんでもないパフォーマンスを出してしまう傾向にある。それに加えて精進不足から来る視野の狭さ、定数倍感覚のズレによってえらい目に遭ってしまった。
A - UFO Invasion
直前に似たような問題をtwitterに投げていたので少しドキッとした。
B - Sign of Friendship
初見では角度が問題の本質だと思った。arctanや二分探索(今回は誤差はあまり気にしなくていいので)が思い浮かんだ。
「これ二分探索必要だったのか」と実装中に思いもしたが、普通に実装して通せた。
このときの順位は普通だったと思う。
C - MAD TEAM
Dを先に解いている。
最小値の最大化ということで二分探索が結びつくわけだが、これは最大値の最小値の最大化なのでなかなか一筋縄ではない。
制約的に考えると2乗対数時間だが、この場合定数倍が重いと破滅の可能性があり、定数倍は軽めに作る必要に迫られた。
答えを二分探索しながら二乗で2人選出して、残りの1人を選ぶ時、 足りない部分のパラメータを充足してくれるような人間を求めることになるが、これをO(1)時間で行わねばならない。
充足する必要のあるパラメータの組み合わせ2^5 - 1に対して、充足しなくてはならないパラメータの最小値が最大のものを先に選出しておけば良い。この前計算で解くことが可能になった。
ところで、この場合二分探索が必要なく、この31人の中から3人選べば十分だということに気付けたので十分実行時間に余裕を持って制することができた。
順位はこの時点で悪くはないものだったと思う。Eを速い時間で通せれば橙パフォに大きく近づくので本腰入れてEに取りかかった。
D - Message from Aliens
reverseしているかどうかを持ってクエリを処理していくような問題は最近何度か見ている。
いつも通りやるだけだが、先頭追加があるのでdequeで実装した。
結構手間取った気がしていたが、この時点で200位切っており好順位につけていた。
E - Sneaking
読んですぐ頂点倍加してのdijkstraであることには気付けた。頂点数が10^5を超えた時に自分のdijkstraは定数倍がでかすぎて通らないことがあったので、陽にグラフを持たない方針で空間計算量を削減して解くことにした。これがすべての始まり、あるいは人生の終わりだった......。
(y, x)→(y - 1, x)方向の移動についての処理が頭の中でぐちゃぐちゃになってしまい、結局7ペナつけた上に本番中に通すことができなかった。なお、陽にグラフを作ってdijkstraしても十分余裕を持ってACできた。
定数倍感覚を改める必要があるのと、微妙な計算量なら最悪ケースを作って試してみることを教訓、ぐちゃぐちゃ実装を作らないことを課題とした。
F - Encounter and Farewell
あまり読めていない。本番中ではおそらく合計5分くらいはこの問題を考えていた。
さて、Eまで一応復習したことだし今からこの問題を考えてみることにする。
-
全域木の問題っぽい。ある頂点xを木に加えることができる場合に後回しにするメリットはない。0からいろいろ繋いでいくことにしてよい。
補グラフが与えられての全域木問題と考えられるか。数列Aの補集合を取るとxor基底がいくらか得られて、これで1~2^N - 1を作る問題に落ちた。なるほど。Eで焦っている時にF見ても解けはしなかっただろうと思うのでまあいいか。
なんかここまで解けた気でいたが、構築パートが難しい。一旦基底に分解すると厄介だ。
基底で新たなベクトルに対してxorを行って新しい基底を作る操作は辺を張るのと同義。のはずなんだけれど
ごちゃついたがなんとかAC。
小さい方から数列Aに含まれない数xを見ていって、まず0からxへの辺を張る。それまでに手に入れた基底でxorを貪欲に取りながら見たことのある数に辿り着いたらbreakする。そこまでの遷移をすべて辺として持つ。ということを繰り返して、最後に持っていた辺を使ってunionfindで全域木にする。という方針だった。
ごちゃついてペナしまくった原因だったのは「それまでに手に入れた基底を使って」という部分だった。本来log(N)個の基底が手に入って、それで以って連結グラフにできるはずなのにグラフの構築と基底の作成を同時に行ったために連結になっていなかったのだ。基底パートを2回回すことで無理やりAC。
総括
Dくらいまでの問題はいつものABCよりやや難しかったが、良いペースで解けていた。少し数学すればいい部分を実装パンチに持っていったところは少し反省。E以降はこの世の終わりのような実装でレートを持っていかれてしまった。定数倍感覚のアップデートが必要なのがわかった。もったいないペナとかしないように気を付けたい。焦って視野が狭くなるのを感じたら一回横になって天井を見ることにしているが、今回は感覚として焦っていると感じなかったのでこれを行わなかったが、20~30分おきに天井見てゴロゴロした方がいいのかもしれない。