AtCoder Beginner’s Contest 141 感想

翌日が休日ってことでAtCoder Beginner Contest 141に参加しました
11時まで本気で頭使ってると翌日に響くんですよねえ
午前中とかの開催もやってくれないものかな
出る人いなくなる？

11時くらいまで普通に仕事でプログラム書いてた時期もあったけど
あのころはどうだったのか
平気だったのかそれとも翌日響いてることに気づいてなかったのか

今回はDまで解けて1442位
DがPriority Queueさえ知ってればACできる問題で、だいぶ簡単だったんじゃないか
Dまでできたにしてはパフォーマンスが1078と低め
Dまで35分でできてて残り時間をEにつぎ込んだけど解けそうな気がしなかった

A - Weather Prediction
ifで普通に書いたけどdictで書くほうがすっきりしたか
ついつい確実に書けるやり方で書いてしまうな
A問題くらいで時間かけたくない、的な

s = {"Sunny": "Cloudy", "Cloudy": "Rainy", "Rainy": "Sunny"}
print(s[input()])

同じ文字列を2回書いてるのが少々気持ち悪くて
["Sunny", "Cloudy", "Rainy"]からなんとかできないかと思ったけど
あんまりすっきりしない

B - Tap Dance
c not in "LUD"なんて書いてしまったのが悔しい
c == "R"でよかったんだよな
まあでも、人に読んでもらうためのコードならあえて上のように書くのも
ないこともない
いや、仕様の書き方がよくないというべきかここは

C - Attack Survival
そのまま書くとTLEになる問題
Cにしてはめずらしいんじゃないか
CまでのひとにもTLEを味わわせてあげようという親心？
一人以外全員-1ってことは一人だけ下がらないと思えば

D - Powerful Discount Tickets
高いものから2で割っていけばいいよねと
優先度キューさえ使えればすぐ

ただし解説を読んだら切り捨てについてちゃんと考察してあって反省している
こんな感じかなと思って書いて出してAC出た、で終わっちゃってた
2で割るたびに切り捨てるのとまとめて割ってから切り捨てるので
おんなじなんだっけ、と気づきが欲しかった

E - Who Says a Pun?
なんかそれ用のアルゴリズムがありそうだなーと思ったけど

まさか正規表現で解けるってことはないよなと思ったけど
まずはr"(.+).*(\1)"でsearchしてみた
TLEは出るだろなと思ったけどWAも出た
この正規表現のどこがマズいのか
フラグつけたりしないといけなかった？

その後自前で1文字の文字列、2文字の文字列、・・・と2回現れるものを
探してみてTLEを出す
予定通り

そんなこんなしているうちにタイムオーバー
解説によるとZ-Algorithmとかローリングハッシュとかいうのを使えば
解けるらしい
勉強はしないでおく

F - Xor Sum 3
問題を読んだだけ

解説を見る
大きなビットから貪欲にやっていけばいいんだな
それくらい

感想
Pythonは実行速度のせいでTLEになったりするけど
ライブラリに優先度キューとか入ってて楽できるところはある
自分で書いて持っててもいいけど
ライブラリならCで書かれてて速かったりしそうだし
優先度キュー(heapq)のほかには双方向キュー(deque)とか
二分探索(bisect)あたりはときどき使う
ほかにも便利なのあるかな？