2023/08/14
18時ごろに起きる。
台風の影響で外が騒がしくなってきた。テレビをつけてみると、京都の綾部市で川が溢れたそう。綾部市の防災・危機管理課の課長の人が電話取材に応えており、こんな真夜中なのに大変な仕事だなあという気持ちになった。
普段は夜になると、大勢の謎の小虫が窓にくっついているのだけど、今日は台風のせいか全く小虫がいない。飛んで来れないのかもな。
2023/08/15
18時ごろに起きる。
相変わらず外は荒れているぽい。
妖怪PCいじいじ。
ABC230-Dの”Destroyer Takahashi”を解く。区間スケジューリングだ！！と実装して提出してみたけど、WAが出てしまった。あれ〜と思い提出したコードを確認すると、破壊された壁かを判定する条件がl_i <= x <= r_iになっていた。どうして…
l <= nowに修正して再度提出したらACできた。
GitHub Copilotのチャット機能の存在を思い出したので、提出したコードと一緒に「もっとシンプルなコードにしてくれ！」と言ってみたら、本当にシンプルになって返ってきてびっくりした。
https://atcoder.jp/contests/abc230/tasks/abc230_d Pythonで書いたやつ: https://atcoder.jp/contests/abc230/submissions/44624235 C++で書いたやつ（Copilotがシンプルにしたやつ）: https://atcoder.jp/contests/abc230/submissions/44624311
ABC230-Eの”Fraction Floor Sum”を解く。いろいろ実験をして、N // X = AになるXの個数を数える方法は分かったが、それ以降がわからず解説AC。整数をいじいじする問題よくわからんのよな…
https://atcoder.jp/contests/abc230/tasks/abc230_e
ABC217-Eの”Sorting Queries”を解く。サンプルを睨んでみると、ソートされている部分とソートされていない部分で列が別れることに気がついた。列の先頭を取り出す操作があるので、ソートされている部分を優先度付きキュー、されていない部分を普通のキューで管理するのが良い。全体をソートするクエリが来た時は、普通のキューの要素を全部優先度付きキューに放り込んで、普通のキューを空にする。
switch-case文が使いたくなったので、C++で実装をした。雰囲気でそれっぽいものを書いてみるけど、どうもうまく動かない。ちゃんと調べてみると、処理の最後にbreak;と書いておかないと次のcaseの処理に行ってしまうことがわかった。初見殺しすぎるだろ。break込みで提出するとACできた。やったね。
過去問のジャッジも新しくなったら、Python 3.10で追加されたmatch-case文を使って似た書き方ができるようになる。期待〜
https://atcoder.jp/contests/abc217/tasks/abc217_e https://atcoder.jp/contests/abc217/submissions/44624786
Eテレで帰ってくれタローマンの再放送をやっていた。NHK製ポプテピピック
2023/08/16
ABC233-Eの”Σ[k=0..10100]floor(X／10k)”を解く。Pythonの多倍長整数を使った愚直解を提出するとTLEした。そりゃそうだ。何か高速化を考えなければならん。サンプル1の計算を足し算の筆算の形で書き起こしてみると、入力の桁が連続して縦に並ぶことがわかった。累積和で各桁ごとに計算して、繰り上がりを処理して出力するとAC。
https://atcoder.jp/contests/abc233/tasks/abc233_e https://atcoder.jp/contests/abc233/submissions/44631949
眠れず、14時ごろまで活動した。
20時ごろに起きる。
AtCoderの提出コードの表示と、コードテストのエディタが新しくなっていた。特にコードテストについては、iPadなどでのコードの選択・コピペがやりやすくなったので大変良い。若干の不具合はあるものの、より便利になったと感じる。
ABC202-Dの”aan aba baa”を解く。辞書順の気持ちになって考えないといけないぽいが、未履修な上しばらく考えても思い付かなかったため解説を読んだ。理屈はそんなに難しくなかったけど、なかなか面白くて良い。ほえ〜〜〜
https://atcoder.jp/contests/abc202/tasks/abc202_d https://atcoder.jp/contests/abc202/submissions/44649159
2023/08/17
20時ごろに起きる。
ARC108-Aの、”Triangular Relationship”を解く。a + b, a + c, b + cが全てKの倍数になるという条件を、Kで割った余りが0になるに変形して、mod Kで考える。
aを固定すると、bは0以上K - a以下だとわかる。これで全探索…は間に合わないので別の方法を考える。愚直全探索にサンプルを入力していろいろ眺めてみると、条件を満たす組が、全て同じあまりの数でできていることに気がついた。まだ憶測の域を出ないので、どうにか証明したい気持ち。
問題文に載っているa, b, cの関係を式に起こすとa + b ≡ 0 (mod K), a + c ≡ 0 (mod K), b + c ≡ 0 (mod K)となる。 a + b ≡ b + c (mod K)から、a ≡ c (mod K)とわかる。 a + b ≡ a + c (mod K)から、b ≡ c (mod K)となり、a ≡ b ≡ c (mod K)だとわかった。つまり条件を満たすa, b, cは、Kで割ったあまりが同じ整数。
1 <= N, K <= 2 * 105なので、あらかじめあまりがXになる整数が何個あるかを数えておいて、aをKで割ったあまりを全探索するのが間に合うので、O(N + K)で問題を解くことができた。
ただ、もう少し考えてみると、条件を満たすあまりは0かK//2（Kが偶数の場合）だとわかるので、全探索せずにO(N)で解ける。
「割ってXになる整数の個数」を求めるのをサボって、ループを回して数えていた。だが、これはO(1)で求めることができるので、全体でO(1)で解くことができる。
https://atcoder.jp/contests/abc108/tasks/arc102_a 全探索: https://atcoder.jp/contests/abc108/submissions/44670258 0かK//2: https://atcoder.jp/contests/abc108/submissions/44670412 O(1): https://atcoder.jp/contests/abc108/submissions/44671355
2023/08/18
眠れず、9時ごろに活動を再会する。
外出マン。外暑すぎる。
外を歩き回ったが、なかなか大変だったわね…。坂が急で大変
腹具合が悪い！
おねむ
2023/08/19
15時ごろに起きる。
ABC315に出る。ABCEの4完。E問題が思ったより簡単（DFS）で拍子抜けした。D問題に張り付いていたら問題を見すらしなかったと思うので、とりあえず問題を見に行くのは大事だな～となった。
1341のパフォーマンスが出て、Ratingは1015になった。highest-6
ABC313-Eの"Duplicate"を解く。初めての（ギリ）青diff自力ACでうれしい。
https://atcoder.jp/contests/abc313/tasks/abc313_e https://atcoder.jp/contests/abc313/submissions/44774024
2023/08/20
10時ごろに起きる。
外暑い！
期末試験1日目。ぼーっと夏休みを過ごしていたらいつの間にか試験の日になっていてびっくりした。復習もほとんどしておらず、ヤバイぜ！と思ったが、ギリ大丈夫そうな感じだった。これで単位が落ちたら悲しい。
外暑い！
ファミマでファミチキを購入。
早起きしたのでねむい。
