週記（2020/09/21-2020/09/27）

09/21(月)

午前10時くらいに目を覚ます。予定まで2時間を切っているのに二度寝する気にはならない。起きる。昼食のために学食に行こうとしたが、今日は祝日で休みであった。仕方がないのでコンビニで適当に買う。

ライブコードゴルフ大会に出演した。これについては参加記を書いたので、そちらへのリンクを貼るだけにしておきたい。

kotatsugame.hatenablog.com

一点、特別に書き残しておきたいことがあった。Rubyは僕は一切手を付けていないため、参加記にも欄を設けていない。このRubyについて、外部の方が引用RTでコードを縮めてくださったので、それを参照できるようにしておきたい。

$<.map{p$s&&_1>$s?0:($s=_1;1)}（30B）、または$<.map{p _1>$0?0:($0=_1;1)}（27B）。

特殊変数を使う発想は僕にもあったが、何か都合のいい初期値を持つ特殊変数を（しかも変数名が記号1文字のものの中から）探そうとしてしまった。30Bのほうは、初期値nilの普通の特殊変数を使って、nilかどうかの判定もしているものだ。nilかどうか判定するのは長いと思っていたけど、それは僕の直感が間違っていて、きちんと試せば短くなることに気づけたと思う。失敗。

27Bのほうは、都合のいい初期値を持つ特殊変数として$0を使ったものだ。これ思いつけなかったのかなりショックだな。実際は$0、つまり実行時のファイル名がいかなる2桁の数値よりも辞書順で大きい必要があるので、ジャッジ環境の詳しい仕様を把握していないため本当に通るのかはわからない。コードのファイル名にa.rbとかmain.rbとか使っていればよいが。

コードゴルフ大会が終わった後、ACPC day3に参加した。1時間遅れだったけど、そんなことは全く関係なく、普通に2時間くらいかけた問題が解けなくてつらくなってしまった。実際は途中でふて寝したりしてるので、椅子を温め続けたわけではない。

日付が変わるころ、今年のJOI予選第1回の問題が公開された。すかさず解いて縮めておく。自明な問題の短縮は速度が命。実際、A問題はすでに何度も出題されているような問題設定だったので、覚えていた最短コードをそのまま書いて終わり。

さて、日付が変わって9/22、秋分の日である。今年の秋分の日は秋分コンテストの日。ということで、これから午後4時くらいまでずっと秋分コンテストをやっていた。これについても参加記を書いたので、リンクを貼っておく。具体的にどういうムーブをしたのかとかは書かない。覚えてないからね。

kotatsugame.hatenablog.com

午後4時頃に、パソコンに向かっていても意識が保てなくなってきたので、寝た。当然日記など書いている余裕はないので、この日の日記は後日書いたものだ。

09/22(火)

午後10時頃に目を覚まし、すかさず秋分コンテストに参加する。R問題はtozangezanさんがリアルタイムで旅をして、撮った写真の緯度経度を当てる問題だ。僕が昨日の深夜に見た段階では、謎の夜景が1枚ぽつねんと公開されていただけだったが、今見ると10枚全部公開されきっていた。

さあやるぞ、と確認したら、最後3枚で度肝を抜かれた。富山の写真だったのだ。通っていた高校や通学路のすぐそばである。一瞬で分かった。かなり興奮した。このことは参加記にも書いたが、あまりに印象深いので、日記のほうでも強調しておく。

真夜中にコンテストが終了してから参加記を書き、ほかの人のツイートを眺めたりしているともう朝になってしまった。

布団に入ってなろうを読んでいたが、どうにも腹が減って寝れないので、学食に行くことにした。帰ってきて寝た。午後3時であった。

09/23(水)

本当は日付が変わったあたりで少し目を覚ましてなろうを読んでいたのだけれど、2時間くらいでまた寝たので、この日はなかったことにする。

09/24(木)

午前6時くらいにベッドから身を起こす。それ以前に意識は取り戻していたが、「ぽきた」のツイートをしたのはこの時間。

たいぺーと待ち合わせて学食に行き、帰ってきてラノベを読んでいると、ホスフィンから「スキャナを使わせてほしい」との連絡がきたので快諾。夜に部屋に来ることになった。少し掃除をする。

