05/24(月)

先週の週記を投稿してから寝るまでの話。

サークルの継続関係の作業を一気に終わらせることにした。大学に提出する書類自体は昨年度も同様のフォーマットで作成したのでそちらから引き写してくれば済む。今年は去年のものがさらに洗練されており、スプレッドシート1つにすべての書類がまとまっていて、同じ内容を1回記入すると、別の欄にも自動で反映されるようになっていた。かなり便利だった。

問題は、サークル活動に使用しているサービスのアカウントの整理で、具体的にはGoogle DriveとSlackからすでに在籍していない人のアカウントを解除する作業があった。できるだけ余計な情報を入手しないという思想の元、サークルメンバーのメールアドレスは入部届にしか書いてもらっていないため、過去数年分の入部届の記録をひっくり返して誰がどのアカウントの持ち主か特定する作業に邁進した。とはいえ、ほとんどのアカウントは本名が表示名になっているので、思っていたよりはすんなりチェックできた。最後に対応が取れなかったアカウントが数個残ったので、しばらくSlackで持ち主を探してみて、現れないようであればこれも解除する。

「レーゼンシア帝国繁栄紀」を読んだ。古本を大量に買ったときの1冊。設定は良さそうだったが、内容はあまり面白くなかった。ひょんなことから帝国皇帝に成りすまして政務を執ることになった主人公が、知識と持ち前の機転を活かして活躍する話。ラストシーンはラノベ冒頭のカラーイラストにもなっていて、それを見る限りは騎士団を鼓舞する勇猛な主人公、という感じだったので楽しみにしていた。しかし本編を読んでみると、別に何かの合戦というわけでもなく、帝都の公園で一騒動巻き起こすために嘘の演説を行うというシーンだったらしく、かなりがっかりした。

布団に入ってから、先週の週記にTCB36のことを書くのをすっかり忘れていたことに気づいた。日付としては05/21(金)、日記を書いてから真夜中に参加したもので、入力の受け取りミスで理論値を逃してしまった。長方形領域の与えられ方が、A B C Dで「左下の点(A,B)と右上の点(C,D)」を表すと思い込んでいたが、実際は「A<=x<=BかつC<=y<=Dなる点」の意味だったらしい。それ以外問題に関しては何も覚えていない。30分くらいで全完した（負け惜しみ）。

布団で少しなろうを読んで、午前11時半就寝。寝る直前に、今日の典型90問のコードを書いて、問題が追加されたら自動で提出されるように設定しておいた。

午後6時くらいに目を覚ました。典型90問の問題自体は追加されているものの、コードが提出されていない。パソコンがスリープしてしまっていたようだ。失敗。とりあえず再度出しなおした。これはRubyのコードだったが、Perlで書いてみるとさらに縮んだ。Rakuではもっと縮むはずだったが、実際にはTLEしてしまったので、現在はPerlのコードが最短となっている。

そのあと布団に戻ってちょっとうつらうつらしたりなろうを読んだりしていたが、本格的に寝ることはできず、午後9時半になってしぶしぶ起きた。食事してシャワーを浴び、1月前のサークルバチャのupsolveをしたが、出したコードが落ちてしまった。もうすぐこどふぉのコンテストが始まるので、放置して参加した。

この回のD問題は解説自体もかなり難しかったが、理解は済ませている。残りは書くだけなので、そのうちupsolveしたい。
週記（2021/05/10-2021/05/16） - kotatsugameの日記

CF #722 div.1。4完51位でレートは2821→2839(+18)、highest。

https://codeforces.com/contest/1528

Aは簡単。直感的には、木を2部グラフと見て、それぞれ最大値を取る点と最小値を取る点に分けることが思い浮かぶが、簡単な反例が構築できた。[0,1]-[1,1]-[1,2]。冷静になると木DPでよい。

Bはちょっと怯むが、しばらく実験してみると、外側に同じ長さのペアをたくさん重ねてより小さい値の通り数に帰着するか、全てを同じ長さのペアで埋めるしかない。具体的には、 $f(N)$ が $N$ に対する問題の答えだとすれば、 $f(N)=d(N)+\sum_{i=1}^{N-1}f(i)$ 。ここで $d(N)$ は $N$ の約数の個数を表す。

