2023/08/21
21時ごろに起きる。どうしてこんなことに…
スプラトゥーンをやる。現在のカタログレベルが60で、シーズン終わり(8/31)に間に合わせるためには一日4上げないといけない。結構厳しいぜ!
2023/08/22
12時ごろに起きる。
外出マン。外が暑い!
帰り際にファミマに寄って、クレープとアジのスナックを購入した。アジのスナックはここ2週間くらい半額で投げ売りされているもので、なんだか気になったので買ってしまった。袋を開けてみると、青魚っぽいあの匂いと、アジフライ的なソースの匂いがした。結構うまい。
家に帰ってエアコンを起動してみたら、とんでもない異音がしてびっくりした。リモコンで冷房開始の指令を送ってしばらくすると、エアコン内部で何かが回りだし(送風?)、それがとんでもない音を立てる。ガンガンガンガンガン!!!!!という感じで、回転数が上がると共に頻度が早くなって、音も大きくなる。
大変怖いので、業者を呼んでしばらくエアコンの運転を見合わせることにした。前のエアコン不調の時は、弱いながらも若干の冷房ができていたが、今回は運転をしないという話なので大変。30℃を超える室温が常態化しそうでヤバい!
2023/08/23
12時ごろに起きる。
今日は期末試験がある日。起きると遅刻ライン20分前でびっくりした。どうして…。
焦るといけないので、とりあえずみかんジュースを飲んで一服(???)。飯を食おうと思ったけど、そんな時間もないのでそのまま出かけることにした。悲しい。行く途中にコンビニがあるので、そこで海老マヨのおにぎりを買って学校で食べた。学校でおにぎりを食べるのは二校目(MMA Contestの時の電気通信大学と弊校)。
試験をしばき、帰る。バスの中で甲子園の決勝戦、仙台育英対慶應をやっていることを思い出したので、どうにかして情報を得ようとする。映像の配信はないと思っていたので、とりあえずNHKラジオを聴くことにした。音量を最小にして、スマホを耳に当てている不審者が誕生。
バスを降りると、近くにベンチがあるのでそこで聴くことにした。ついでにABC278-Eの”Grid Filling”を解くことにした。
解法はバスの中で思いついていて、色ごとに区間の中にある個数の累積和作って、塗りつぶす領域の左上で全探索するという感じ。これをベンチで実装して提出するも、TLEしてしまった。アルゴリズム的には合っているハズなので、何かPyPyの遅くなる罠を踏んだのではないか?と思って色々いじってみたけど、TLEは取れなかった。
累積和の配列のループをy,x,色で回していたのだが、これが原因だった。累積羽の配列は色ごとに作られているので、このコードだとメモリへのアクセスが不連続になってCPU的に辛い。ループの順序を色,y,xに変えたらACできた。
TLE(2秒以上)していたテストケースが1100msで終わるようになってびっくり。メモリアクセスの局所性の話は知っていたので、意識はしていたけどうっかりしていた。うっかりしただけでこんなに遅くなるとは思わなかった…。本番でも気をつけないといけないわね。
https://atcoder.jp/contests/abc278/tasks/abc278_e
そうこうしているうちに、甲子園では慶應高校が点を重ねて2-8になっている。すげ〜 しばらくTwitterを眺めているうちに優勝してしまった。
Abemaで行われているネット配信の存在を知らなかったので、映像で見れたのは最終盤の一部だけになってしまった…。ただ、ラジオでもなんとなく状況がわかるのですごい。
甲子園が終わったので帰る。チカレタ…。
なんも覚えていないけど、多分飯を食ってからスプラトゥーンをしていた。
2023/08/24
午前4時近くになって、テレビをつけてみると、NHKではヨーロッパの綺麗な街並みが流れている。他のチャンネルはみんな通販番組なのよね…。しばらくぼーっとしていると、北朝鮮からミサイルが来るぞ!!!というJアラートの速報が流れ始めた。
ついでにプリゴジンが暗殺されたという情報も流れてきてひえ〜という気持ちに。
沖縄県上空を通過したぞ!という情報が出てから、特に新しい情報もなさそうなので寝ることにした。ねむい
19時ごろに起きる。
ゴロゴロしているだけで1日が終わってしまう。助けてくれ
2023/08/25
エアコンが復活して部屋が涼しくなった。文明最高!
深夜にファミマで買ったのり塩のポテチを食べた。イ〜ヒヒヒ。なんて悪いんだい
2023/08/26
18時ごろに起きる。
ABCに出る。ABCDEの5完、1600位/10347人、パフォーマンス1298でいい感じ。
A問題
きずぐすりを前から順番に見ていって、条件を満たす薬があったら出力して終了。Aはソートされた状態で入力される
B問題
答えは一意に定まるという制約があるので、連続する整数の端が答えになることはない。
入力をソートして隣接する数を順番に見る。差が2だったら、その二つの間の数が答えになる。
C問題
DFSで経路を列挙する。最初はCPythonで提出したが、TLEしてしまった。CPython 3.11で再帰関数が早くなったと聞いていたけど、それでも足りなかったらしい。PyPyは再帰が遅いという話を聞いているので、恐る恐るPyPyで再提出したら間に合ってACできた。
PyPy再帰(訪問済み集合の管理にsetを使用)が1500ms、PyPy再帰(訪問済み集合をビットで管理)が900ms、それを非再帰にしたら560msになった。結構変わるものね。非再帰版をCPythonで投げたら変わらずTLEした。
D問題
よくわからず、一旦飛ばしてE問題を解いた。戻ってきて、まずは問題文を理解するところから…。
選挙を題材にした問題らしい。ある選挙区で過半数を得ると、Z_i個の議席を獲得できる。過半数の議席を獲得すると、選挙に勝利できる…。という感じ。問題文の「議席」を「選挙人」に置き換えると、アメリカの大統領選挙の仕組みと同じになる。問題名のPresidentはそこから来ているぽいわね。
何人寝返らせると、何個の議席を獲得できる…という風にすると、ナップザック問題みたいになる。DP[i個以下の選挙区で][j議席獲得するために] = 寝返らせる必要がある人数の最小値 という感じでやった。後から考えてみると、DP[獲得する議席数] = 寝返らせる必要がある人数の最小値 でも良かった。
E問題
D問題を飛ばして読みに行ったけど、思ったより簡単ぽかったのでこっちを先に解くことにした。
入力から視線の情報を前処理して、見られる部分を壁と同じ扱いにする。あとはBFSで最小コストを求めて出力するだけ。実装で色々バグらせて時間がかかった…
2023/08/27
風呂に入ろうと思ったけど、テレビで世界陸上の中継をしているのに気がついてしまった。気になるので見る。終わったら午前5時になっており、試験前日の人間が起きている時間じゃないぞという気持ちに。
試験の予定を確認して、眠る。
2023/08/28
眠れず、そのまま試験に向かった。
3つの試験を受けて、そのうち2つはいい感じだったのだが、残りの一つ、数学Aで大事故が発生。試験本番になってnCrの計算方法を忘れてしまい、今回の範囲である集合・組み合わせ・確率のうち、組み合わせが崩壊。確率も共倒れという形になった。
数日前にnCr mod 1000000007を計算する問題を解いたからか、脳内の計算式がコンピュータ向けのn!/(r!(n-r)!)に置き換えられてしまった。眠っていない状態で頭もよくまわらず、計算方法を再発明することもできず…。「ヤバいぜ!」とツイートしたら、「自分はnPr/r!で計算している」という空リプがあった。なるほどすぎる。これを本番で思いつければ…。
ちゃんと演習をしていたら覚えているだろという感じなので、後期ではこういうことがないようにしたい。
試験の事故で心が穏やかでないので、帰り際にセブンイレブンでうみのこカレーを買って帰った。去年の同じくらいの時期にも食べたわね。前回は乗船何十万人記念!という感じだったけど、今回は40周年!ということらしい。毎年何かと理由をつけてやってほしい(???)
家でカレーを食べて満足し、ベッドでゴロゴロしていたら眠ってしまった。冷房をかけないまま眠ってしまい、部屋があまりにも暑くなって起きた。とんでもなく汗をかいた。