昨日は競プロの問題に夢中になりすぎたせいでかなり夜更かしをしてしまい、今朝は10時くらいまで寝てしまった。ほどほどにせねば。
昨日ハムを焼いたフライパンを見たら油というより「脂」でべとっとしていたのでよく洗った。
鉄パンをつかっているので油をあまり過度に落とし過ぎないように、いつも洗う時は軽く汚れを落とす程度にしているのだが、脂はやはり油とは別物だな。
過去にソーセージを焼いたあとでフライパンがべっとりしているのを見て、「この油脂分で卵焼いたらどうなるんだろう」と思って実験したらはちゃめちゃに焦げ付いたという経験があるのでそれで学んだ。脂はしっかり落とす。
今日解いた競プロの問題。
ABC248
A: 0から9までそれぞれについて文字列全体を走査すれば9×10の90回以内で見つかる。setなどを利用すればO(NlogN)にもなろうが、めんどかった。
B: やるだけ。$A,B,K\leq 10^9$なので、掛け算でオーバーフローする心配はない。しかしすぬけくんはいちいち叫ぶのか…
C: どの要素まで見たかと総和の値を持つDPで終わり。$O(NMK)$。
D: 要素の種類ごとに位置を持ってにぶたんすれば空間$O(N)$の時間$O(Q\log N)$で解ける。こういうのスパっと解けるようになったの嬉しいな。
E: K=1ならInfinity。K≧2の場合、ありうる直線の数はnC2以下なので全列挙して調べればOK。各直線について$O(N)$でどの点が通るか調べられるので、全体$O(N^3)$で解ける。テレビを見ながらやってたら数式処理に手間取った。片手間でやるもんじゃないな。
F: まだ解けてないが、グラフの特殊性を使えば$O(N^2)$で解けそうに見える。全体が連結であるためには、辺iと辺(N-1+i)が同時に切れていることはあり得ない。なので、どっちまたは両方をつなげるか+縦の辺を繋げるかだけ考えれば遷移していける。「左から順番にどこまで見たか」と「繋げた辺の数」を持てば$O(N^2)$のDPで多分解けるが、細かい部分が詰められてない。
散歩した。普段あまり通らない道を探検したのだが、かなり広い通りの存在を新たに知った。地元の町でも数kmも離れると知らないことはあるものだ。
途中、鉄棒のある公園を見つけたので、なんとなく逆上がりをやった。出来るかな～と思ってやろうと思ったら割と普通に行けた。昔やったときは全く出来なかった記憶があるのだが、単に成長したせいだろうか。
普通に行けたと思ったのだがやったあと腹と右肩が痛くなった。多分フォームとかがあまり綺麗でないのだろうな。
良さげなパン屋なども発見したのでいくつかパンを買った。明日の朝食べよう。
腕立てをやった。昨日はスクワットをやったので、再び続ける習慣ができればいいなと思っている。
Categories: 未分類