07/20(月)
深夜、目を覚ます。眠れなかったのでレポート問題を考えていると、解けた気がしたので、いそいそと起きて書き始める。しばらく資料を見ていると、全然解けていないことに気づき、布団に戻って寝る。
起きて学食に行く。この日から学食は椅子とテーブルを解放したので、これまでのように外のベンチで食べたりしなくてよくなった。テイクアウトなんだから持ち帰って家で食えという話ではあるが。
深夜に書いていたレポートは完成させるのを諦めて、提出した。別のレポートに取り掛かる。こちらは問題をいくつか選択して解く形式で、頑張ると終わる。
本当は今日提出期限のレポートがほかにもあるのだが、こちらは演習で毎回出ているレポートだし少しくらい……遅れてもばれへんか、ということで無視する。コードゴルフをする。
ABC047~ABC058のCD問題を見る。その中から1つ取り上げる。
max(A,B)*2-(A-B)/(A-B)
という感じ。A!=B
の場合はこれでよい。問題はA==B
のとき。
0/0
をしようとすると、エラーが出るだけで何も行われない。つまり、本来ならA-B A-B
というスタックが1
になるはずが、0 0
のままになってしまう。以前のコードはここを何とかするためにzR
で一番下の要素を掘り出してきていた。
よく考えると、A==B
なのだからmax(A,B)
の代わりにmax(0,B)
をしても問題はない。つまり、スタックをA A-B A-B
という状態にしておけば、/r[max(*,B)]
で1 max(A,B)
とA 0 max(0,B)
の2種類の動作に分かれ、どちらでもスタックの上2つは求めているものになる。
[max(*,B)]
を実装する際はdlB>B
とするのが短い。これは場合によってスタックにゴミが残る。そのため、r
で下に送る代わりにk
で保存しておくとよい。これならスタックの途中にアクセスする必要がない。
2B短縮。
07/21(火)
15時間睡眠をキメてしまう。起きたら学食が閉まりかけていたので、行くのを諦めた。
睡眠負債がたまっていたのは自覚しているが、こういう負債の返し方をすると、一瞬で昼夜逆転して生活が崩壊する。実は崩壊すると困る現実世界の用事がある。
夢うつつで考えていたが、実は昨日書き上げたレポートに致命的なミスがあった。しょうがないのですべて忘れることにする。
日課のatgolferチェックを行うと、最短コードが奪取されている。これはちょっと訳あり。
AtCoderの旧ジャッジではmawk
が使われていた。これはNF>=32768
になった瞬間REを出して落ちる。そんな具合では1行に105個の数値が書かれた入力の問題を解けない。
そこでRS=FS
を実行すると、空白区切りで読み込むようになってゴキゲン……というのが主な解決策だった。主な、と言ったのは、例えばsplit($0,A)
とかでも解決できるため($1
以降にアクセスした瞬間落ちるが、$0
ならセーフ)。
で、言語アップデートにより、gawk
になった。これはNF>=32768
でも平気な顔して動く。それじゃあこれまでのmawk
のコードは軒並み縮むかというと、そうでもない。
mawk
を使ってのゴルフが盛んになったこの1年くらいで、RS=FS
に関連したテクニックが数多く開発された。そういうのを駆使することで、gawk
でフィールド要素をループするよりも短いコードが書ける。
でも中には当然縮むものもある。例えば配列にわざわざ入力を保存していると、明らかに長くなってしまう。今奪取されていたやつがその理由。せっかくなので、mawk
内の最短コード全部にRS=FS
で検索をかけて、ヒットしたものを全部確認することにした。
大体5時間くらいやったところでこどふぉがあったので、出る。C問題で詰まってしまったので何気なくatgolferを確認すると、昨日縮めて上に解説を書いたBottonsがさらに縮められている。読む。
max(A,B)==max(A-B,0)+B
。これはPerl
において特殊変数$-
を使うとかなり短く書けるため非常に頻繁に使うテクニックだが、dc
でもk
を使うと同じ理屈で短く書ける。
一応考えたことはあって、いろいろ調べた結果あんまり縮まなさそうという結論に至ったのだが、実際に縮んでいるのを見ると、してやられた!となる。
わざわざA-B
を計算していると長くなるが、別の用事で計算する必要があったなら、流用できて短くなるという事情。1B短縮されて負け。
そのあとC問題を再度考察して、ギリギリ解けたところでコンテストが終わる。微減。コードゴルフに戻る。
さらに3時間くらい投入したところで、一通りの確認が終わった。9問くらい腰を据えて考えたいものがあって、別ウィンドウにまとめてあるが、これをやる前に明日提出の課題を終わらせる必要がある。
ちなみに昨日無視した課題は今日も手付かず。
07/22(水)
昼過ぎに宅配が来て、対応のために起きたのだが、その後眠れなかった。これには理由もあって、前日進めて残り大問1つを残していた課題が解けておらず、提出期限が迫っていたためである。
布団でごろごろしながら考えていたのだが、自力では解けなかった。かといって眠るのも難しそうだったので仕方なく起きたところ、ちょうどZoomでその問題の解説が行われていることを知り、参加してみた。
結局書くのが間に合わなくて期限後の提出と相成ったのだが、まあ演習の課題であることだしどうでもよい。と斜に構えていたところ、どうやら期限に遅れると問答無用で100点満点中20点が引かれているようだ。これは……辛い。
atgolferを確認すると、面白いコードが流れてきていた。
こういうのどうやって思いつくんだろう。ちなみにこの類のジャッジぶっ壊れを利用して縮んだ問題は最近にもあって、これだ:
きっかけとしては、ツイッターでジャッジのバグ報告が流れてきたことを覚えている。自分で探し当てたわけではない。
さて、実は同じ演習の課題がもう一つあるので、これも進める必要がある。さらに別の講義にも提出物がある。こちらは毎週課されるノート1ページ作るだけの謎の課題なので秒で終わるかと思いきや、意外と苦戦した。出せば加点っぽい謎具合なんだからカレーの作り方でも書いておけばよさそうなものだが、そういう手の抜き方は個人的に難しい。
手を抜くことに関して。大学に入学してからこれまで、すべての科目において他の人のレポートを読んだことがないため、自分では真面目にレポートを書いているつもりでもゴミカスみたいな評点をつけられている可能性があると感じている。この点数学はよくて、答えがあっていたり証明が完成していれば、自分で正しいことを書いているなあとの判断ができる。
または単純に、興味のない科目のレポートを錬成するのはひたすらに面倒なので、実際レポートから不真面目さが伝わってくるのかもしれない。興味のある講義をできるだけ選ぶようにすればよいのでは?と考えていたのは大学一年生のころだけで、結局のところ期待すればするだけ、実際の講義内容と自分が思い描いていたものとの差異に敏感になって講義が嫌になる。
それはそうと、今日は一日眠くて頭が使い物にならない。夜、yukicoderに出る。かなり難しくて考えるのが嫌になってしまい、二完。そしてレポートを書くのに飽きたのでコードゴルフを始める。昨日別ウィンドウにまとめておいたものを再度チェックしただけで終わり、レポートに戻る。
結局期限を3時間くらいオーバーして提出した。まあ演習の課題だし……。
手が痛くなってしまった。手書きレポートがたくさんあるとつらい。TeX打ちは最初の敷居は高いが、一度書き始めてしまえば1つも2つもあまり変わらない。ボールペンで書くと手が疲れないという話をよく耳にするのだが、僕はいつもレポートに書きながら試行錯誤しているため、レポートを書いたり消したりする。よってボールペンを使うのは難しそうだと考えている。
07/23(木)
ひどく気持ち悪い夢を見て、4時間くらいで起きてしまう。とりあえずツイッターの下書きに夢日記を書き、再度の入眠を試みると成功。そのまま夕方まで眠り続ける。
学食の夜の部に十分間に合う時間に起きたのだが、家から出るのに失敗する。
祖母から荷物が届いて、中に野菜が入っていたので、そのまま食べることにする。「塩をふって食べるとおいしいかと思って入れた」とのことだが、残念、我が家に塩はない。なくてもうまい。
さて、今日期限のレポートは2つある。1つはボールペン書きかパソコンでの作成を強制されている。昨日書いた理由によりボールペン書きはしたくないため、TeXを書く。
先週まで2ヵ月近くずっと射影空間の話をしていたのに、急に意識を取り戻したみたいな問題が出される。途中でatgolferを確認すると、Vim
でいくつか縮められているのを発見し、動悸が激しくなった。Vim
は全然勝てない。ギリギリ1つ取り返して一矢報いた気分になり、レポートに戻る。
まだ1つ目にしか手を付けていないが、2つ目は前評判的に難しそうだし、期限に遅れても全く受け取ってくれないというわけではないので、あまり気にしないことにする。逆にTeXで書いているやつは期限に遅れると即座にアウト。コワイ。
結局23時くらいに書き終わった。2つ目を読もうとしてうっかりatgolferを確認している間に日付が変わってしまう。コードは縮まない。
問題を読んでみると全然わからないので、すっぱりあきらめることにする。これまで毎回提出してきたし、1回くらいええやろ!の精神。ちなみに月曜日から無視し続けているレポートの科目は半分くらい提出していない。困った。
特に何も用事がなくなったので(あるが)、コードゴルフ配信をする。4時間弱でABC091-ABC100を確認した。1つ取り上げて解説する。
sum(A,B,C)+max(A,B,C)*(2^K-1)
。sum
とmax
を同時に計算する方法として理想的であると感じられる。
まず[rSAdx]dx
について。これはマクロをスタックの2番目に送りながら1番目をレジスタA
に保存し続け、最後、メインのレジスタに何もなくなったとき、マクロ自体をレジスタA
に保存して止まる。
この、マクロを別のレジスタに保存せず、スタックの中での位置をうまく制御してループを自在に継続・停止する技法が面白いし、短い。ちなみに、rSA
というシンプルな命令でなくとも、うまくr
やR
を配置することでもっと複雑なことができる。うっかりするとすぐ無限ループに入るため、コードテストでは毎回10秒無の時間を過ごしている。
ループから復帰する過程で、dlA>ALAK+k
が行われる。レジスタとこの復帰する過程を組み合わせることで、スタックの底から順に要素を舐めることができる。逆に、この方法でなければzR
で毎回引っ張ってくることになって、効率的にはできない。
まずdlA>A
。これは月曜日にも登場したが、max
を計算する最も一般的なコード片だ。ちなみにループの最初は1つも要素が積まれていないため、比較しようにもできず、lA
がそのまま取り残される。これは望ましい挙動だ。次にLAK+k
は、レジスタA
から値をpop
して、精度を表す変数に加算している。このpop
によってレジスタA
の次の要素にアクセスできるようになる。
ループから抜けると、スタックのトップにはmax
が保存されており、K
はsum
となっている。sum
がINT_MAX
を超えるとエラーを吐いて加算されなくなってしまうため、そのような場合は当然別のレジスタを用意して、そこを書き換えるとよい。
07/24(金)
午後7時に起きる。今日は8時からSRMがあるが、もう一度寝ようか迷いながらatgolferを確認すると、ちょうど数分前に新手が出ている。適用できるコードを1つ思い出せたのでとりあえずスマホで縮め、そのあとさらに確認するためにPCの前に座る。
ちなみに、新手とはこれのことだ:
ループ内で入力を読むことで、最初の引き算が行われず、1
がスタックの底に残る。これは、以前のコードではわざわざ別のところで積んでいたものだが、まとめることができて縮んだ。
この問題はn==0
のケースがある。このときはそもそもループに入りたくない。しかしその場合分けは長いため、以前のコードでは事前に1足したりして補正を頑張っていた。ここもうまく解決されている。
というわけで起きぬけにコードゴルフを頑張っていると、SRMの時間になる。今回はsquareさんがwriter。
Medで優れた直観が働き、2完最速になった。Hardは高度典型らしいが、LPなる言葉は聞くだに難しい。
今日はこのあとこどふぉもある。コードゴルフしながら時間を待つ。
CでWAを生やす。とりあえず順位表を確認すると、なんと誰も通していない。一気にやる気を失ってツイッターを始める。しばらくぼんやりしているとEが解かれだしたので、見てみる。一瞬解けそうになったが錯覚で、全然わからない。放り出してハーメルンを読む。DのAC数も増えてきた。読んで適当にエスパーする。あんまり時間がないので、とりあえず書いて投げることにすると、通る。
結果、ABDでhighestを更新した。
カスみたいな取り組み姿勢のわりには今日は調子が良かったらしい。そもそも典型とエスパーしかしていないのに調子も何もない、という話かもしれない。
急にゴミ出しをしたくなったので、生ごみをまとめたりシンクの排水口から食べ物の残骸を取り除いたり風呂場の排水溝から髪の毛を取り除いたりして、準備をする。ゴミ袋の口を縛ってさあ後は捨てるだけだ、となったところで、ごみ収集は昨日だったことに思い至る。ひどい徒労感に苛まれた。
午前4時ごろにホスフィンが家に来る。お互いレポートとコードゴルフにしばらく取り組んだあと、飲酒をした。
ホスフィンは始発を待って帰っていった。さらにコードゴルフを進める。今日はRated企業コンの昔のほうから順に確認していた。
07/25(土)
午後7時55分に起きる。8時からコンテストだと勘違いして一気に目が覚めて、洗面台に走りこんで顔を洗っている最中、自分が開始時間を1時間間違えていることに気づく。
atgolferを確認するといくつか更新されていたので、確認しつつ待つことにする。1つ取り上げる。
昨日縮めたやつが更新されていた。Vim
の知らない機能がいくつか盛り込まれていて勉強になる。たまたまさらに縮むところを見つけたため、上にはそれを反映したものを貼った。
これまでVim
のレジスタはいつも""
しか使っていなかったのだが、少し前に、"1.."9
を使うことで縮むコードが登場した。またそこでは"=
も使われていた。
上のコードでは"-
と".
が登場している。"-
は範囲が1行以下のコマンドで削除したテキストが入るが、これは削除のあと別の内容をヤンクしても中身が変わらない。".
は挿入したテキストを保存しているが、その使い方にはなるほどと唸らされた。q
でマクロを定義する代わりに、挿入コマンドで直接書き込んでいるのだ。この問題では、途中で全体の半分を一気にr#
するのだが、その前にテキストを書き換えても行の長ささえ同じなら影響がないことを利用している。R
コマンドで置換することにすれば、行の長さを変えずに所望のテキストを挿入することができて、これが".
で参照できるようになる。
あとはCtrl-F
でページスクロールするのも自分では思いつかなかったものだ。L
を使うと移動の幅が足りず、かといって複数回実行しても結果が変わらないため、しかたなく49j
とかしていた。
M-SOLUTIONS プロコンオープン 2020はEがなかなか難しかった。前計算など頑張ってO(2N N3)で解いたところ、コンテスト終了時点でのfastestだった。
コードゴルフもそこそこうまくいって、これを書いている時点ではABCDの4問で最短コードを保持している。
さて、昨日からFHCのQualification Roundが始まっている。2年くらい前まではGCJもoutputファイルを提出する形式だったと覚えているが、これは結構精神にストレスがかかる。入力をダウンロードしてから6分というのは怖い。例えば、突然パソコンが爆発したらどうなるだろう?まあさすがにそんなことは考えていないが、ダウンロードしてからの操作には結構注意を払う。
考えるのが面倒になったので全部は解かずに辞めた。qualでは1問通ればよいので、さすがに落ちるわけがない。
本を1冊読んだ。ここ数か月全然読めていないのに、読書冊数の目標ばかりバカデカいため、絶望的。冊数を目標に設定するのはよくないという話を聞くが、これには同意せざるを得ない。
さらにコードゴルフを進める。今日も企業コンを下からやっていく。Crystal
で取った最短コードがいくつかあるが、これは大体Ruby
がTLE
してしまうからだ。Ruby
が通るならば、基本的にそちらのほうが短い。以前はCrystal
にのみArray#sum
が存在したので、そこが強みと言えないこともなかったが、言語アップデートでその差もなくなった。
ということで、Crystal
のコードを全て確認しておく。いくつかRuby
でもTLE
しないようになっていたので、適当に縮めた。
07/26(日)
22時半に起きる。意味不明。今日はコンテストがないためこういうことができてしまう。
とりあえず今日期限のレポートがあるので、適当に錬成する。インターネットのページをチラチラ見ながら書いたのだが、参照していたページが謎にグラフィカルで、ページ遷移のたびにアニメーションが挟まれてキレそうになる。
yukicoderに問題がたくさん生えている。よく見たら前にHackerRankで参加したコンテストらしい。大教室での講義中だったのだが、いそいそとノーパソを開いてタイプ音に神経をとがらせながらコーディングしたことを思い出す。
最後の問題はOEISで解いたことを覚えていた。もう一回書くのが嫌だったのでこれだけコピペして提出。制約が変わっていて、1回REを生やした。
問題名が逆ポーランド記法で、実際に逆ポーランド記法を実装しなさいという問題。ところでdc
は逆ポーランド記法の言語で、入力を1行読むコマンド?
は実際にはeval
しているため、これで通る。
さて、月曜日に無視してしまったレポートだが、結局提出していない。それどころか同じ演習の今週の課題も手付かず。評価基準が説明されたので確認すると、解いた問題数に各問題の基礎・標準・応用の難易度分け(公開情報)で重みづけされた値によって成績が決まるらしい。過去の問題のレポートも受け付けてくれるようだ。これまで出た演習の問題をカウントして僕の評点を確認すると、なんと3分の1くらいしかない。これまでの10回のうち半分、つまり5回提出してあるのだが、これがちょうど問題数の少ない回だったようだ。涙が止まらない。
仕方がないので、古いやつから解いていくことにする。とりあえず1回分終わらせたところでもう朝になってしまった。
途中で本を1冊読んだ。創元推理文庫「タルト・タタンの夢」で流し読み気味だが面白かった。シリーズもので続編があるらしく、把握していなかったので、とりあえず古本サイトで探してお気に入りに登録しておく。今度古本を注文する機会があれば一緒に買うだろう。
実は次の木曜日は今学期唯一の期末テストがある。しかも午前中。これに出席するためには、生活リズムを前にずらすか後ろにずらすかしなければならないのだが、前にずらすことを選択する。頑張っていきたい。
結局今日はコードゴルフほとんどできず。「あなたがコードゴルフ以外のことをしている間に、ライバルはコードゴルフをしています」になってしまった。