03/29(月)
正午、起床。昨日のDDCCのアンケートが来ていたので回答した。
ABC158-Dが縮められていた。
非常に面白い。リダイレクトという機能があることを知っているつもりだったが、それがコードゴルフに役立つとは一瞬たりとも考えたことがなかった。これはprintからシェルにリダイレクトしているが、逆にシェルからgetlineにリダイレクトする記法もある。こちらは本当にコードゴルフには役に立たないだろう。getlineが長過ぎるためシェルの方で操作するべきで、その時役立つであろうsystem関数を使用するコードゴルフにはすでに前例がある。
ARC116-Fをupsolveした。
偶数長の列の真ん中2つだけ見る、というのが嘘だったらしい。先頭を削るか末尾を削るかで、奇数長の列に帰着できる。奇数長の列に最初に操作する側が必ず損する（しかもそれで手番が入れ替わるわけでもない）から、奇数長の列を考えるのが後回しになる。このことから、どちらが奇数長の列に対して最初に操作する役割になるか？が定まって、このとき、それぞれの奇数長の列の最終的な値を、先週書いたように真ん中3項を見ることで計算できる。これは、先週の週記に書いた「先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まる」ことに対応している。
例えば、全ての数列の長さが2以下だったら楽だろう。長さ2の数列のどちらを選択するか？ということのように、先頭と末尾のどちらかを削ることによる利得がプレイヤーによらず定まって、高橋君はその大きな方を、青木君は小さな方を選択するというようにできないだろうか？
週記（2021/03/22-2021/03/28） - kotatsugameの日記
コンテスト中の大胆な予想というのはあんまり外れていなくて、このもとで考察を進めた後に最初に考えていたことに立ち返れば良かったのだろうか。しかし、解説を読み解く過程でいくつか大きなギャップを感じていて、正直、そのうちの1つがわかっていたとしても、それ以外がわかったかというと自信がない。
昨日は先週ぶんの週記を投稿できずに寝てしまったので、その作業をする。数日溜めてしまっていたので、これにはかなり長い時間がかかった。ずっと文章を書いていた。日曜日のDDCCについてはオンサイトであるから、別に参加記の記事を作った。
DDCCの参加記を書くにあたって、自分の装置実装の模様を撮影した動画をTwitterにアップロードした。ブログ記事に動画を挿入するためだったが、これをきっかけに他にも数名アップロードした人がいるようで、僕は当時失意のズンドコにいてあまり他へ注意を払っていられなかったこともあり、改めて他の人の様子を見られて楽しい。
ただ、僕の動画には微妙に顔が映っている人が2名ほどいるようだったので、正直ちょっと危なさはある。
ARC116-Aのコードゴルフが進んだ。もともと僕のdcが最短で、今日、ループ部を改善して-1Bされていたのに気づいた。そこで改めて最短コードに近い長さの他のコードを眺めていると、Perl 39Bを見つけた。これは普通に三項演算子で書いているだけ。よく考えれば当たり前で、1行に1つしか数値がない上に出力もただの場合分けであるから、dcの利点というのはほとんどない。そこで改めてRakuで書いてみると、さらに-2Bできてしまった。最近はdcでバトルすることが多かったように感じるが、それで視野狭窄に陥っていたのか。
夜、CF #711 div.2に出た。全完8位。
Aは2|gcdとなる場合を考えようと思うと、桁上がりが起こるたびにパリティが変わって良さそうだな、という気分になる。桁上がりが連鎖する場合はともかく、そうでない場合はだいたい20個くらい試したら見つかるだろう。それで書いたら通った。正直全探索で正解だろうと確信していたので、桁上がりが連鎖する場合についてはあまり考えていなかったが、冷静になれば連鎖したらさらに20回くらい調べるのでよい。
Bは二分探索して上のbitから見る。Wが2^29くらいのbitを持ちうることを忘れて2^19から見始めたため、1WA。これに気づくのに結構時間を使ってしまった。Cはややこしいことが書いてあるが、愚直に実装して毎回何個あるかカウントすれば通る。Dもちょっと悩んだが、数は必ず大きくなるし、クエリごとに全ての数を見ても間に合うので、小さい方から順に見ていく。操作回数の上限については、「その数を作るために現在のクエリで操作した回数の最小値」を持つdpで考慮に入れられる。kxのオーバーフローで1WA。
Eはk_u<=k_vなるu,vについて? v uを聞いて、Yesだったらuとvは互いに到達可能。よってk_v-k_uが大きいものから順に聞いていけばよい。これは（正直それ以外の方針で解ける気がしないため、というエスパーでもいいが）証明も付けられる。uからvへ到達可能であることを言えばよくて、u->vという辺があれば当然よい。以下、ない場合（u<-vである場合）を考える。uでもvでもない頂点はN-2個あり、そのうちN-1-k_u個にはuからの辺が存在し、またk_v個はvへの辺が存在する。ここでN-1-k_u+k_v>=N-1>N-2のため、鳩の巣原理よりuからの辺とvへの辺を両方持つ頂点が存在し、それを経由してuからvへ到達できる。
Fはk==1でGrundy数を計算するコードを書き、しばらく実験しているとわかってきた。深さはmod 2kで同一視してよく、kから2k-1までのそれぞれの深さに対して、その深さの頂点に対するaの総xorのxorが非ゼロなら先手勝ち。ほとんどエスパーみたいなものだが、一定の確からしさは感じられる。全方位木DPを書いたら一発で通った。
その後しばらく本を読んでいたが、読みきれないまま午前3時半就寝。
03/30(火)
正午起床。
本来は明日本屋に行く予定であったが、明日は昼にyukicoderでコンテストがあることに気づく。4月頭に発売される本を購入することを考えると、03/31はともかく03/30だとちょっと不安感があるが、しばらく迷った結果、今日本屋に行くことにした。
母に車を出してもらい、ちょっと足を伸ばして県内でも大きめの本屋に行った。結局4月頭どころか03/30発売予定の本もなかったが、ともかくそこで5冊買い、さらに古本屋にも行って18冊買った。
└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/fbcGpVrT7w
— こたつがめ (@kotatsugame_t) 2021年3月30日
この古本屋に前回行ったのは、昨年の8月のようだ。
昼食を食べて古本屋に行く。仙台でも駅前のブックオフにはよく行っていたのだが、最近はご無沙汰。僕が最後に行ったときのものと比較すると、富山で僕が行く古本屋はラノベがよく揃っているように思う。
週記（2020/08/17-2020/08/23） - kotatsugameの日記
半年ぶりということで、本棚のレイアウトこそ様変わりしていないものの、内容にはいくらかの入れ替わりが見られた。まあ店側の商品が何も変わっていなかったとしても、その時々でどのようなタイトルの本に興味を惹かれるか、どの位置の背表紙に目を留めるか、というのはちゃんと時とともに移り変わっていくから、古本の購入は常に行える。
この古本屋、もといブックオフでは、他の店舗と同様トレカの売買も行っている。デュエルマスターズの高額カードを眺めていたが、今や売られているほとんどのカードは左上のコストが丸で囲まれた新しいデザインのものになっていた。そんな中で1枚だけ、僕にとって見慣れたデザインのカードがあった。あの「超新星アポロヌス・ドラゲリオン」……と同じパックで登場した「ザ・ユニバース・ゲート」だ。
《ザ・ユニバース・ゲート》 - デュエル・マスターズ Wiki
このパックは（子供のお小遣い程度ではあるが）かなり買った覚えがある。当然このカードも何枚か当たって、しかし実際にデッキに組み込むことはなかった。そもそもフェニックスなんてほとんど持っていなかったためである。効果のド派手さに惹かれるものはあったのだが……。それが今こうして値段が付いているというのは、なんとも面白く感じられる。ちょっと調べてみたが、別に信じられないような使い方をするわけではなくて、普通にフェニックスを捲ってターンを追加するらしい。
デュエルマスターズの漫画においては、エスメラルダがこのカードを使ってザキラ相手に3ターン追加し、シールドを14枚に増やしていた。そもそもシールドを増やすためのカードをそんなに使えたこと（そのころは墓地から回収して使いまわすなんてのもほとんど知らなかった）、また結局そのシールドがアポロヌス・ドラゲリオンのワールド・ブレイカーで1発で割られてしまったことなど、目まぐるしい展開に気を取られていたが、そもそも3ターン追加したのに殴り勝つ・あるいは究極銀河ユニバースによるエクストラウィンをしなかったことがかなり謎らしい。
ハーメルンの「輝きたくて」が完結した。
この作者の前作「うちの脳内コンピュータが俺を勝たせようとしてくる」は、作者自身があとがきで指摘しているように終盤かなり駆け足だったが、今度は駆け足どころではなく、個人的には打ち切りと変わらないくらいの唐突さで終わったように感じられた。最近10話くらいかけて描かれたイベントが終わっていたので、書きたいことを全て書いたからこその完結なのかもしれない。考えてみれば、特に山も落ちもない話を延々続けるのは良くないという考え方も存在するだろうし、その点においてはすっぱり完結させてしまうのが一番良いのかも。唐突に終わったと言ったが、では唐突ではない終わり方とはなんなのか？僕がリアルのVtuber界を全然知らないため、最後の山場を感じられなかっただけではないか？
「文字渦」を読んだ。面白かったが、かなり疲れた。自分としてはそれぞれの短編をそれなりに読めていると感じていたのだが、文庫本の巻末の解説を読んでみると、さらに丁寧な解釈がされていて、自分が全然読みこなせていなかったことに気付かされ、愕然。どの短編も全くの無から生まれてきたわけではなくて、ちゃんとモチーフになる事物が存在したらしい。
モチーフ、つまり現実と、そこから小説にするにあたっての創作の境目を見極めるのには、固有名詞の創作か否かの判別が鍵となるだろう。よくわからない語彙が出てきたときに、適当にスルーするか、それとも検索してみるか。全部検索にかけているといくら時間があっても足りないので、自分の嗅覚である程度判別しなければならず、僕は普段SFを読まないためにそのような嗅覚が備わっていない。
そういえば、短編のモチーフについては1つだけ明確にわかったものがあった。「ハングル大移動」と言われて、言語ごとにまとめられた文字の話をしているから、これはと思ってUnicode関連で検索したらあたりだった。Unicodeにおけるハングル文字の配列が変更されたことと、より一般にUnicodeにおける言語の文字領域の話だった。最初からそのつもりで読んだので、この短編についてはかなり読めた方に入るのではないだろうか。
検索している途中に面白い話を見つけた。
北朝鮮の文字コード(KPS 9566)には「金日成」と「金正日」専用領域が確保されているのだけど、2001年にUnicodeに追加のプロポーザルを提出していたらしい（残念ながら却下されたようだ） https://t.co/ePlXqdz7zI pic.twitter.com/xETOX8IAwh
— rls (@quolc) 2017年1月10日
現代の避諱。他のサイトでは、こうやって別の文字コードを割り振ることによって、この文字だけ装飾を付けたりすることが簡単にできると書いてあって、うまいなあと思った。
「時々ボソッとロシア語でデレる隣のアーリャさん」を読んだ。ふぁぼん氏がロシア語という部分に反応して言及していたラノベ。イラストが良いので、そういう言及がなくとも購入リストには挙がっていただろう。僕が引きこもっている間に売り切れてしまい、再版を待たなければならなかった。
ヒロインの出身国をたまたまフランスでもイタリアでも中国でもなくロシアにしてしまったせいでこんな異常オタクに目をつけられてしまった作者さん、かわいそうすぎる 寄り添った
— ふぁぼん(Фабон Ильич Фаворский) (@syobon_hinata) 2021年3月4日
非常に良かった。ロシア語要素はかなり限定的で、それよりも主人公の過去だとか、それから始まり本編を経ての心境の変化だとかに興味を惹かれた。設定されたキャラ同士の関係も良いしストーリーも良い。おまけに絵も良い。ラブコメとしても面白かった。次の巻が楽しみ。
さらに別の本を読み始めたが、途中で切り上げ、午前4時就寝。
03/31(水)
午後2時半起床。
せっかく本屋に行く日を前倒しにしたのに、当日起きてみたらコンテスト（yukicoderの新入生プログラミングコンテスト 2021（昼の部））が始まっていて絶望。しょうがないので遅れて参加し、途中昼食を挟んで解いた。全完。
Aはよい。Bはちょっと考えたが、たとえばハンバーグだとN+1品あればランチが1つできる、と考えられる。Cは幾何ライブラリを整備したことがあればすぐわかる、というより思い出せるだろう。Dでちょっと式を書いていたら昼食が用意されたため、Dを含めて残り5問を覚えてパソコンの前を離れた。昼食を食べながら全て解き、帰ってきて簡単なものから実装した。
HはA^Bを全探索すればよい。A^Bの各bitがどちらに割り振られるかについては、A<=Bという条件から最上位bitだけ確定し、あとは自由。FはMを全探索すればよい。Dは式を見ると4項ごとに-4倍されているようだったので、N%4とN/4%2で場合分けして実装。Eは拡張ダイクストラ。Gは正直何をやっても解けると思っていたが、実装しようと思ったら実は適当にやっても解けないことがわかった。冷静になると後ろから見ればOK。
夜、外食に行き、帰りに本屋に寄った。昨日行った本屋とは違い、こちらはそれより小さな家の近くの本屋だが、ラノベの品揃えは結構充実しており、4月頭に発売される本や昨日探してもなかった03/30発売予定の本を購入することができた。
また本を買ったぜ！ pic.twitter.com/ZPMnqiBVYx
— こたつがめ (@kotatsugame_t) 2021年3月31日
夜9時からまたyukicoder。今度は新入生プログラミングコンテスト 2021（夜の部）。最後の1問が解けなかった。
Aは、ややこしいが、制約から愚直にやって解ける。FA。Bは適当に貪欲。Cはちょっと面倒な実装。Dはさすがに親の顔より見た。EはBのコードを拾ってきて、後は平均Zを、各要素からZ引くことで総和=0に言い換えるやつ。Gはよくわからなかったが、Rubyで愚直に実装してそれなりに大きそうなケースを試すと爆速だったので提出。変数名を間違えていたりC++に提出してしまったりで、正答まで4回の提出がかかってしまった。C++に間違えて提出したほうはCEになるので、ペナ的には1WA。Gは二分探索の判定問題を考えるとX(X+1)/2>=Nなる最小の整数Xが答え。
Hは、ちょうどこの日きたまさ法の話題を目にしていたので、それをずっと考えていた。しかしかなり経ってから線形性が全然ないのでどうあがいても不可能であることに気づく。きたまさ法について、漸化式の左辺の添字を2倍するときに右辺で添字が変わる変数を勘違いしていて、線形性がなくても行けると盲信してしまっていた。後から適当に行列累乗など生やしてみるもTLEでコンテスト終了。答えを二分探索することでbit列の問題に言い換え、更に高速化できるらしい。
ところで、Gは（問題文は違えども）答えが同じになる問題がAtCoderに存在する。その問題の最短コードがこれだ。
を満たす最小の整数
は
。このコードはコードゴルフの配信中に見つけたことを覚えている。
改めて手元で調べてみたが、この式は少なくともでは正しい値になるようだ。どのようにして見つけたのだったか、再現してみよう。
まず、を解くと
になる。
は整数なので天井関数を適用するが、その中身に
を足すことで床関数に直せると考えると
。ここで根号の中の
と
が打ち消しあうとすれば
が得られる。昔はこの式によるコードが最短だった。
ここでとして両辺を2乗してみると、
。大胆にも
を無視すれば
が得られ、さらに根号を取るにあたって毎回
floorしても答えが合ったというわけだ。
SRMを見送ってラノベを読んだ。「僕が答える君の謎解き 明神凛音は間違えない」。最近「継母の連れ子が元カノだった」で売れている紙城境介さんの新作ということで、本屋で見かけて即決で購入した。非常に面白かった。ラブコメも面白いし、それでいてちゃんとミステリーしている。
ヒロインは、推理に必要な材料が集まった瞬間直ちに真相がわかる特殊能力の持ち主。これで犯人を指摘することはできるが、一方でそれを証明するための推理の流れは自分でもわからない。そこで主人公が、「ヒロインがどのようにして推理し結論にたどり着いたのか」を推理し直すという話である。これはつまり、一見それとはわからない形でストーリー中に「読者への挑戦状」を組み込んでいるとみなすことができて、後期クイーン問題に対する1つの回答である。
また、主人公が最初にたどり着いた推理の道筋が、ヒロインの当時の振る舞いと合わない（証拠を集めながら推理しているのに、集めた順番が違う等）ことがあって、さらに別パターンの推理の道筋を示すなど、多段階の謎解きになっている話もあって、巧みだなあと感じた。
さらに別のラノベを読み始めたが、半分くらいで切り上げた。午前5時半就寝。
04/01(木)
正午起床。
TechFULからAmazonギフト券が5000円ぶん届いていた。いつだかのTCBで1位を獲得した商品。回を重ねるごとにどんどん強い人が進出してきたので、今後1位を取れるかは微妙である。直近のセットなど理論値達成者がいたので、もはやそういう世界の勝負である。
このはてなブログを開設してからこれで3年らしい。RUPCの参加記を書こうと思って開設したはずだ。初期には解いた問題の解説記事を作ったりもしたが、2つ書いただけで終わっていて、それからしばらくは読書記録を更新するのとオンサイトイベントの参加記だけが積み重なっていき、最近（といってももう8ヶ月前か）になって日記を書き始めた。
ブログを開設する前、2017/03の時点から読書記録自体はメモ用紙で付けていたので、そのぶんも記事を立てたときに入れておいた。
チュウニズムのアップデートが行われていた。ノーツ数が4208の譜面が追加されていてびっくりした。これでもエイプリルフール限定ではなく通常の譜面のようだ。これまでの最多ノーツ数はKattobi KEIKYU Riderの3600ノーツだったので、一気に増えたなあという感想。
ABC197-Dが縮められていた。tauと書くとになるのだが、これは素直にギリシャ文字で
τと書くと2Bになるようで、-1B。piとπはどちらも2Bなのでどちらを選ぶかは好みであり、僕はいつもpiと書くが、それに引きずられてtauと書いたままにしていた。悔しいのでしばらく睨んでいたらZ*を使って入力に係数を掛ける書き方を思いつき、縮めることができた。さらに-1B。
夕方は本を読んでいて、夜からyukicoderでエイプリルフールコンテストに出場した。今年は自分も1問出している。
yukicoderが今年もエイプリルフールコンテストを開催するらしい。一昨年出題したが、今年も出題しようと思い立つ。
週記（2021/03/08-2021/03/14） - kotatsugameの日記
僕が出したI問題を除いて、コンテスト中にはBDEFKが解けた。
Bはシンプルで、必ずYesになる。Dは公式が存在する事実が有名。Eはなんとなくページのソースを確認したら解けた。FもBと同様エスパー要素のないシンプルな問題。Kは普通に難しくて、Y-12年とY+1年がそれぞれうるう年であるか判定して場合分けした。念入りに考えてコーディングしたところ1発ACできて気分がいい。
挑戦して解けなかった問題について。Aは質問タブを見れば良かったらしい。これは秋分コンテストでも見たもの。Cは最短コードがbash 10Bであるのを見て、tr A-Z a-zとかその逆を試していた。Text(cat)が最短でない以上入力を読む必要があると考えていたが、スペシャルジャッジで弾いていただけらしい。やられた！Hはどうしようもない。Jはfactordbで素因数分解するまでは良かったが、問題名の「除け者」という言葉に囚われて、指数が1であるような素因数だけ抜き出して連結したり掛け合わせたりしていた。特に、連結した文字列の長さは最短コードであるText(cat)の12Bと等しくなったので、これが答えであると確信したのだが……。
さて、僕が出したI問題についての話をしよう。この日記を書いている時点でFavが10個も来ていてありがたい。
最初は入力文字列に数字・空白や改行を入れてQコマンド以外も使おうと考えていたのだが、これはちょっと難しいというか面倒であることに気づいた。そこで今のような、英大文字小文字のアルファベット列を出力するソースコードを作成させる問題に簡略化した。
Esolang wikiを探してもまともな処理系はなさそうだったので、安心してオレオレルールを定めることにした。例えば作者のページではqqqqというソースコードがqqqq_qqqq_qqqq_qqqq_（_は改行）を出力するような書き方がされていたが、いちいち改行されてはたまらないため、改行を自動付加せずソースコードだけを出力するような処理系を書いた。これで改行なしのソースコードを食わせれば望んだように、先の例で言うならqqqqqqqqqqqqqqqqが出力されることになる。
しかしこの状態では、問題の回答となるソースコードは改行なしの文字列になってしまうため、出力の最後に改行を付けてくださいという注意書きが推奨される状況においてはあまりよろしくない。そこで、半ば無理やりであるが、処理系自身で1行だけ読んで末尾の改行を取り払うようにしておいた。
このとき2行目以降に適当な文字列を付け加えても無視されるので、そうやって2行以上に渡るソースコードを書いて、実行すると1行目だけ読まれて正しい文字列が出力されるので正しい回答です、とも言える。そんなのは困るため、さらに回答は1行だけにせよとの制約も付けた。1行だと回答は一意に定まるため、これでちゃんとスペシャルジャッジを用いずとも判定できる。まあスペシャルジャッジを書いても良かったのだが、面倒……。
以上のようなことを考えていたので、問題文では「改行」や「1行」という言葉を多用して、なんとか曖昧さをなくそうとすることになった。結果、どことなく怪しげな、何かありそうな問題文になってしまった。
H、Q、9、+以外の文字の扱いに関する質問がいくつか来た。それらは僕の書いた処理系ではnopになるが、WikipediaのHQ9+の記事だけ見ていてはわからないことだっただろう。そのあたりもカバーするつもりで「以下の処理系を使用します」と書いたものの、実際に僕が意図していたことは「以下の処理系を言語仕様の定義であるとします」であったことに気付かされた。
「新 謎解きはディナーのあとで」を読んだ。最近東川篤哉さんの手になる本を全く読んでいなかったので、久しぶりに触れることになった。記憶にあるよりもずっとギャグ調でびっくりしたが、それはそれで面白い。このシリーズの以前の本を読んだのはもう覚えていないくらい昔のことだから、キャラクターなどわからないのではないかとビクビクしながら読み始めたが、すぐ「ああ、こういうキャラだったな」というのが蘇ってきてスムーズに読めた。それほど特徴的なキャラクターたちだったのだろう。
3月が終わっていたので、3月に買った本・読んだ本の集計をした。
3月の集計
— こたつがめ (@kotatsugame_t) 2021年4月1日
買った：48冊
読んだ：14冊
積読：+34冊
積読（累積）：+32冊
来月から頑張りたい。
夜中、溜めていた日記を書いていたが、全然終わらない。月曜日から水曜日のぶんまで書いて、今日のは後回しにしてしまった。布団に入って少しラノベを読んだが、流石に夜が明けそうだったので就寝。午前6時だった。
04/02(金)
午後1時起床。
「新妹魔王の契約者」13巻を読んだ。シリーズ完結。12巻が発売されたのは2018/04だったので、丸3年開いたのか。これまで書かれてきた店舗特典等の短編集なので、これまで12巻のストーリーを総復習している感じで、以前の巻を参照しながら読んでみると面白かった。かなり重要なことを話している短編もあるように見えたが、確認してみると、確かにそのシーンは本編では飛ばされていたようだ。短編にたまに入る挿絵は当時描かれたものが使われているため、最近のラノベと比較するとそこまで過激すぎるということはなさそうだが、その分描き下ろしの絵はすごかった。これが全年齢対象というのは信じがたい奇跡。
「異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」という作品が完結した。
https://ncode.syosetu.com/n6063gu/
1作、面白いと感じるものを見つけて読了した。「異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」。
週記（2021/03/15-2021/03/21） - kotatsugameの日記
この日に読み始めた。読了したと書いているが、実際には「最新話に追いついた」という意味合いであった。
主人公の友人が高校に入学したこととか、話のネタになりそうな展開はあったものの、あまり触れられずに完結してしまった。番外編で触れられるかもしれないので楽しみに待つつもりだ。
yukicoderのコンテストに出た。6完。コンテストタイトルに〇〇's Birthday Contestと書いてあって、あまり注意していなかったが、本当にお誕生日コンテスト（原義）だった。
Aの問題文を読んでまずびっくり。この時点ではお誕生日コンであることに気づいていなくて、まともな問題を出す気がないのかとキレかけていた。
Bは3進数で桁和を取って、1引くときに繰り下がりが起きてもパリティは変化しないことを確かめた。これでも解けることは解けるが、そもそも取れる石が必ず奇数個なので、そのままNのパリティを見ればよかったらしい。解説を見て気づいた。
Cは多倍長整数が必要そうだったのでRubyで書いた。DはRubyのto_rで一発。pで出力すると(1/2)のように括弧が付くことに気づかず1WA。
Eは逆から見て/2と-3に言い換えた上、NからBFSした。実は4->1以外は/2できるなら貪欲にして良いことが示せるらしい。mod 3に着目すればよいと聞いたので考えてみた。まずmod 3=0のとき、-3しても/2してもずっとmod 3=0であるから、必ず不可能。mod 3!=0のときは-3しても/2してもずっとmod 3!=0なので、値がどんどん小さくなっていって最終的に必ず4->1か2->1ができる。当然減少スピードが速いほうが良いため、/2を優先的に選択するべきである。この方針だと2回に1回は/2することになるため、操作回数はlogのオーダーになる。
Fを見てTwitterでキレたところ、お誕生日コンであるとの指摘を受け、ここでようやく気づいた。この問題はだいぶ壊れていて、定数を確定させた後の式が何度も更新されることになった。僕は4!P(4n,4n-4)と書かれた時点でイコール(4n)!であると早とちりして、実際その解釈でACしてしまったが、実はn=0のことを考えると両者は一致しない。この点も考慮しつつPで書き表すのは不可能に見えていて、式はその後も何度も修正されていたが、Writerがやりたいこととそれが不可能であることがわかっているだけにもどかしい思いをした。今思えば質問タブでちゃんと指摘すれば良かった。
Gは普通に難しい。解説を読んでもよくわからなかった。
「氷の令嬢の溶かし方」2巻を読んだ。2人が自身の恋心を自覚して両片思い状態になった。これは健康に良い。身も蓋もない話だが、ちゃんと作中でそうであることが明言されているので安心感がある。列車の窓から黒い羊が見えたとき、その羊の少なくともこちら側半分が黒いことしか保証されず、他の羊に関しては何も言えないのと同様に、作中で明言されない限り、ヒロインは主人公が好きなのではなく、今でもただ主人公とお友達になりたいだけである、という可能性を否定しきれない。
なんにせよ、1巻はまだ馴れ初めといった感じなので、続刊が出るよう祈っている。
週記（2020/10/19-2020/10/25） - kotatsugameの日記
とりあえず続刊が出てよかった。さらに帯には何らかの賞を受賞したと書いてあったので、かなり売れているのだと思っていたが、どうやら打ち切り間近らしい。そういうことをかなりオープンにしている作者さんというのは珍しい気がする。それともこのラノベの出版元であるモンスター文庫特有なのか？僕はモンスター文庫を少し避けている節があるのでよくわからない。ともかくも2人が両思いになる様は読みたいので、売れてほしい。03/30に発売してから1週間が勝負……！
初めまして、デビュー作が半年で打ち切られそうなラノベ作家です。
— 高峰 翔@打ち切り間近の作家 (@kakeru_takamine) 2021年4月2日
売れ行き次第では続刊可能ですが、ここままでは…といった状況です。
1人でも多くの方に作品を知ってほしいので、RTで拡散してくださると助かります🙏 pic.twitter.com/A4b1PvHYym
また週記を書く。明日は仙台に戻るつもりなので、読んだ本の感想などを実物を参照しながら書こうと思うと今日中に書いておく必要があった。午前5時くらいにこの日のぶんまで追いついたので、就寝。
04/03(土)
午前11時半起床。
バナナを1本食べて車に乗り、両親とともに仙台へ向かう。普段は来た時と同じように新幹線に乗って帰っているが、たまに両親の旅行がてら車で送ってもらうことがあり、初めてではない。非常にありがたいことである。車で移動することのありがたみというのは、主には荷物を自分の目が届く場所で運べることにあると考えている。
途中で三春滝桜を観光した。
三春滝桜 | Find！三春 【みはる観光協会～福島県三春町】
— こたつがめ (@kotatsugame_t) 2021年4月3日
ぐるっと一回りして写真を撮ったが、その中から1枚だけ選んでツイートした。うまい文章が思いつかなかったので、位置情報だけ付けている。何回か写真を見返しているが、やはり綺麗であったと感じられる。せっかくなので、日記では他の写真も投稿しておこう。
夜になって仙台に近づいてきた。仙台は最近新型コロナウイルス感染症の感染が急拡大しているため、市街地で食事をするのは憚られた。よってサービスエリアのフードコートで食事をした。両親はレストランがあるサービスエリアを探していたようだったが、どれも一時休業中であった。
— こたつがめ (@kotatsugame_t) 2021年4月3日
仙台の部屋にたどり着いたのは午後9時手前であった。一緒に運んでもらった仕送りの食糧や本を部屋に入れ、代わりに読み終わった本を持ち帰ってもらう。読了済みだけど読み返したいので手元に置いておきたい本というのはいくつかあって、特に「りゅうおうのおしごと！」なんかは全巻部屋に保管していたのだが、いよいよ本棚の空きスペースがなくなってきたので、今回ついに持ち帰ってもらうことにした。非常にまずいが、本を売るというのは考えられないので、頑張って読むか、本棚を増やすか……。実家の本棚も埋まりつつある。
両親は部屋にしばらく滞在して、持ってきた食糧を棚に詰めたり、僕が放置していた水回りを掃除（！）してくれたりした後、帰っていった。今日は仙台で一泊して、明日富山に帰るらしい。調べると、富山に帰るのは「帰富（きふう）」と呼ぶのがよさそうだった。確かに「帰山」であると、該当しうる県は多数あるようだ。
しばらく放置してしまっていた競プロサークルの公式メールアドレスを確認すると、さっそく入部希望のメールが来ていた。入部届の準備をしなければならない。早速取り掛かろうとしたが、こどふぉがあったので出ることにした。
CF #712 div.1。4完して31位だった。レートは2649→2743(+94)。いい感じ。
A問題は、最初片方を(((...()...)))の形にしてもよいという大嘘をついたが、サンプルで落ちたので気づけた。s_i='0'なるインデックスの個数が偶数でなければならず、かつ先頭と末尾を含んではならない。これらが満たされているとき、s_i='0'なるインデックスだけを取り出すと()()()と)()()(になるように配置して、残りを先ほどの(((...()...)))で埋めるとよさそう。
Bは最初(i+j)%3で分けることを考えたが、ダメそうだった。そこでなんとなく(i+j)%2を考えるとうまくいった。そうやって市松模様で埋めると、2種類の色のうちどちらかは必ず使用できる。それでどちらかの色を使い切ったら、残りのマスはすべて隣り合っていないので、例えば色2を使い切って色1が余っていたら、色1のぶんを色1と色3の使用できる方で埋めていける。気づけたので面白い。
Cは、遷移コストの式を見ると、aの値が小さくなる方向の遷移はいくらでもできるので気にしなくて良さそう。ここで、まずaが大きくなるほうに移動して……と考えたが、スタートがa最小とは決まっていないためちょっと戸惑った。しかしよく考えてみれば、結局ぐるっと一回りするわけだから、a最小の頂点をスタート地点とみなしてもよい。あとはDPっぽく計算する。DPの値はpriority_queueで管理して、a+cが今見ているaより小さいか大きいかで管理するキューを分け、適当に移し替えながら計算した。コンテスト後のTLによれば、これはa+cの最大値を管理しつつはみ出した分を足すだけでよかったようだ。
Dはいくつか切れ目があって、分割したそれぞれのブロックについては配置が2種類しかありえない。またブロック同士は関係しないので、それぞれ貪欲に取れる。実装にしばらく悩んだ。サンプルも弱かったが、度胸試しとばかりに提出したら通ってびっくり。Eは全然わからなかった。
入部届（と継続届）の準備をする。どちらもGoogle formで作成している。継続届のほうは去年のものをコピーしてきて、いくつか質問を追加するだけで完成。追加した質問というのは、個人とSlackのアカウントとAtCoderアカウントを対応付けるための質問で、これは昨年度のICPC準備の際にうまく対応が取れずちょっと苦労した思い出から。
入部届のほうはそううまくはいかない。弊サークルの入部届は、formの回答を送信すると記入したメールアドレス宛にメールが届き、そこに記載されたSlackの招待リンクやサークルで使っているGoogle ドライブへの招待を通じて活動に参加するという形になっている。どうやら去年のものをコピーしてきただけの入部届ではうまく動いていないようだった。そもそもどういうシステムでそのような連携が可能になっているのかわからなかったので碧黴さんに確認して、返信を待つことにした。
まだなんとなく眠る気になれなかったので、第1回えでゅふぉを開いて全問通したが、かなり大変だった。
ABDEはよい。Cは105個の点が与えられて、偏角の差が最も小さいペアを出力せよという問題。偏角の差というのは時計回りと反時計回りどちらか小さいほうであって、必ずπ以下になる。制約から点の座標の絶対値は104以下であったから、atan2でソートしていけるかと思ったが、WA。
この問題の制約ならatan2を使用してもソートできるらしい。誤差の評価についてはmaspyさんが教えてくださった。
週記（2021/02/01-2021/02/07） - kotatsugameの日記
この部分に続いて引用されたツイートによれば、今回の入力では偏角に1e-8くらいの差があるなので、偏角ソートは良さそう。角度を比較するところがダメだったらしいが、それに気づいたのはこの日記を書いているときであって、当時は偏角ソートすら怪しんだ結果整数の範囲で偏角ソートするライブラリを持ち出した。
さて、角度を比較しなければならない。今回は偏角の差であるから、内積を取ってからcosだけ取り出したものの大小比較でよさそう。そのままだと分母にユークリッド距離のsqrtが出てくるが、ここで分母を払って2乗し、改めて符号をつけなおすことで、ちゃんと整数範囲で比較できる。ただし値の大きさが8乗オーダーになるので、__int128を使わなければならなかったが、通った。
みさわさんに別の方法を教えてもらった。あるベクトルを回転させてX軸上にそろえて、角を構成するもう一つのベクトルも同様に回転させ、その位置を外積によって比較することを考える。回転は、以下のツイートのような考え方を用いれば、整数の範囲で行える。
とりあえず複素平面と思っておきます。複素数の掛け算は(極座標表示を思い浮かべれば)回転拡大です。
— みさわ (@Mi_Sawa) 2021年4月3日
共役との積は実数なので、p の複素共役を掛け算する操作は、p を実軸に持っていく回転拡大になります。
これは回転行列のabs倍をしているとも考えられるが、そちらだと整数になることがあまり直感的ではないように感じられるので、上の説明が一番わかりやすかった。これだと移動後の座標の値は2乗オーダーで、外積でさらに掛け合わせても4乗、よって64bit整数に収まってくれる。Y座標を0以上に直すことで、偏角の差がちゃんとπ以下になる。
Fは幾何。自己交差のない、（凸とは限らない）多角形があって、クエリごとに与えられる直線との共通線分の長さを答える問題。かなり苦労した。基本的には直線と多角形の外周との交点を列挙し、ソートして2個ずつ見る。多角形の頂点が直線上にある場合は、その直前の頂点と直後の頂点を結んでできる線分が直線と交差するか見て、交差しなければその点は考えないことにする。
多角形の辺が直線上にある場合が一番つらい。適当に前処理して、そのような辺が2つ連続することがないように、もっと一般には内角が2直角の頂点がないようにしておく。先ほどと同様に直前の頂点と直後の頂点を結んでできる線分が直線と交差するか見て、交差すれば、交点の代わりに辺を区間として見て両端を持っておく。交差しなければ辺の両端をそれぞれ持ち、処理後にその間が答えに足されていないようなら改めて足すことにしたら通った。
布団に入ってなろうを読み、午前7時半就寝。
04/04(日)
午後1時半、目を覚ます。
昨夜碧黴さんに送ったメッセージに返信があった。Google formの回答を集めるスプレッドシートからスクリプトを動かしているらしかった。formをコピーしただけでは動かないのも当然のことだが、幸いスクリプトや設定をコピーしてくるとちゃんと動いた。
まず継続届のリンクをサークルのSlackに貼って、記入をお願いする。同時に活動する曜日に関するアンケートを取った。新入部員が出そろうまでの仮の日程で、またゴールデンウィークを目途にアンケートを取りなおす予定だ。さらに入部届を公開する。とりあえず入部希望のメールを送ってくれた人に送って、さらにサークルの公式サイトに2021年の新歓ページを作って載せてもらった。サイトのほうは記法などよくわからないことが多かったのでホスフィンに丸投げした。ありがとう……。
ホスフィンはさらにSlackに自己紹介用のチャンネルも作ってくれた。
布団に倒れこむ。眠いが、昨夜読んでいたなろうの続きが気になるので、ずっと読んでいた。途中のこどふぉも微妙な眠気を言い訳にサボり、驚くべきことに午前4時半まで読み続けていたようだ。そのまま寝落ちした。
なろうと書いていたが、正確には「ノクターンノベルズ」というなろうの男性向けR18版サイトだ。「放課後インスタントセックス」という作品。この日の時点ではまだ最新話に追い付いていないので、特に感想などは書かない。
