08/10(月)
昼頃に目覚ましをかけておいて、頑張って起きる。生協に行こうと思ったけど、どうやら祝日で休みらしい。ちくしょう。
無理やり起きたのでハチャメチャに眠い。レポートを書く。講義で扱ったクイックソート・ヒープソート以外で、2種類のソートアルゴリズムについて図などを交えて動作原理を解説し、平均時間計算量と最悪時間計算量を記せという問題だ。いやだ。でも単位は欲しいので書くしかないんですよね～～～
適当に錬成する。ボゴソートとか書いちゃうのはウケ狙いにしても寒い感じがするので、無難にマージソートとバブルソートを書いた。バブルソートの平均swap回数の解析はよくわからないが、比較回数は明らかにO(N2)だろう。計算量の解析は比較だけ書いておく。
バブルソートといえば、僕が高校生のときのとやま科学オリンピック2016の数学部門で、ソートアルゴリズムに関する問題があった。このPDFの4ページ目だ。
http://www.pref.toyama.jp/cms_pfile/00019053/01301460.pdf
2021/06/14追記：リンクが切れていたので更新。https://www.pref.toyama.jp/documents/9894/01301460.pdf
最後の問題は、特定の数列でバブルソートよりも比較回数が少ないソートアルゴリズムを構成せよという問題だ。こんなの知らなきゃできないだろ、という印象。幸い僕は当時すでに競プロを始めていて、マージソートを実装したことがあったので、それを書いた。まあ問題はここではない。(2)の、バブルソートの比較回数の最大値の話だ。
問題文には、「なおこの繰り返しは、交換が起こらなくなった時点で終了します。」と書いてあるので、ソート済みの列に対してバブルソートを実行すると、一回左から右に舐め終わったら即座にbreakする実装であると読み取れる。なのでN=8の時、総比較回数の最小値はN-1=7のはずだ。ところが最初の採点では、常にループを最後まで実行するとしたときの比較回数N(N-1)/2が最小値（かつ最大値）とされていたらしい。アホくさ。
まあ幸い修正されていたので点数は来ていた。
とやま科学オリンピックの数学部門は毎回情報系の大問が1つ用意されていて、ほかには確か「最大フロー<=最小カットを自分の言葉で説明する」という問題があった。等号ではなく、不等号だ。受験会場では手も足も出なかったことで印象深い。ちなみにその年はまだ競プロを始めていなかった。
話は戻るが、レポートが終わって一息ついたところで布団に倒れこみ、3時間ほど寝てしまった。
また起きて、レポートを書く。さっきのも今のも両方8/11提出のやつ。今度は複素解析の講義で、なんもわからんことで有名。レポート問題は3種類出題されており、2つは好成績を狙ったりやる気がある人向けで、残り1つはそうでもない人向け。僕は「そうでもない」側なので、それを選んで、書く。分量も示された最大値の半分くらいで終わりにする。もう無理……。
atgolferを確認すると、Vimでびっくりする更新があった。
正規表現中の謎の制御文字は、<CTRL-R><CTRL-W>だ。これでドキュメントに検索をかけると、ヒットした：
貼ったリンクの下のほうに記述がある。
実際に手元で動かしてみると、なるほど先頭の単語が拾われて正規表現に挿入される。/^\d{までタイプした時点でマッチするテキストはなくなって、「現在マッチしているテキストの末尾」がファイルの先頭になって、それで一番先頭にある単語が追加される感じか。まあ使おうと意識していればごくまれに使いどころがあるんだろうな～って程度の機能に見える。どれだけ仕様を熟知しているんだ……ヤバすぎる。一生勝てへん。
そうこうしているうちに、また昼近くになってしまった。今から寝るが、すぐ起きて頑張って生協に行きたい。完徹はちょっとしたくない。
08/11(火)
また昼頃に目覚ましをかけて、起きる。超がんばった。これで生協に行ける。
残念ながら学食の昼の部は終了していたので、購買でパンを買おうとした。しかしこれも売り切れだったので、仕方なくバームクーヘンを購入。うまい。
注文していた森見登美彦の新作を、ようやくのことで手に入れる。ちゃんと初版だった。一般にどんな本も初版だと嬉しい。
学食の夜の部が始まるまで、あと1時間半ほどある。髪の毛が伸びてきているように感じるので、床屋に行く。
床屋に行った後郵便局でatgolferを動かしているサーバの使用料を払い込んだりしていると、学食の夜の部が始まった。さっき食べたバームクーヘンが効いていて、眠気もひどくて全然おなかがすいていないが、頑張って食べることにする。
最も小さいように見えたどんぶりものを選択したが、食べ終わるのにかなり時間がかかってしまった。それでも何とか完食。家に帰る。
眠すぎるためベッドに横になり、意識を手放す。3時間くらい寝て、起きた。水曜日提出のレポートがあるので、取り掛かる。
環論の講義だ。この講義は動画を視聴する形式なのだが、ISTUという東北大学に元からあるプラットフォームで視聴する形式になる。最初の1回は動画を前に飛ばすことができない。かなり意味不明な制約だ。義務教育じゃないんだぞ。こんなの見てられないので、ほとんど視聴していない。レポート課題は別に問題がPDFで配布されるため、問題ない。
しかし講義を聞いていないのでよくわからない。演習はかなり丁寧に取り組んでいるが、そちらはかなり手厚く誘導がなされている。対してこちらは、さすがに期末レポートだけあってそんなことはない。
あと問題の意味もよくわからない部分があった。R-左加群としてどうこう、みたいなものは何を言えば十分なんだろうか。R-同型写像を構成しようとしてかなり時間を溶かしたが、結局できなかった。あきらめてただの同型を示す。いろいろググってみても、うまい対応があるようには見えなかった。
コードゴルフについては取られっぱなし。今日もVimから一つ取り上げて読む。
連番を生成するのに、このコードは2を3つ挿入して、それぞれインクリメントとデクリメントをしている。Vimには連番を生成するコマンドg<CTRL-A>があって、こうじゃ：
同じ長さじゃないか……たまげたなあ……。
こちらは要素数が3つの固定長である必要がない。なのでほかにもいろいろと応用が利く……と考えて、105要素の問題に提出してみたところ、TLEした。アホくさ。まあそれでなくても現最短より長かったので、特に粘ることもしない。
逆にこっちの取られた問題は、相当いろいろ考えていたが、縮まなかった。下手の考え休むに似たりってところか？実際、Vimで取られた最短についてはすべて、それぞれ時間を割いて縮まないか考えているのだが、全然縮まない。そのくせよく、縮まないと結論付けたはずのコードがさらに縮められているので、単純にVimゴルフがド下手くそという話。悲しい。
RubyコードをZlibで圧縮して最短を取られた。output onlyの問題でコード長のほとんどをマジックナンバーの繰り返しが占めていたため、圧縮が効いたのだろう。試しに適当な問題のRubyコードを圧縮してみたが、展開部分を含めなくてもコード長は伸びた。
変数名とかコードの配置とかいろいろ試して圧縮が効くものを探す、みたいな作業は本当にやりたくない。さらに、自作の最短コードクローラがこのコードをcsvファイルに書き込もうとして、落ちた。百害あって一利なし。一利もないのは僕の保持する最短コードではないからだ。
とりあえずクローラについては、rescueしてString#dumpをかませることで対応した。最初からdumpしようとすると、改行が全部\nになって大変なことになる。dumpしたあと\nや\tなどの一部の文字についてはgsubで戻す、という対応も考えられるが、実装が面倒。しかもそういう場合分けする対応は予期しないところで落ちがち。コードゴルフは通れば何でもありなので、すべて予期することは不可能。
08/12(水)
昼頃気合で起きて、洗濯をし、荷物をまとめて外出。この状況下で帰省を決行する。何出歩いてるんだ！みたいな炎上はしないでほしい。
かなり迷ったが、新幹線の写真を撮ってtwitterにアップロードする。これも自分の炎上リスクをいたずらに増すだけの行為。
新幹線は自由席を選択した。仙台始発の東京行きやまびこに乗る。1両にどれくらい人がいただろうか？仙台を出発するときは1両に1桁人しか乗っていなかったが、東京に近づくにつれて単調に増加した。僕は大宮で降りたが、このときも別の車両からは10数人降りていて、思ったより多いなあという感じ。
大宮で乗り換えの待ち時間が20分発生した。1つ飛ばしで座るベンチは、空きが少しだけある。平常時とは比べるべくもないが、そこそこの人がいる。
大宮からまた自由席に乗る。今度は最初からかなり人がいる。1列に1人くらいか。これは目的地・富山に着くまで単調に減少し、僕が降りるとその車両にはもはや1人しか乗っていなかった。
新幹線内で乙一「暗黒童話」を読了。7月の終わりに「夏と花火と私の死体」の読了ツイートをしたところ、薦められた作品だったが、あまりに不穏すぎて手が伸びなかった。
途中、とんでもないバッドエンドを想像して総毛だったが、実際のラストはかなり平穏に見える。
面白かったのは確かなのだが、自分の中でまだ情報が整理しきれていない。過不足なく説明されていることは期待できるが、そもそも途中何が明らかになっていないのか、きちんとカウントしておらず、まだ何か読みとれていないことがありそうにも思える。
新幹線の駅から家まで送ってもらう途中で本屋に立ち寄った。外出の機会が失われて久しく、ラノベの新刊すら満足に買えていない。リスト化してはいたので、前の巻を積んでいないものを選んで購入した。前の巻を積んでいるものは、仙台の部屋に置いてあるので、ここで買ってもしょうがない。
思ったよりたくさん買ったので、結局半分くらいは読みきれず仙台に送ってもらうことになりそう。
そういうわけで、今日はコードゴルフをしていない。Vimで縮められたものが1つあって、これの精読は明日以降に回す。実家のパソコンの準備をする必要がある。スマホからではnon-printableな文字を判別するのが難しいからだ。
08/13(木)
4時間くらいで目が覚めてしまう。再度寝ようとして、あまりの暑苦しさにエアコンを付けたところで目が冴えてしまった。諦めて本を読む。
午前中に墓参りに行ったあとは、家で延々本を読んでいた。昨日買ってきたラノベを3冊消化した。
少し前に、Twitterでゴルゴ13の「白龍昇り立つ」という回が話題になっていたことを思い出す。実家にあるので、読む。エアコンのついていない部屋で読みふけっているとTシャツが汗まみれになった。
姉が面白そうな本を持っていた。「ドキュメント 道迷い遭難」と「ドキュメント 気象遭難」。気象遭難のほうをパラパラ読んだ。グループで遭難した事件の生還者に聞き取り調査を敢行している。このため、故人の仕草や言動が克明に描き出され、台詞からその最期が圧倒的な臨場感を持って迫ってくるように感じられた。
「ホット・ゾーン」という本を薦められた。以下のリンクで第一章の冒頭が読める。一気に引き込まれたので、この場で姉から借りて読むことにする。
第一章を読み終わったところで、今日は終了。
コードゴルフについて。ほとんど行っていないが、一応昨日言及していたVimのコードは読んだ。
そういうことをするのか……。このOで挿入した文字列を".で参照するテクは初出ではない。しかし冒頭にある程度長い行を追加するというのは問題を解くアルゴリズムでも必要だったようで、まさに一石二鳥。
H<=50なのでggはHでも代替できるのではないか？と考えたが、2ケースほどWAになってしまった。
08/14(金)
昼頃起きる。よく寝た！atgolferを確認すると3つ取られている。ベッドに座り込んだままノーパソを引き寄せて確認する。2つ取り返したがVimで取られたもう1つは自分では縮められなかった。
5/13の夜から5/14の昼にかけて1日だけ行われていた言語アップデートのときに、とりあえずdcで縮めたものがそのままになっていたが、発達したテクを適用して大幅に縮められていた。なんとかさらに-1Bして取り返した。
これは式変形によるものだ。AとBを読み込むが、Aの方だけ-1して、残りは同じ数式に適用したい。これは、Aだけ最初に読み込んで-1したあと、ループに入るしかなさそうだ。
しかし、Aを処理する前と後で異なるものとしてスタックの深さを利用することを考えると、A-1とB-0を処理する代わりにA+0とB+1を処理することが考えられる。これ向けに数式を変形する。
まず、最初の数式はf(n)=n(n+1)(3(n+1)^2+(n+1)-2)だった。これはnがスタックにある状態でd1+dd2^3*+2-**でできる。避け得ない1+のあとも、rすることなくdして流れるように計算できている。これは、数式の各項がn+1を起点に計算するようにまとめられているからだ。
ところが、n+1がスタックにある状態からではd1-rdd2^3*+2-**と+1Bになってしまう。見てわかるとおり、1-したあとにわざわざrしている。これは、長い。
そこで、f(n)=(n+1)n(3n^2+7n+2)としてみる。先ほどと同様n+1がスタックにある状態を考えよう。そのまま実装するとd1-dd2^3*r7*+2+**である。rなんぞ書いていて、更に係数も掛けていて先程のものより明らかに長い。
ここで、f(n)=(n+1)n((3n+7)n+2)にしてみる。このような式変形は、例えばPerlのような、変数名が2文字かかる言語以外では見にくくなるだけでコードの長さは変わらない。しかしdcでは劇的に効く。d1-dd3*7+*2+**だ。さっきのものと比べると-3B、一番最初の数式のnがスタックにある状態のものと比べると±0Bになる。確かにrを一切使用せず、dして増やしたものをまた順にまとめていく、（主観的に）きれいなコードだ。
式変形では長さは変わらないが、これとzを使うことによってAとBの処理を入力までまとめて行えるようになった。それが効いて、全体で-1Bという結果になった。
昨日読みさしにしていた「ホット・ゾーン」を読んでいく。上巻が終わって下巻も残り1章というところで耐え難い眠気に襲われ、4時間ほど寝てしまう。起きて夕食を食べ、読み切った。
非常に興味深かった。現在の感染症が世界中を席巻している状況下で読むと、一段と深く考えさせられる。というか普通に怖いんだが？
次に森見登美彦の新作「四畳半タイムマシンブルース」に取り掛かることにした。数十ページほど読んだところで今日は終わりにする。明日はABCがあるので、今ブログを書いたりしているノートパソコンではなく自室のデスクトップPCを起動しておく必要がある。もうかなり長いこと使っているし、さらに前回使用してから数ヶ月開いているので、結構動作が不安定だったりする。起動してから10分くらいは何をするにしてももっさりしていて、重い。
まあスペック的には今のノーパソより圧倒的に良いし、モニタも2枚あるので、やはりデスクトップは……最高やな！
最初にデスクトップPCを買ったときは、最も安いモニタを探して買った。当然スピーカーなぞついていないが、別に買えばそれでいいじゃんとなった。実際モニタにスピーカーが内蔵されている必要性を感じなかったので、今仙台にあるPCのモニタもスピーカーはついていない。しかしそのため実家のPCにつないでいたスピーカーを仙台に持っていってしまったので、こちらでは音楽を流したりできなくなってしまったのがちょっと不便。イヤホンをつなぐと音量MAXにしても小さいと感じるくらいの音しか出ない。
よく考えたら実家で夜中のコンテスト中に音楽流すのは結構迷惑だな！
08/15(土)
起きたら午後8時くらいだった。14時間寝た。まだ眠い。意味不明。
ABCがあるので、出た。実装重めで、D問題からすでに1000Byteを超えるコードを書いてしまった。Fは去年のICPC横浜で見たが、文字列を右から見るか？左から見るか？みたいなフラグも必要で、これまた実装が辛かった。
コードゴルフ的にはまあまあ。D以降を縮める気にはなれないが、AとBとCの最短は（この日記を書いている時点では）確保している。A問題なんか発想一発みたいなコードで、コンテスト開始40分くらいの時点でようやく気付いて提出したので、速度的に負けているかな～と考えていたら取れた。
Bについては、Rubyは組み合わせの生成が短いが、Rakuで比較演算子をつなげて書ける（A<B<C<A+B）ことが効いているらしく、そちらが最短になっている。これはよくわからない。Rakuで順列を生成するとき、要素の個数を指定することができず、強制的に全体の順列になってしまうのがかなり残念。
Cはdcだった。入力の1番目のXはabsを取る必要があるのだが、これはただdcで?するだけでよい。-はdcにおいて演算子であって負号ではないからだ。負の数を読み込むと、まず-が演算しようとする。今回はスタックに何もないので、何の影響も与えることなく終わり。次にabsが数値として読まれる。これでOKである。
コンテストが終わった後しばらく虚無の時間を過ごして、FHC Round 1を待つ。始まった。丸一日時間がある。これの結果は明日書こう。
合間で「四畳半タイムマシンブルース」を読了。非常に面白かった。大満足である。
08/16(日)
起きたら午後6時だった。13時間寝た。意味不明。
FHCを解かなければならない。30点でR2進出のところ、まだ25点しか確保できていない……と思っていたら、なんだかおかしなことになっている。B問題の制約が変更され、足切りも25点に下がっている。
昨日B問題を考えていて、エスパーしてこれっぽいなと思っていた解法に反例を見つけてしまい悩んでいたのだが、それが通るような制約になっているようだ。勝ったな！ガハハ！
B問題は、PとQを両方ソートして、より左のほうにある地点にはより左の人間を向かわせるべきである、というエスパーから、かかる時間を二分探索して、だれがどれだけ担当できるかを前から貪欲に決めていく解法が思い浮かぶ。この解法は、S>0のときには「より左のほうにある地点にはより左の人間を向かわせるべきである」が成り立たないため、不適。今回の制約変更でS=0となったため、正しくなる。
反例はこうだ。S=4、P=[9,12]、Q=[1,6,7,8]を考える。すると、P=12の人がQ=1を担当して、残り3つをP=9の人が担当したとき、かかる時間が15になって最小を達成する。この場合、座標の順序と担当が逆転してしまっており、困る。
とにもかくにも、これでB問題が解けたため、提出。昨日のうちに提出したA1、A2と合わせて45点を確保した（正確にはコンテスト終了時まで通っているかどうかはわからないが）。
A3を考えようとしたが、よくわからない。そのうち嫌になってきたので撤退することにした。どれか1個落としても通るのでええやろ。
こどふぉがある。CGRはこれまで毎回参加しているので、今回も出る。特に出るにあたって支障はないし、CGRじゃなくても出るんですが。
C問題から早速詰まってしまい、Fも解けるのに途中嫌になってポカンとしていたしで散々な結果。6完223位で-23。F問題はスタックでゴリゴリやったのだが、なんだか頭のいい解法があるらしい。よくわかっていない。
今日はコードゴルフをした。
<CTRL-R>-で"-レジスタの中身をコマンドラインに貼り付けたい。これは:で書いている時には可能だが、QでExモードに入ったときはできないらしい。gQでExモードに入ると、:と同じ扱いになるため可能になる。
もしかしたら僕が方法を知らないだけかもしれない。怖いが、Qのドキュメントには「通常のコマンドライン編集機能は使えない」と書いてあるし、<CTRL-R>はコマンドライン編集機能の一部なので、たぶんできないだろう。+0Bで行えない以上、gQとすることで+1Bで達成しているので、これが最短のはずだ。
こどふぉ中にFHCが終了した。出したものは全て通って、R2進出。一安心。
さて、実はまだ前期のレポートがすべて終了したわけではない。ラスボスの計算機数学Bが手つかずで残っている。本当は代数学概論B演習もいくつか提出できるものはあるが、こちらはもう単位取得には十分な量の課題を提出したことだし、諦めることにする。8/5ぶんの日記に、次の一文がある。
実際は他にも任意提出の課題が毎週出ていて、これは期限がまだ先。これまで毎回出してきているので、せっかくだし全部出したいところだ。
週記（2020/08/03-2020/08/09） - kotatsugameの日記
これのことだ。結局出さないことになってしまった。残念だとは思っている。