Cは、Soroushの木を元に考えれば、求めるクリークの頂点は全てSoroushの木における根からある頂点へのパスに乗る。よってSoroushの木でdfsをし、そのパスを全探索する。パスを1つ固定すると、Keshiの木に関する条件は、選んだ頂点たちが互いに親子関係にないということだから、Keshiの木において深いところにある頂点から貪欲に取ってよさそう。実際には毎回パスの頂点を全部見るわけにはいかないので、暫定的に頂点を選んでおいて、より深い場所に頂点があったらそれに入れ替えるということをすることになる。ある頂点が別の選んだ頂点の部分木であるか、またある頂点の部分木に別の選んだ頂点が含まれるか、ということは、Keshiの木でオイラーツアーした列を区間setの遅延セグメント木に乗せれば判定できる。さらに、今見ている頂点が選んだ頂点のうちどれの部分木に含まれているかという情報も、区間setの値を頂点番号にすることで得られる。

Dは、dijkstraの頂点に到達時刻 $\bmod{N}$ の値の情報も持たせたくなるが、ちょっと考えるとできる限り早く着いてから待つのが最適であることがわかる。よって頂点数 $N$ 、辺数 $N^2$ のdijkstraを $N$ 回行う問題に落ちる。最も内側のループで $N$ による剰余演算が行われるとかなりパフォーマンスに影響するらしく、僕は何となく安全側に倒してif文を書いていたのでpriority_queueのlogをつけても900msくらいだったが、そうでなければ $O(N^2)$ のdijkstraをした人でも2000msを超えたりしていて、かなり怖い。

Eに1時間くらいかけたが、解けなかった。そのままコンテスト終了。

「レーゼンシア帝国繁栄紀」の2巻を読んだ。ここで打ち切りらしい。相変わらずあまり面白くなかった。伏線回収とはいえ、行き過ぎて主人公が最初から全部わかっていたという結論になってしまい、主人公視点で綴られてきた話との印象が合わない。しかし、こう言語化すると、よくある話のように思えるから、この作品が面白く感じられなかった理由としては弱そう。結局打ち切りだということをわかって読んでいるのが一番ダメだった。同様のことを以前の週記でも言及したなと思い探したところ、案の定あった。人はそう簡単に変わらない。

「打ち切りになってしまった」という情報を念頭に作品を読んでもあまり楽しめないということに気づいた。
週記（2020/11/23-2020/11/29） - kotatsugameの日記

E問題の $n=3$ における答えを教えてもらい、しばらく格闘していたら、解けた。コンテスト中の考察には間違いがなく、数え上げのミスだった。解法をここに書こうとしたが、さすがにちょっと長すぎたため個別に記事を立てた。

kotatsugame.hatenablog.com

コンテスト中のコードは、上の場合分けのうち最後のケースの計算が誤っていたようだった。

コンテスト直前に解いて落ちてしまっていた提出を修正し、通した。

https://codeforces.com/contest/1019/submission/117265532

これもかなり難しい。与えられた点から3点選んで三角形の面積が $S$ になるような組を探せ、という問題で、解法は2点決め打って3点目を探索。この探索が非常に頭が良い。決め打った2点 $P_i$ と $P_j$ の法線ベクトルとして $P_j-P_i$ を反時計回りに90度回転したもの $\overrightarrow{n_{i,j}}$ を考えると、三角形の面積は、その法線ベクトルと3点目の位置ベクトルの内積について1次関数の関係にあるらしい。頑張って計算すると分かったが、かなりびっくりな性質。

計算についても一応書いておく。 $a(\vec{a})=P_i$ 、 $b(\vec{b})=P_j$ 、 $c(\vec{c})$ の3点によって作られる三角形の（符号付き）面積を求める。 $\vec{n}=\overrightarrow{n_{i,j}}$ とおく。点 $c$ から直線 $ab$ に下ろした垂線の（符号付き？）長さを $h$ とすると、 $t$ を変数として $\vec{c}-h\cdot\vec{n}=t(\vec{b}-\vec{a})+\vec{a}$ が成り立つ。両辺に $\vec{n}$ を内積として掛けると $\vec{c}\cdot\vec{n}-h|\vec{n}|^2=\vec{a}\cdot\vec{n}$ 。よって $h=\frac{(\vec{c}-\vec{a})\cdot\vec{n}}{|\vec{n}|^2}$ 。

よって定数を $k$ や $k'$ としてまとめると $S=\frac 1 2|\vec{b}-\vec{a}|h=k(\vec{c}-\vec{a})\cdot\vec{n}=k\vec{c}\cdot\vec{n}-k'$ と書ける。

