07/27(月)
まだ学食が開いている時間に起きることに成功する。シャワーを浴びて外を見ると雨が降っており、かなり行く気を失ってしまうが、頑張って外に出る。
帰ってきてしばらくコードゴルフをする。Python
で縮められているので、もっと短い(であろう)言語で書くか放っておくか迷う。迷っている間にさらにPython
で縮められたので、とりあえず1つRuby
で書くことにする。……TLE
した。仕方ないのでCrystal
を持ち出す。
Crystal
はRuby
っぽいコンパイル型言語だ。しかしPython
とPyPy
みたいにほとんど同じコードが動くなんてことはなく、いろいろ違う。
手元に環境がないし、ググラビリティも低い。旧ジャッジでは、AtCoderのコードテストでコンパイルエラーが表示されなかったため、仕方なく次のサイトで試行錯誤していた。
こちらは入力を設定できない。なので、コンパイルできるコードが書けたらAtCoderのコードテストに移ってさらに試行錯誤を重ねる……みたいなことをしていた。言語アップデートでコンパイルエラーが表示されるようになっていて嬉しい。コードに関しては、Crystal
の経験値は絶対的に少ないため、まだいくらでも縮みそうな感じはする。
そもそも解法が面倒なので、こういうのをゴルフしようとしたら方針をたくさん立てていろいろ書かなければならない。常套手段として、しばらく放置しておいてある程度他の人の短いコードが溜まった段階で、いくつかよさげなのを読んで方針を決定する方法がある。しかし先ほど述べた理由によりそもそも試行錯誤が面倒なので、すっぱり辞める。
明日期限のレポートを書く。10題あって1~3題選んで解くやつ。問題の難易度に明らかな差があって、誰かが先生に配点の違いがあるかなど聞いたらしいが、ないとのこと。僕はこの科目の何をもわかっていないため、その事実は歓迎できる。しかし逆に、自信のある科目だったとしたら、こういうあまり人と差をつけられないような評価形式だとちょっとつまらなく思いそうなので、結局ただのポジショントーク。
実際、解けない。そうこうしている間に今日も本を1冊読んだ。乙一「夏と花火と私の死体」。この作家は結構好みで、一応集めてはいたが、ホラーということで積んだままあまり手が出ていなかった。読んでみると妖怪・お化けの類の怖さではなくて、楽しめる。読了ツイートをしたら、FFの方からいくつか同じ作家の作品を薦められた。そのうち未読のものとして、「暗黒童話」を読み始める。こちらも積んであった。少し読んだところで切り上げて、明日以降に回すことにした。
水曜日提出の、ノート1ページ作る課題もやった。こちらは今回、講義スライドに論理回路に関する問いがいくつか置かれていて、それに答えていれば1ページ自然と埋められる親切設計。
さて、FHCが終了した。結果としてはD2以外出して全部通った。D2もパスからの距離を考えるとD1と同じDPに落ちるらしい。部分木ではあまり動かないことはわかっていたが、そこから先を考えるのがどうしても面倒だった。Qualは通ったのでヨシ。
明日はごみ収集の日。先週土曜日から口を縛って放ってあったごみ袋を、ようやく出すことができる。前日深夜に出すことにすると生活習慣崩壊者でもゴミ出しができる。
水曜日提出の課題を始めるが、問いがあやふやでよくわからない。しばらくうだうだした挙句、諦めてコードゴルフを始める。またRated企業コン。そろそろ今年のコンテストに入りそう。
07/28(火)
起きたら午後9時だった。頭おかしい。期末受ける気あるのか?この週の日記が公開される頃には当然期末が終了しているため、結果をお楽しみに!
実際、午後3時くらいに目覚ましで起きてしばらくゴロゴロしていた記憶はある。雨が降っていたため学食に行く気を失い、寝てしまったことを覚えている。
明日期限のレポートを書く。結構な時間をかけて、1つ終わる。もう午前3時なんだが?(致命傷)あと1つは昨日からやってるやつだが、いまだによくわからない。放り出してコードゴルフをする。
3時間くらいやって、やっとRated企業コンが全部終わった。言語アップデートがあってから未確認の問題は山のようにある。今日も1つ取り上げよう。
A==1
またはB==1
のとき1
を、そうでないときはceil(A*B/2)
を出力する。この場合分けがうまく書けた。
1 ans
と積んでおいて、A
でR
したあとB
でR
する。1
でR
すると位置が変わらず、それ以外はswap
されるため、A
とB
の片方だけが1
のときはswap
された状態に、両方1
でない・または両方1
のときは元の状態に、それぞれなる。A==B==1
のときはans==1
となるため、結局スタックのtop
を出力すればよい。こういう場合分けは他にもあったような気がしてならないが、探す気力があんまりない。
ceil(*/2)
について、これは2~+
という書き方が最も短い。僕にとってはかなり非自明に見える。ちなみにceil(A/B)
の一般的な書き方は、(A-1)/B+1
だったり(A+B-1)/B
だったりするだろう。前者が常に短いと思っていたのだが、後者の書き方でいくつか最短を取られたことがある。どういう条件のときに後者が短くなるかあまりよく覚えていないが、それ以来両方試すようにしている。
0^*
でiszero(*)
ができることを利用して、A B
の状態から~0r^-1+
みたいな書き方もできないことはないが、これは明らかに長い。……と思っていたが、よく見るとr1-r/1+
と同じ長さだった。びっくり。
今日は読書していない。そのくせまた日が昇ってから寝ようとしている。まずいぞ。
07/29(水)
正午の目覚ましとともに起床、重力を振り切って身を起こす。偉すぎる。近代史に名前残しちゃった。
眠気覚ましにatgolferを確認すると、昨日上に得意げに解説を書いたやつが縮められている。
ハァ~~~~~~~~~辞めたら?コードゴルフ。これ見た瞬間巨大な感情に襲われて身動きができなくなってしまった。
何とか体を起こし、ほかに縮められていたやつを考えながら学食に向かう。帰る途中にスマホで縮め返した。
頑張って早起きしたため、正直眠くてつらい。うつらうつらとコードゴルフをする。今日はPASTを全部見る……と思っていたが、PASTは第2回から新ジャッジで行われているため、そんな自明に縮むものはない。
こんなRuby
コードがあった。
$x
というのはRuby
のグローバル変数だ。ループの中でこれに答えを代入して、外で参照している。普通の変数と違って最初の宣言がなくてもループの外から見えるため、短い。あと$
のおかげでスペースが削れたりする。
さて、これは定数でも同じことができる。定数は$
がいらないため1B
縮むが、毎回の代入の時に警告が出たりしてかなり遅い。実際この問題はここで定数を使うとTLE
になる……と思ったら通ってしまった。実行時間もあまり変わってないので、ボトルネックがそこではなかったということだろう。
この問題のことはさておき、実際に定数への代入より速くて+1B
で書けることは確かだ。この事実を用いて縮むコードを探す。Ruby
の言語内最短コードを全部読む気力はさすがにないため、全体でも最短のRuby
コードを、ABC
・ARC
・AGC
に絞って読む。結局見つからなかったが、読んでいく過程でいくつか普通に縮んだ。
レポートを書く。月曜から手を付けてはいたものの、全然進んでいなかったものだ。かなり難しく感じる。自分が正しいことを書いているのかよくわからない。環にいろいろ性質が設定されると、まるで整数であるかのように扱えてしまうため、うっかりやってはいけないことをやってしまいそう。
ちっとも進まないので、この演習を担当する先生のWebページを見ると、下のほうに評価基準が書いてあるのを見つけた。読んでみると、「グループ用問題」という種類の問題を解いて加点されるのは1回につき3題までらしい。僕は書けば書くほど点が来ると思って、できるだけ全部解いていたのだが、これは実のところ結構な量が点になっていないようだ。この演習は結構頑張っているため、自分が思っていたより人と差をつけられていないことを確認するとちょっと落ち込んでしまう。月曜日に書いていたことが実際に起こっている。
何とか終わらせたころには日付が変わりそうになっていた。こどふぉがあるが、出ずに別の課題に手を付ける。明日期末テストなので、それに対応する演習の課題を解いておこうと思う。
半分だけやったところでもう午前3時。明日は午前10時30分から期末テストなので、さすがにまずい。最近はうっかりするとすぐ12時間眠ってすべてを破壊してしまうので、明日はちゃんと頑張りたい。もう寝る。
07/30(木)
午前9時、目覚ましによる起床に成功する。対戦ありがとうございました(天下無双)
atgolferを確認すると4つくらい取られている。スマホで縮め返すが、全部は取り返せない。
これは夜に取り返したやつなのだが、話題が散らばるのでここに書く。取られたので-1B
で取り返したら-3B
でさらに取られたので絶望していたところ、何とか-1B
できたという形。
z
が3,2,1
で、それぞれ32,32,10
にマッピングしたい。これはz2/22*A+
で書かれていた。いろいろ試行錯誤すると、まず2
を積んでからz
で割ったあまりを求めたとき、スタックに2
が積まれていることによりz
がそれぞれ4,3,2
になるので、2,2,0
となる。これに11
を掛けて10
を足せばよいが、11
も10
も1B
で書けるので縮む。2z%B*A+
だ。これ気づいたとき思わず指パッチンした。イキリオタクか?
先週書いていたのだが、max(a,b)=a+max(b-a,0)
はスタックにゴミを残さないのが偉くて、毎回0k
による初期化みたいなのを行うコストを考えても縮むらしい。多分改めて探せばもっとあるんだろうけど、今は課題で手一杯なんじゃ……厳しい。確実に縮むだろう更新点を把握しておきながらコードゴルフできないのは本当にストレスになる。
昨日の夜にCrassroomから講義資料を一気にダウンロードしたら、ファイル読み込みが終わらなくなってしまった。このままでは期末が受けられない。最初はノーパソを取り出してそちらで見ようかとも思ったのだが、Edgeで開くといけた(あとからChromeを再起動したら普通に動いた)。さて、期末テストだ。
……驚くほど解けなかった。あと計算量がヤバすぎる。ヤバい(語彙力喪失)対戦ありがとうございました(意気消沈)
生協に行って、昨日出版された森見登美彦の新作を探す。ないのでインターネットで注文する。
学食に行くと、数学科の友人と久しぶりに会う。期末テストの話になる。聞くところによると、計算量がヤバかったのは座標近傍の取り方が悪いとのこと。ハ~~~~~……。ほかにも多様体の話をいろいろ聞く。学食が閉まった後も道路で立ち話をしていた。3時間くらい!
帰ってきて、レポートを書く。昨日はヤバい座標近傍をとってしまい6次式が出てきたのだが、改めてヤバくない座標近傍を取ると計算がスイスイ進む。特に問題なく終了。
さて、今日はサークルでオンラインの解説会がある。解説役は毎回立候補制なのだが、今日は誰も立候補していない。何もないのはまずいので、かなり適当にスライドを用意して発表できるようにしておく。午後8時から開始。
ほんでーかれこれまぁ2時間くらい、えー待ったんですけども、参加者は、誰一人、来ませんでした。ガチャ。
嘘です。二人来ました。片方はサークルに入部したばかりの人なので解説会には参加できず、もう一人は十分強いし、それでなくとも一対一で解説会ってなんやねんという話なので、今日は終わりにする。
明日提出のレポートがある。演習ではなくて普通に講義の課題なので、ちゃんと出す必要がある。が、問題を読んでみると、解けない!ものの見事に何一つわからない。本当につらい。
なろうを読んだ。今日はもう寝る。明日の自分が頑張ってくれ。
07/31(金)
疲れているはずなのに午前9時くらいに目を覚ましてしまい、そのまま二度寝できず布団の上で数時間をドブに捨てる。実際にはレポート問題を考えていて、1つ解けたので興奮して寝れなかったというのもある。
あきらめて起き、レポートを書く。1題ぶん書いて学食に行く。生協のほうを覗いたら森見登美彦の新作が置いてあったが、すでに注文してしまったので泣く泣くその場を立ち去った。
家に帰ってきて、レポートが嫌になったのでコードゴルフを始める。昨日言っていたように、dc
は更新点がまだたくさんあることが予想されるので、それを探すことにする。途中、超自明な更新を逃して放心状態になったりしていた。4時間くらいやっていたら午後6時になったので、さすがに危機感を覚えてレポートに再度取り組む。
かなり頑張って、やっとのことで少しずつ問題を解いていく。実際正しいことを書いているかはあやふやだが、書かないよりはマシ。yukicoderに出るのをあきらめてさらに解き続ける。留数定理を使おうとして、留数が計算できずに止まっていた積分の問題があったのだが、天啓を得て解けた。少なくとも、僕の経験からすればこれは天啓。
結局1問どうしても解けなかったので、あきらめが肝心ということでそのまま提出。単位は守られた、はず。さらにコードゴルフを進める。
今日はあまり面白いコードを書かなかったと思ったが、まあ毎日やってきたことだし今日も一つ取り上げよう。
W>=2
という制約なので、必ずo
に保存できる。出力の際にAo
と+2B
かけて戻さなければならないのだが、このコードではsWlWlW
と3回使っていたので、それをoOO
にすることで-3B
。結局-1B
の更新が可能になる。
こういうのも縮むポイントだろう。制約で2以上の変数だけではなく、例えばmod
を保存して縮んだコードを書いたこともあるし、制約上許されていてもたまたま1のものがテストケースになかったりするのは、問題文を読んでいるだけではわからない。実際にいろいろ提出してみて探さなければならない。
08/01(土)
昼前に起きてしまい、眠れない。睡眠負債めちゃめちゃたまってる感覚がある。どこかで死ぬほど寝そうでこわい。学食に行く。
今日期限の課題はないので、コードゴルフをする。配信でABC101~ABC125の全問題をチェックする。これは6時間くらいかかった。これまでちょこちょこ配信してきたが、6回でABC001~ABC125の全問題をチェックしたので、以降の令和ABCは配信しないことにして、完結という感を出す。
配信は終わったが、コードゴルフはまだまだ続く。とりあえずTCOにレジろうとArenaを起動したところ、Javaの更新があって、その結果一時的にログインできなくなった。かなりビビる。コンテスト開始1時間くらい前にもう一回チャレンジしてみるとちゃんとログインできた。謎。ちなみにこの間もずっとコードゴルフをしていた。
さて、TCO R3Aだ。1完。1問目によくわからない問題が出て、2問目は天才パズルみを感じる。Hackフェーズから部屋の提出がぼこぼこ落ちていて非常に怖いが、何とかシステスが通る。システスでどんどん落ちて行って順位表が上にスライドしていくのが面白かった。
順位的にはカスなんだけど、超強い人が太陽キメていたりとかなり荒れ模様の順位表で、+26
して赤復帰。そう……という感想しかない。
終わった後もずっとコードゴルフをする。結局今日は12時間くらいやっていた。全体的にあんまり縮んだ気はしないが、最後に1つ良いコードが書けたので、取り上げる。
これは新言語で提出されており、-1B
ぶんアップデートで可能になった縮め方がされているものの、もう-1B
は旧ジャッジでもAC可能なコードである。つまり、2年くらいの間、見逃され続けていた更新ということ。
ABC-AはQiitaに網羅記事を書いたりして、結構な回数人の目に触れてきたはずなので、今更(言語アップデート以外の理由で)縮むのはびっくり。さらにこの問題の以前の最短コードについては、僕自身あまりにもそのまんまなコードを見てさすがにもうちょっとどうにかならないのかと思い続けてきたので、実際に縮んでうれしい。
基本的には、get.comb
で1行目を文字ごとに分解して、所望のインデックスでアクセスすることによって配列の形で文字を取り出し、出力する。配列をそのまま出力すると間にスペースが入ったりするので、|
でflatten
みたいなことをしている。配列を分解して関数の引数にする感じだ。
所望のインデックスを得るのに、これまでは入力を読んでそれぞれ演算していた。冗長に感じていたのだが、実は(0..4 X 0..4)
という直積の配列のN番目に相当する。0..4
が^5
と書けることを利用すると元の最短コードより短くなって-1B
。さらに言語のバージョンアップによって、^5 X ^5
のうち最初の(つまり左側の)^5
が無限リストになっていてもかまわず、それが^*
と書けることから、(^*X ^5)
になる。この場合5
とX
の間に必要だったスペースが削れてさらに-1B
。合計-2B
となる。
08/02(日)
午後4時半に起きる。そのまま2時間くらいベッドの上でゴロゴロし続ける。最短がいくつか取られているので、起きる。
そのままゴルフしているとABCが始まった。A問題はperl
の素直なコードが最短だが、気づくのが遅すぎる。さらにC問題はAWK
が短いらしいが、これもdc
で解いて満足してしまい気づけず。言語アップデートで新しく追加された言語にうつつを抜かしており、本質的なコードゴルフ力としてはむしろ弱くなっていそう。まず知ってる言語全部試せ。
今日期限のレポートがある。月曜日の講義で、毎週ワード1ページの課題が出される。これが最終回だ。数学の講義ではないため、レポートの評点がよくわからないやつ。結局今回は3問のうち1問書かずに出してしまったが、さすがに毎回出してるし単位は来るだろう。
東北大学の全学教育(東北大学 全学教育ホームページ Tohoku University General Education)について。特に基幹科目という講義群では、講義ごとにテーマがあり、それに沿って教授が基礎的な話をするのだが、開講されている講義のテーマには毎年毎年ことごとく興味を持てなかった。しかもこの講義は大体、毎週のミニットペーパーの提出が評価に入るため、出席する必要がある。さらに毎期の時間割において開講されるコマは2つ設定されているが、必ずどちらかが1限になっている。以上のことが重なり、3コマぶんの単位を取得しなければならないところ、僕はこれまで6コマ受講して2コマぶんしか単位を取れていない。今日出したレポートはこの基幹科目のものだ。今度こそ単位を得て基幹科目から解放されたい。
コードゴルフに戻る。今日はたくさん取られているので、それぞれについて取り返すか諦めるかするまで延々考え続けるやつをすると、新しい問題をゴルフすることができない。悲しいね。
今日は2つ取り上げよう。
この問題はQiitaに記事を書いている(AtCoder Beginner ContestのB問題の最短コードを読む(001-020) - Qiita)ので、基本的な解法はそちらを参照されたい。
Qiitaで記事を書いた当時の最短コードは、floor
とceil
が入り混じっているのを無理やり解決しているため、ちょっと美しくない。ここがdc
でうまく書けた。具体的には、floor(double-int)
においてdouble
は切り下げられるが、floor(int-double)
にすると切り上げられる。ただしfloor
の中が非負であるとした。この問題は制約が微妙で、結局70000
と70001
が区別できればOKという感じ。floor(70000/5000-14)=floor(70001/5000-14)=0
だが、floor(15-70000/5000)=1>0=floor(15-70001/5000)
ということ。ただこのままだと1/100
が切り上げられて困ったことになるので、r
を1つ追加してちょっと調整した。
Vim
からも1つ。
これはかなり偶然の産物。#
が単独で実行されると、上方向への検索が失敗した結果最終行まで飛んでいくので1コマンド削れた。本来は}
で移動していたのだが、うっかり入れ忘れて提出したところ通ったので、発覚した。
さらに、数値をレジスタに格納するときに空白が混入するのだが、これも必要だった。#
で検索する対象はカーソル直下の単語だが、空白を実行してカーソルを1文字ずらさなければ、それまでに編集していた文字列を検索しようとしてしまい、移動できない。