お酒を持ってきてもらったので、飲酒しながら映画を視聴する。僕の部屋に集まるときはこれが定番。なぜなら僕の部屋には遊べるようなものが何一つ存在しないので。

「夜は短し歩けよ乙女」の映画を観た。原作は全然読み返していないので展開などあまり覚えていなかったから、差分を観察することはできなかったが、そういう楽しみ方でなくても普通に観るだけで超面白かった。偏屈王が思ったよりミュージカルしていてびっくりした。しかし城ヶ崎氏のダッチワイフのくだりは何の説明もなかったので、原作を読んでないとわからないんじゃないのか？

次にホスフィンが観たいというアニメ映画を見ることになったのだが、僕が限界に達して床で意識を失ってしまったらしく、視聴は取りやめになった。正直スマン。

あとは動画投稿サイトで各々の好きな動画を布教しあっていた。僕はラーメンズが好きなので、コントをいくつか見せようと思ったのだけれど、これといって心に決めていたものがなかったので、かなり迷ってしまった。

結局「五重塔」「日本語学校アメリカン」「バニー部」「受験」を見せたけど、この選択には心残りがある。新しい公演からもっと選んでもよかったかもしれない。

午前3時半、お開きになる。ホスフィンはこれから歩いて帰る。僕はもう身動きが取れないため、後片付けは明日にして即座にお布団イン。就寝。

09/25(金)

起きたらちょっと気持ちが悪い。最近翌日まで響く酔い方をしていなかったので、結構つらい。食事をとらずにパソコンを触っていたらどんどん気分が悪くなっていったので、インスタント味噌汁を飲んだ。少し楽になった。

今日はゲームセンターに行くつもりだったので、微妙に怪しい体調を抱えて行く。これ風邪の諸症状とかじゃないよね……？

本屋さんに寄って本を買った。以前から買おうと思っていた新刊が3冊と、うっかり手に取ってしまった4冊。直前に遊ぶお金を下ろしていたので財布の中身に余裕があり、手に取って迷った本は全部買ってしまった。

チュウニズムについて、9/30までのマップが2つ残っていたので、これを進める。結局終わらなかったんですが……。期限までにまた行きたい。

疲れ切っていたので、帰ってきて風呂も入らずベッドに倒れこんだ。午後11時のツイートを最後に寝落ちした。

09/26(土)

朝早い時間に目が覚めて、ハーメルンを読んでいた。午前11時ごろに起床ツイートをしたが、まったく実態に即していない。

今日はTCOのRegionalだ。今年はオンラインでの開催となった。去年は思いっきり寝坊してらてあに迷惑をかけたことを覚えているが、オンラインならば問題はない、というか、別に参加しなくとも何にも言われなさそう。交通費とか出てるわけじゃないので……。

アルゴリズムラウンド以外に興味はないので、開会式とかは見ない。正直Regionalに参加する意思表示だけしたらTシャツが降ってくるんじゃないかと思っているが、念のためコンテストに参加しておく。div.2レベルの問題と宣言されているくせに全員Ratedなのはもはや定番。こういうのでレートを稼ぐと赤になりやすい。

Easyは忘れた。Medはある数の値を決めるために中央値を使ったけれど、最小のものを出力しなければならないことを忘れてA[A.size()/2]としてしまった。これはA.size()が偶数のとき最小ではなく最大の値となってしまう……と思ったら、実装の都合上偶然符号を反転していたのでセーフ。これは本当に意図しないラッキー。2人にチャレンジされて戦々恐々としていたが、おそらくこれに関係するものだろう。

Hardはよくわからない。よくわからないなりに、適当なところまで全探索して残りはDPした。これでうまくいく理論的な証明は一切行っていないが、提出した後にありうるすべての入力を試して正答したので自信はある。手元で何並列かして試していて、本当はすべて試し終わった後に提出しようと思っていたのだが、実際には時間がかかりすぎるので待ちきれなくて20%くらい終わった瞬間すぐに提出してしまった。そのまま走らせ続けた結果すべて正答したからよかったものの……。