従って、点を法線ベクトルとの内積の値によってソートしておけば、二分探索で3点目を探せるようだ。このソートの方法も頭がよい。考えられる法線ベクトルをすべて列挙し、偏角ソートしておく。それを順番に見ていくとき、ある点 $P_i$ と $P_j$ について順番が入れ替わる瞬間というのはこの2点によって作られた法線ベクトルが出現した瞬間に限られるらしい。このことは $\overrightarrow{n_{i,j}}\cdot \overrightarrow{P_i}=\overrightarrow{n_{i,j}}\cdot \overrightarrow{P_j}$ であることと法線ベクトルを偏角ソートしていることからわかる。

日記を書いた。texにおけるvecとoverrightarrowの使い分けが難しい。問題の解説を念入りに書いていたら1日分で5000文字にもなってしまった。マズい。

布団に入ってから新しいなろうに手を出した。午前11時半就寝。

05/25(火)

午後6時半起床。

典型90問が投稿されていたので提出した。問題自体は昨日寝る前に確認していて、ほとんど同じ（に見える）問題が記憶に強く残っていたので、これもすぐわかった。

kotatsugame.hatenablog.com

寝ている間に縮められていた問題と合わせてコードゴルフ。前者は勝てたが後者は負けている。3時間くらいずっとバトルしていた。PerlのUnion-Findで新手らしきものが出た。配列の代わりに${-1}、${-2}……を使用するというもの。それはそう、という感じだが、結構効いた。ほかにもPerlでUFを書いているコードを探して睨んでいた。

atcoder.jp

TCB36は理論値を逃してしまい、10位以内には入れなかったが、代わりに特別賞が当たった。運が良い。僕が初めて参加したTCB31からこれまで毎回賞金・賞品を得られていて、Streakは何とか続いてくれたようだ。

布団に戻って3時間くらいなろうを読んでいたら、先ほど縮めた問題がさらに縮んだと報告された。Vimのコード。慌てて起き上がりパソコンに向かった。削る余地のあるコマンドは少ないように見えるが、Vimのコマンドには1文字のものも多いため、ちょっとの隙が命取りになる。実際、しばらく試行錯誤していたら相手と同じ長さのコードが完成してしまった。非常に悔しいのでさらにごちゃごちゃしていたところ、テストケースハックができて1文字縮んだ。

昔の週記をちょっと読み返していた。当時、自分の裡に激しい感情があったことは覚えているが、もう

寝る前にと思ってメールを確認すると、インターンの面接日程についての話が来ていた。前回1回目の面接の結果、2回目の面接に進ませてもらえるようだ。会社のCEOが出てこられるらしい。特に対策する気もない以上なるようにしかならないので、失礼のないようにだけ心がけておきたい。

布団に戻って昨日寝る前に読み始めたなろうを読んでいた。およそ6時間くらい読み続けていた。非常に面白い。

https://ncode.syosetu.com/n5534co/

午前11時に寝た。

05/26(水)

午後6時半起床。

今日の典型90問を通しておく。かなり簡単だし、あんまり縮まなさそう。実際、すぐに得られる46B解から更新がない。おそらく提出時間の関係で誰かに負けているだろう。

すぐに布団に戻ってなろうを読み続けていたが、今日は皆既月蝕なので、せっかく見えるらしいし見ておこうと思う。下だけジーパンに着替えて、上はパジャマにパーカーという格好。後ろの裾からパジャマの緑色が見えていてなんとも言えないが、まあすぐ戻るだろうと思って出た。

月を探して少し歩くと、道端にぽつぽつ人が立っている道路があった。確かにこの辺りは満月がよく見える。僕が出て行った時間はすでに蝕の最大であり、もしかして月がどこに行ったか分からない！？と思っていたが、全然そんなことはなかった。左上のあたりはいくらか光が当たっていたし、そうでなくとも全体が紅くぼんやりと光っていて、これを見逃すことはあり得ないだろう。

🌒 pic.twitter.com/ufq6tSp9T1
— こたつがめ (@kotatsugame_t) 2021年5月26日

