22/08/24

日記を書くことで自律神経のバランスを整えることができるらしい。この日記は睡眠時間を削って書いているので逆効果な気がするが。

 

  • 朝
    • 昨日は日記を書いたせいで睡眠時間が4時間半程度になってしまい異常に眠い。なんとか寝坊せずに登校。
  • 昼
    • 学食で昼ごはんを食べた。普段はコンビニで買ったものを食べているが、たまにはまともなものを食べようという気持ちからの行動であった。辛味噌ラーメンを食べようと思ったがなかったので赤門ラーメンを食べた。ぼちぼちの美味しさ。
    • 学食からの帰り道、道の真ん中で五体投地している子どもを見つけた。15秒ほど動いていないように見えたので少し心配だったが、普通に立ち上がって走り去ったので一安心。
  • 夜
    • 仕込んだ反応の様子を見たが大して進んでいなさそうなので放置してさっさと帰宅。7時に研究室を出ると寝る前の時間を2時間ほど確保できるので精神的に良いとされている。

    • No.818 Dinner time - yukicoder　昨日の続きを進めた。下に白文字で考察を書いた。
      昨日は平方分割でなんとかすると言っていたが、流石に実装が厳しいのでもう少し良い方法を考える。DPテーブルが常に下に凸になっているという観察が重要で、実は左端と右端だけ見ておけば最適値を計算できる。これで状態数がO(1)となり、ACできた。かなり良い問題なのでfavが多くついているのも納得。

    • No.919 You Are A Project Manager - yukicoder　
      N<=10000なのでO(N^2)とかを考える。Kを全探索した後、左からとるチーム数と右からとるチーム数の組を全て試せば答えが求まる。左と右のチーム数の組を試すのは累積和によって線形時間できるので、中央値を求めるためのソートが律速になってO(N^2logN)になる。これで一度投げると微妙にTLEする。よく考えると中央値を求める部分はA_iの昇順に見ていくことで線形時間になり、O(N^2)となる。これで書き直した後、適切な定数倍高速化を行うとギリギリ通る。想定解はMo's AlgorithmによるO(Nsqrt(N)log^2N)らしい(全く頭になかった)。yukicoderをやると定数倍高速化のテクニックが身につくので良いとされている。一応非想定解ではあるが、C++でしか通らない解法を紹介するのもなと思い解説記事は書かないことに。

 

  • 日付が変わる前に書き上がったので、今日は睡眠時間を削らずにすみそうだ。