コーディングフェーズ終了直後は24位くらいだったか？16位以上は何かあるらしいけど無理だろうな……と思っていたらシステスでボロボロ落ちて16位に滑り込んだ。かなりびっくり。2206→2246(+40)。

とりあえずTCOのワイルドカードラウンドへ進出したが、Regionalのイベントとしてもう1つ、1対1のトーナメントがある。短い時間で1問解いて、点数が高いほうが勝つ。僕は16位なので、初回の相手は1位のACRushさんだ。草。無様は見せられない。

最初、数秒差で負けて非常に悔しかったたが、ACRushさんがリサブした。このままシステスが通れば僕の勝ちだが、ACRushさんがリサブするような罠があったのだろうかととても怖かった。実際には何事もなく通った。ACRushさんの解法と僕の解法は異なっており、ACRushさんの解法だと32bit整数がオーバーフローしてしまっていたらしい。ACRushさんが配信にコメントしていたのを見た。

配信で何度か僕の名前を読み上げられたのだが、kotatsugameのgameの部分は何度読まれても「ゲーム」になってしまう。わかるよ。わかるけどウケる。

2回戦は普通に問題が解けなかった。ちゃんと式を書いて変形するべきだったのに、それを怠ってサンプルから合わせにいったせいだと思っている。結局0点で、相手の人も0点だったが予選の順位差で負けた。16位はつらいぜ。

ともかく、これでTCO Regionalの僕が関係するイベントはすべて終了。あとはABC（ACLBC）の時間までラノベを読んでいた。

ABCは全完9位。F問題は畳み込みとしてとらえるのに時間がかかり、また高速化が足りず1回TLEしてしまった。同じものを何回も畳み込んでいるように見えたので、ここを2分累乗法で実装したら通ったが、計算量はよくわからない。まあでもやばそうなのは1..sqrt(N)まで1回ずつ畳み込むケースだけど、これはO(N log N)くらいでできそうなのでいいのかな？想定解は小さいほうから2個ずつマージしている。この発想は何回か見た覚えがあるが一切身についていないらしい。

ベッドでハーメルンを読んでいたら、寝落ちしてしまった。たしか日付が変わったくらいの時間だったはず。

09/27(日)

午前7時くらいに目覚めて、ずっとハーメルンを読んでいた。本当は結構眠気があって二度寝したかったのだが、ハーメルンを読むのをやめられなかった。

昼頃、あきらめて起床報告をし、食事して、またベッドに転がってハーメルンを読み続けた。結局そのまま午後8時くらいまで読み続けていた。眠気がかなりあるが、今日もAtCoderのコンテストがあるので、意地で起き続ける。今日のコンテストはChokudai Contest、つまりマラソンだ。

まず、盤面すべてを1色で塗りつぶさないとお話にならないことを確認する。次に、どんどん連結成分を大きくしていくといいんじゃないか？という直感から、同じマス目を連打することを考える。最後に、変える色は連結成分が最も大きくなるような色がよいだろうと考える。実際にはこれはたぶんよくなくて、盤面の端のほうに速くたどり着く必要があるため、それを優先するべきだったらしい。なるほど。

ともかく、コンテスト中は以上3つのことを実装した。これにはランダム性は一切含まれないので、連打するマスさえ決定すればスコアは常に変わらない。テストケースが公開されているので、それぞれに対して連打するマスを全部試し、最もスコアが高くなるものを埋め込んだ。計算は結構時間がかかるので、プロンプトを7個開いて7並列で実行していた。手作業で埋め込みを行ったので、かなり面倒だった。その甲斐あってか、終了時点で全体20位とギリギリ順位表の1ページ目に滑り込んだ。

1点変更しか実装したことがないので、今回はそれが使えずマラソンをやってる感じは全然なかったのだけど、ビームサーチができるらしい。そりゃそうか。いずれ実装できるようにならなければならない。あと焼きなまし法の温度関数もどういう風に書くのかよくわかっていないので、マラソンをするにあたっての課題はかなり多い。

日付が変わってからこどふぉのdiv.1があるが、眠すぎるので見送る。起きる時間はかなり健康的だけど、健康的な生活を送るとコンテストに出られなくてかなりつらい。