スマホで写真を撮ってみた。4倍くらいにズームして夜空にレンズを向けた。シャッターを切ってから撮影が完了するまで、これはその時々で発される効果音によって判別しているが、が非常に長かった。露光時間が長いことが関係しているのだろうか、それとも撮影自体は一瞬で、光量の補正処理に時間をかけていたのだろうか。びっくりしてかなり手を揺らしてしまったが、写真になってみるとそれほどブレているようには見えない。いや、僕が4倍ズームの影響だと思っているぼやけは、実際にはこの手ブレによるものだったのかも。

写真だと紅さがより感じられるように思える。非常にエモーショナル。レイリー散乱という言葉を初めて聞いたのは、何かのクイズ番組だったと思う。

しばらく見ていると雲に隠れてしまった。蝕の最大を目の当たりにできたのはかなり幸運だったらしい。周りの人たちはそそくさと帰っていったが、僕はしばらく残っていた。せっかくだし月が半分くらい光を取り戻すまで待って地球の影が丸いことを見てやろう、と思っていたのだが、よくよく調べると月が地球の影を脱出するのにはまだ1時間半ほどかかるらしい。そんなには待っていられない。また雲から顔を出した月を最後にもう一度眺め、帰った。

PerlのUnion-Findに、昨日とは別の新手が出ていた。

atcoder.jp

popと$_[0]を使い分けることで、1つの関数でUniteとFindの両方を実現してしまっているらしい。すごいコードであると感じる。ただ、1回Uniteするだけならば直接書いたほうが短い……はず。試していない。PerlのUnion-Findはいろいろ方法があって、local$_を利用してみたり、ちゃんとmy$x=popとしてみたり、どれが短いかは直ちにはわかりにくい。

布団に戻ってまたなろうを読み続ける。途中SRMがあったが、前回のEasyの問題文がひどかったこと、またなろうが面白すぎて読むのが止められないことの2点をもって見送ることにした。しばらくしてSRMを終えた人たちがTLに現れたが、その感想を聞く限り今回はかなりまともだったらしい。

明日は木曜日で、毎週のゼミがあると思い、生活リズムをどうしようか悩んでいたが、先週お休みを言い渡されていたことを思い出した。これで思う存分生活を破壊できる。午前10時まで読んでいた。

途中でTCB34のアマギフ1000円分が届いた。

午前10時、寝落ちした。

05/27(木)

午後4時起床。今日もまた1日の初めに典型90問を通す。今日は半分全列挙で、そうやすやすと短くはならないから、適当にC++で書いておいた。

月曜日にほとんど終わらせていたサークル継続届に関する作業の、最後の詰めを行う。継続届に関する顧問の先生のチェックは、月曜日に書いてすぐ依頼したので既に終了していたが、実際のところは携帯電話番号がまだ不明な人がいる。ひとまず連絡先を持たないということにして、本人に確認を取ろうとしていたが、結局数日たっても音沙汰なしだった。仕方ないのでそのままにして、今日の日付に直した継続届を大学に提出した。次に、誰のものかわかっていないアカウントについて。それぞれSlackでDMを送ったり、アカウント名を公開して身に覚えがあるか問いかけてみたものの、どちらも自分のものであるという人が現れなかったため、これも解除した。これでスッキリ掃除が完了し、現在残っているアカウントはすべて持ち主との対応が取れている。取れているはずだ。

今日の典型がRubyで縮められていたので、自分もやってみる。半分全列挙なのであまり短くなるようには見えない。combinationやbsearch_indexなど、便利なメソッドはたくさんあって、そういうものを利用するのが一番短くなることは試行錯誤の結果わかっているものの、やはり長いメソッド名が気に食わない。あまり縮む余地はなさそうだが、何とかひねりだして現在の最短を持っている。

布団に戻ってなろうを読んでいた。午後7時くらいに何とか学食に行こうとしたが、家を出てみると雨が降っていたので今日は行かないことにした。閉店時間的にもギリギリで、自転車で行くなら間に合うだろうが徒歩だとちょっと厳しいのもあった。

布団に戻ってまたなろうを読んでいると、明日のyukicoderが1時間早まるという情報が流れてきた。こちらの解説会と被る恐れがあるため、前日で申し訳ないが30分早め、午後7時半から行うことを周知した。

PythonのコードがCythonで縮められたので、起き上がってパソコンの前に向かう。Cythonを適用するとわかっていればこちらも同様の変更をすればよく、多少手間取ったはものの取り返せた。Cythonの実行環境が手元にないのがちょっと辛いが、ほとんどPythonと同じでfor文を短縮することにしか使っていないため、まだ何とかなっている。

布団に戻ってなろうを読み続けていたが、午後11時半くらいに寝落ちした。

05/28(金)

午前3時くらいに目を覚ます。この日は午後5時までほとんどずっとなろうを読んでいた。

昨日の典型がさらに縮んでいるらしい。もう全然わからないので、放置。

午前10時くらいには、今日の典型問題を解いて提出するスクリプトを書いた。今日の問題は非常に簡単で、制約もかなり緩い。最初はRakuがよいと考え、そのコードを提出するよう設定していたのだが、しばらくしてからdcで書いたほうがよほど短いことに思い当たる。慌てて書き直した。25Bで、午後2時少し前に無事提出されたようだ。問題なくACでき、全体で2番目のACだし、それ以降縮んだという報告もないので、最短は取れているだろう。

午後5時になって、眠気に耐え切れなくなった。解説会が2時間半後にあるが、かなりどうでもよくなってしまい、自分が起きられなかった時のことをホスフィンに託して寝た。そこから30分おきに目覚ましを設定しており、何とか午後7時に布団から這い出ることに成功した。

寝ていた pic.twitter.com/MLF0GA65SD
— こたつがめ (@kotatsugame_t) 2021年5月28日

解説スライドの用意も何もできていない。幸い今日も熱心なサークルメンバーが2問くらい発表してくれるようなので、最悪それだけでもよいか、と考えていたが、思い直して簡単な問題を1問だけ解説することにした。スライド4ページを適当に書いた。

解説会は、前日に30分前にずれ込んだものの、いつもと変わらない数の参加者が集まってくれてありがたかった。問題なく終了し、そのあとの処理、つまりスライドの公開作業なども終了。ホスフィンには解説会の代理を頼むならもっと早くに連絡してほしいと怒られてしまった。かなり申し訳ない。勝手になろうを読んで生活リズムが限界になっていた。

僕が少しだけ寝ている間に、昨日のCythonのコードがさらに縮んでいたらしい。これはもう全然わからないため、諦めの境地にある。

またもう1つ縮められたコードがあって、そちらはかなり面白かった。いや、自分のコードが縮められているので悔しさのほうが大きいが。

atcoder.jp

odというコマンドを使って、入力をなんらかの数値にマッピングする。これをdcで加工することで望む出力を得る。以前のコードはRubyで同様のこと、つまり入力を適当な数値にして加工する、を行っていた。同様の手法で得られた最短コードは他にもあるが、そちらはどうも縮みそうになかった。

yukicoder 297に参加した。7完。

yukicoder contest 297 - yukicoder

Aはx=0かx=dの場合のみを考えればよい。これを式に起こしてみるとdaとdbだった。意味を考えれば当たり前で、d min(a,b)と書ける。Bはよくわからなかったのでいったん飛ばす。Cはまあ、できる。未証明AC。Dもわからなかったので飛ばした。Eは行列累乗やるだけ。

FはAを降順ソートしてdp[N][M]の動的計画法だろうというのはわかるが、遷移がちょっと難しそう。2個組にして遷移したいが、できない。ここでよく考えると、奇数番目にある要素を選んだらソートした数列Aにおける次の要素も必ず選ぶことになる。選んで損しないからだ。これで遷移も定数時間で書けてハッピー。気を使ってdp配列を使いまわそうとしたが、2個先の配列にアクセスする必要があることに気づいたため、泣く泣く書き直した。

Bに戻る。種類数がkの通り数を考えていたが、これは全然ダメ。そもそも着眼点が違っていて、1からNのそれぞれの値が得られた数列に含まれるかを見ればよい。これもいわゆる主客転倒か。これがすぐに見えなかったのは反省。Dは得られていた式をWolframAlphaに投げたら閉じた式になった。

Gは、パスグラフのみを考えればよいとして、一番先頭に1e9-1を置いて、K-1番目に-1e9を置き、あとは周期Kで同じ値を繰り返すことにしたら通った。これは(N-1)%K==0のときだけNoになる。しかしコンテスト後に落ちてしまった。解説を読むと信じられない場合分けが書いてあって、かなり信じられなかったので、落ちているのも今は放置することにした。

Hは解けなかった。マージテクを思いついたと思って書いたが全然答えが合わなかった。

CF div.2があったが、見送ることにして、日記を書いていた。なろうをずっと読んでおり、溜めてしまっていた。

その後Amazonでお茶と黒コショウを注文し、GCJ Tシャツを受け取る手続きも済ませた。GCJ Tシャツのサイズ表記はSM、MD、LGなどと書いてあって何のことかよくわからなかったため、胸囲と身長の対応など調べてSMにしておいたが、どうやらこれらはSMall、MeDium、LarGeの意味らしい。これまでは確かMサイズを注文していたので、間違えてしまったか？

午前2時、布団に入ってなろうの続きを読んだ。そのまま午前10時まで読み続け、明日のことを考えて就寝した。

05/29(土)

午後3時と午後4時に目覚ましをかけていて、午後4時のほうで起きる。生協の弁当を受け取りたい。起きた時点ではまだ到着していなかったようだが、うつらうつらしていたらすぐに届いた。受け取って、そのあとちょっとなろうを読んだが、さすがにまずいと思いなおして午後4時半に寝直した。

午後7時半起床。眠すぎたのでしばらく布団でなろうを読んでいた。ARCまで残り40分くらいになったあたりで出て、食事した。その後今日の典型90問を解いていた。何をさせたいかはわかっているはずだが、実装が悪いのかクエリ回数が全然足りていない。

午後9時からARC121に出た。

NOMURA Programming Contest 2021(AtCoder Regular Contest 121) - AtCoder

3完189位、パフォーマンス2329、レートは2761→2724(-37)。DとEの両方を解けるべきで、解けなかった結果。しかし今はなろうが面白すぎて特に思うこともない。

Aは、xとyそれぞれで大きいほうから2個と小さいほうから2個を取り、その高々8個の点の組を全探索した。ちょっと慎重に解いたが、問題なくAC。

Bは、異なる体色の犬のペアの個数が小さいことにはすぐ気づいた。しかし、RGとGBのペアを考えているとき、なぜか2つのGが同じかわいさを持っていると考えてしまって、RBとGGに組みなおしたほうがよいと勘違いしてしまった。これで2WA。逆に、RGとGBをそれぞれ計算するときに同じGの犬を使ってしまう場合を考えなくてよいことはすぐわかった。

Cはよくわからない。1手で転倒数を1少なくできる場合はその動作をしてよくて、できない場合は4手使って転倒数を2少なくするか、5手使って転倒数を1少なくするかのどちらかをすることになりそう。前者はよいものの、後者が頻発するとちょっとまずい。操作回数の制約から、平均的に2手で転倒数を1少なくしたいからだ。しばらく考えていたがよい方法が思い浮かばなかったので実装したところ、フラグの管理ミスで1WAしたが通った。よくわかっていない。

そのあとsolved数を見てEに行った。自分の子でまだ決まっていない頂点の個数を持ち2乗の木DPをすることを考え、そのあとずっと格闘していたが、コンテスト終了間際に愚直なコードを書いたら合わないことに気づいてしまって、絶望。そのまま解けず終了した。

Eは解説の1行目だけ読んだ。1行目からよくわからなかったが、逆順列を考えると自分の子についての条件になって扱いやすくなるらしい。確かに、問題の定義をそのまま使っていたが、うまく木DPできなくて苦労した。Dは、一応問題分だけ読んでいて、TLで0を増やすということを耳に（目に）した。これは天才。

今日の典型90問の続きをする。させたいことというのは、黄金分割探索だろう。クエリの様子を出力してみると、どうやら途中から幅1で探索をしてしまっているらしい。Wikipediaで調べた通り、x1<x2<x3を持った状態で次に調べる箇所をx1+x3-x2に設定していたが、最初に区間を黄金比で分割する際の誤差が影響してどんどん変わってしまっているようだった。ならば、ということで区間の幅を広げるような補正をかけてみたが、まだクエリ回数は指定された15回より5、6回くらい多い。

次に調べる箇所を単純な計算で求めるのはあきらめ、毎回区間を黄金比に分割することにした。すると、クエリ回数が17回になった。誤差が怖かったが、毎回手作業で補正しているよりはマシ……ということだろうか。

この段階で、初手で区間の両端を聞いていることに注目する。ここはなくてもよいのかもしれない。そうしてやってみると、確かにほとんどのケースでは15回のクエリで特定できたが、端を区別できなくなってしまい、k=1,2のケースなどでは16回のクエリを使ってしまった。最後に、区間の両端として1とNではなく0とN+1を持つことにしたら、すべてのケースに対し15回のクエリで特定できるコードが完成した。

コードゴルフ。どうやら1500回クエリを投げるコードでもACにはなるらしい。dcで45Bを書いたが、すぐさま44Bに縮められた。45Bはかなり素直なコードだが、微妙に同じことを2回ほど書いているので、そのあたりが縮むのだろうなとは予測がつくものの、実際どういう風に縮められたのかはわからない。

日付が変わったあたりからまたなろうを読み始めて、午前7時くらいまで読んでいた。ここでいったんシャワーを浴びる。パソコンの前に座って、初日以来一切手を付けていないAHCのコードを書こうと思ったが、やろうとしていたことが案外面倒なことに気づいて諦めた。なろうが面白すぎるのが悪い。日曜日が期限のミニットペーパーを提出して再度布団に戻り、午後1時半までまたなろうを読んでいた。

途中で今日の典型の解説が投稿された。初期の区間幅をフィボナッチ数1597としておくと、すべての分割点がうまく整数点となってくれるらしい。なるほど……。

また、寝る直前に昨日Amazonで注文した商品が宅配ボックスに配達されたことを知ったが、取りに行くのは面倒だった。午後1時半就寝。

05/30(日)

午後7時半起床。布団でごろごろしているとAHCが終了した。僕が考えていたことというのは、乱数が加えられる前の縦横の辺の重みの元となる数をどうにかして推定すればよいだろうということで、これは焼きなまし法でも使うのではないだろうか、と考えていたが、TLに流れてきた解法を見ると、機械学習モデルなどを使用した人が多くて怯んだ。

初日に少しだけやっていたときはテスト実行が動かなくて困惑したが、コマンドを指定する部分で自分で定義したaliasを使っているのが悪かったらしい。また、RubyでString#*に負の数を与えるとREになってしまうらしく、ここで1WAした。

最短コードについては、1B差で勝っていたものの、相手のRakuはもう少し縮んだので、出しておいた。出してからさらに縮むかもしれないことに気づき真っ青になったが、30分待って再度提出してみるとそちらはWAになった。手元だとうまく動いているようだが、よくわからない。

午後9時からABC203に参加した。全完21位。

AtCoder Beginner Contest 203（Sponsored by Panasonic） - AtCoder

Aはどう書いていいかわからなかったので、とりあえず非ゴルフ解を出しておいた。Bは適当に式変形してdc。CはとりあえずRuby。

DからはC++で書いた。Dは二分探索することは一瞬で分かったが、実装にはかなり苦労してしまった。中央値となりうる値の最小値を求めたいが、判定関数として「x以上の中央値をとる場所が存在する」を使うのはダメだった。「x未満の中央値をとる場所が存在する」という判定関数を使用し、そのようなxの最大値を求めて、それに1足したものが答え。

Eは実装は面倒だったがちょっと面白く感じられた。 $Y$ 座標ごとに見て、例えば $(X_1,Y)$ と $(X_2,Y)$ （ただし $X_1\lt X_2$ ）があったら $([X_1,X_2),Y)$ をグラフの頂点として見ることで、ある点から別の点に移動できるかということをグラフの有向辺として捉えることができる。この上でBFSをした。

Fは両者の行動を混ぜて考えてもよい。青木君が草を抜く本数に対して高橋君が何回操作するかを考えたくて、これはAlienDPかと思ってしばらく調べてみたが、どうやらAlienDPの条件は満たせなさそう。そこで考え直すと、高橋君の操作回数がかなり少ないことに気づく。高橋君が操作した回数をDPの1つの次元で管理することで解ける。わかってみればかなり簡単だった。

ゴルフ。Aは現状sedが最短。sで置換した後tで分岐していて、これは仕様を完全に忘れていた。Bは全完後にちょっと縮んだので残念な思いをしたが、時間差で最短になっていた。CはPerl。DFは手つかずで、Eは適当にRubyで書いてある。Enumerable#partitionを初めて使った。

CF combinedがあったが見送ることにして、また布団に戻ってなろうを読んでいたが、午後3時半に寝落ちした。

今週はこの「影の勇者の再冒険　～～Re-Tale of the Brave～～」にすべてを破壊されてしまった。毎日少なくとも10時間くらい読んでいたらしい。

https://ncode.syosetu.com/n5534co/

月曜日から読み始めて、寝落ち時点でだいたい700話だった。このペースだと、外伝も含めてあと3週間ほどは身動きが取れなくなるだろう。最高困った。