週記(2021/05/03-2021/05/09)

05/03(月)

先週分の週記を投稿したのは正午くらいだった。今日は午後8時から競プロサークルで解説会があるし、準備も相変わらず手つかずなので、寝ないことにする。まあそれでなくても日曜日の起床時間は午後11時だったのだ。

昼食を手に入れるため、買い物に行くことにした。これまでは大学近くのコンビニまで行っていたが、より近くに小さめの店があることをGoogle Mapで確認したので、散歩がてら出向いてみることにした。店は小さく、品ぞろえもよくない。僕が入店したら爺さんが奥から出てきてレジに陣取るという、なんともいたたまれない感じ。確かにコンビニより近いし、標高差的にもこちらのほうが通いやすそうだが、これから先利用するかというと……うーん。まあ種類を選ばなければ食べ物は買えるから、利用してもいいのだが、いたたまれなさがすごいのが自分の中では一番の問題だったようだ。

帰ってきて、解説会の準備を始めるにも中途半端な時間であるから、ラノベを1冊読むことにした。「ルミナス☆アイドル」。主人公が幼馴染3人組をアイドルユニットとしてプロデュースするという話だ。設定は非常に好みであったが、話の展開の仕方があまり良くなかった。IKUTOという現役トップアイドルかつ学園の非常勤講師が、ことあるごとに主人公たちにアドバイスを与えたり助力をしたりするのだが、その頻度が高すぎるように感じられた。何もかもIKUTOにおんぶにだっこであるような状態では、プロデューサーとしての才能があるとされている主人公のそのすごさというのもよくわからない。IKUTOがすごいのは十分伝わってくるのだが。シリーズが続いていけば主人公の主人公らしさというのも徐々に明らかになっていったのかもしれないが、残念ながらこのラノベは1巻打ち切りであった。

解説会の準備をする。今日は僕だけが発表者になるらしい。ABC199のBCF問題のスライドを作成した。かなり時間に余裕があったので、解説会が始まる前にすでに今日の解説会の記録を公式サイトにアップロードする準備が整っていた。

さて、解説会が始まった。今日は見学2名、ホスフィン、僕の4名らしい。やはり連休の半ばであるというのは効いているようだ。今日はかなり気を付けて丁寧にしゃべっていたつもりだが、自分でそう思っているだけで普通に早口のままかもしれない。このF問題を全くの初心者に解説してもどうしようもないので、せめてもと思い二分累乗法について喋っていた。F問題の解説も終わりかけた頃合いで見学の2名が相次いで抜けてしまった。タイミングを見計らっていたのだろうか、だとしたら申し訳ない気持ちになる。入退室自由とは謳っていてもやはり気になるのは仕方ない。また終わる時間を明確に決めていないのもあんまりよろしくなさそう。

結局Meetはホスフィンと1対1になったので、サークル運営について話していた。いつかどこかでサークルが用意したセットをyukicoderで出題したいから、音頭を取ってくれ、といったことを言われた。僕は誰かの提案に便乗する気だったので、自分が主体となるらしくびっくりしていたが、それもサークル長の務めである。

午後10時くらいに布団に入ってスマホでなろうを開いたが、即座に寝落ちした。

05/04(火)

午前4時半、目を覚ます。布団で少しだけコードゴルフした。

例えばRubyは文の区切りとしてセミコロンと改行のどちらを使用してもよい。僕はこのような場合、自分の美意識に従ってできるだけ改行を使っている(しかし、この仕様はAWKでも同じだが、そちらはセミコロンを使っている)。改行を含むソースコードを提出するときは、CRLFではなくLFとして文字数を減らすため、特殊な提出方法を行う必要がある。特殊といってもUserScriptがあるので、それを導入するだけで済むのだが。

github.com

しかしこの提出方法は現状スマホからだと行うことができない。そういう理由があって、Rubyなどでコードゴルフする必要がある場合は毎回パソコンの前に座っているのだが、この時はPerlでゴルフしていたので、布団からでも提出できたというわけだ。Perlは、文の区切りはセミコロンのみである。

そのあとはなろうを読んでいた。午前5時から午前7時半までかけて、この作品を最新話まで読んだ。

https://ncode.syosetu.com/n6285gw/

最近はある方のツイートを見てなろうを漁っており、TSものが多くなってきている。この作品にはほかにも配信者要素、掲示板要素があって、好みだ。

午前8時から午後0時半まで、再度寝ていた。

yukicoderに問題が追加されていたので、解いた。

No.1498 Factorization from -1 to 1 - yukicoder

105までの素数は104個くらいしかないが、そのすべてで試し割りしていると微妙に間に合わなさそう。そこで、素因数分解する対象の数がi^2+1という特殊な形をしていることに着目し、必要となる素数を絞り込むことにした。素因数分解する対象を全列挙して、そのどれか1つ以上を割り切るような素数だけ抜き出してみると、個数はだいたい半分になった。抜き出すプログラムも手元では2secくらいで実行できたので、そのまま提出してみたのだが、見事にTLEした。オンライン実行で試してみたところ、手元では2secだったのがyukicoderのサーバ上では3secになっていてたまげた。

そこで、必要な素数と不必要な素数それぞれの特徴を調べてみることにした。4で割った余りが3でなければ必要な素数となるようだ。i^2+1\not\equiv 3 \pmod{4}ということから類推したが、どういう原理なのかは知らない。ともかくも、全探索によって正しいことはわかっている。これで素数を抜き出す箇所の大幅な高速化がなされ、AC。

しかし、抜き出した素数すべてで試し割りして失敗するような入力が続くとかなり時間がかかるらしい。そういうケースを作成してチャレンジしておき、改めて一度素因数分解した数値をメモしておくようなコードを書いて通した。解説を見たところ、もっとちゃんとした解法があったようだ。

コードゴルフのつもりでfactorコマンドに投げてみると爆速だった。最短コードについては、問題が追加された深夜の時点で%20さんがコードゴルフしていたようだった。

vectorの途中の要素が、一番後ろの要素とswapしてからpop_backすることで削除できるという話を聞いた。言われてみれば当たり前だが、かなり盲点。

外に遊びに行こうと思っていたが、今日の典型90問・031が追加されたのでコードゴルフすることになった。climpetさんとバトルしていたら夕方になってしまったので、今日は外出するのを諦めた。

atcoder.jp

dijkstra法を使用する問題でコードゴルフするため、Pythonを使っている。頂点の情報として2つの整数を組にして持つ必要があった。以前のコードだと数値2つをくっつけて1つの整数にしていたが、ここをtuple<int,int,int>にしたところ、TLEしてしまった。Pythontupleは遅い、という話は何度か耳にしていたので、仕方ないかと思いつつも、試しにtuple<tuple<int,int>,int>で持ってみたところ、これまでと変わらない速度でACしてしまった。かなり面白い。

レトルトのパスタソースを使用する際、これまではわざわざ別の器を用意して電子レンジにかけていたが、今日ついにパスタと一緒に茹でる決心がついた。テク自体は以前から知っていたが、パスタを茹でる時間とレトルトを湯煎する時間が合わず、断念していた。別にきっちり時間を守らなくてもよさそうであることに気づいたので決行。

何もすることがないので、以前の典型90問のコードを見直していた。7問くらい縮んだ。

夜中、CF div.3に出ようと思ったら、1日延期されていた。仕方ないのでコードゴルフ続行。典型90問・023はO(HW2^{W})で通したっきりになっていたが、ちゃんと想定解で出しなおしておいた。状態を圧縮して事前に番号を振るのをサボり、mapで処理していたのだが、以前に出した「dpテーブルの値が0のところから遷移しない」高速化をしたコードに負けてしまった。そちらの解法も、確かに圧縮こそしていないものの想定解の計算量と言えるのかもしれない。そのあとRubyに移植してコードゴルフした。

Array#max (Ruby 3.0.0 リファレンスマニュアル)

現在の実装では、先頭2つをまず比較して、そのうち大きいほうと3つ目を比較……というのを続けていく実装になっているらしい。おおよそeach_cons(2)のようなことができる。これまではreduceを使用して書いていたはずだから、縮むコードが存在するはずだ。そう思ってずっと探していた。1つだけ見つけることができた。

atcoder.jp

探している間も寝そうになっていたから、とりあえず一通り目を通したと思った段階で布団に入った。布団でなろうを開き、「転生したらスライムだった件」を読み始めた。主人公がなかなか人型にならなくてもどかしい。10話ちょっと読んだ段階で寝落ちした。午前6時だった。

05/05(水)

午前11時半起床。

テストケースハックでコードが短縮されていた。もともとVimだったのがsedになっている。[a-z][a-z]があってかなり縮みそうな予感がするので、Vimに戻して\lを使ってみたが、出力するために書いておいたYesesに反応してしまいダメだった。テストケースをダウンロードして、2つある[a-z]のどちらかがもっと短くならないか試していたら、なんと[a-z][ah]で通ることを発見した。左右どちらかを1文字にしてしまうとダメで、さらに2文字+2文字もすべてダメなようだから、この方針だと[a-z][ah]が最も短い。

今日こそ遊びに行こうと思って準備していたところでちょうど典型90問・032が追加された。このままだと昨日と同じことになるので、適当に縮めてすぐ切り上げた。

まずミスドで腹ごしらえして、ゲーセン。今日は「真千年女王」でSSSを達成した。2021/04/28に縦連が間に合わないと言及していたもの。前半の縦連は、今日やってみると普通に間に合った。後半は真ん中にノーツが増えて、それをカバーするために手を広げると間に合わなくなるようだった。このような場合は真ん中3鍵の連打を片手で処理することにしていたが、今日はこれが信じられないくらい下手くそで辛かった。ラストの4鍵は普通に難しいが、事前に家で再生速度を落とした譜面動画をじっくり見てきたので、そこそこうまくいくことが多かった。

ほかにも、13+のスコアがいくつか伸びたのと、13のAJが3つ増えた。明らかに速い鍵盤についていけるようになっている。

ゲーセン頻度的に考えれば、2021/05/09に閉店する仙台レジャーランド一番町店に来るのは、今日が最後の日になりそうだ。そこそこ感慨深くなりつつ帰宅した。今後はセガ仙台に行く。チュウニズム、より一般にセガ音ゲーをするにはここが最適だろうが、ボルテや弐寺の民はどこに行くのだろう。他人事ながら大変そうだ。

シャワーを浴びてCF #719 div.3に出た。全完。

Aは適当に書いたがちょっと怖かった。Bは桁を全探索する。テストケースごとに毎回計算してよい。Cは非常に難しかったが、4x4を手で構成している最中にひらめくことができた。連続する数を斜めに置いていけばよい。Dは超典型問題、非可算無限回見た。

Eは左端を全探索する。左端を1つ右に進めるとき、コストが1増える羊と減る羊がいるので、それを管理する。コンテスト後に知ったが、これはi番目の羊の位置をA_iとして\sum |A_i-i-x|の最小化となる。そういう言い換えをすると、AtCoderに全く同じ問題がある。

C - Linear Approximation

F1は二分探索。F2も二分探索で、1度聞いたクエリの答えはメモしておく。この時、クエリを聞く前・聞いた後に0から1になったものを補正するためにBITを使った。聞く区間の候補は218くらいあるが、答えるクエリが少ない以上、あまり細かいところを何種類も聞くことはない。GはスタートとゴールからBFSする。高々1回使用するワープポイントをどれとどれにするかは独立に決められる。

Gの入力が4e6個あるうえ、テストケースが120個以上あったので、ジャッジが詰まりまくった。scanfcin高速化より遅いので戦々恐々としていたが、ふたを開けてみれば1800msくらいで収まった。自前の高速入出力を使うと260msになった。

布団に入ってちょっとした競プロ関連の記事を読んでいたが、耐えられず寝落ちしてしまった。午前4時半だった。

05/06(木)

午前11時起床。大型連休を挟んで久しぶりに学食に行き、食事した。帰ってきてから、大学生協のオンライン書籍注文サイトで本を注文した。

午後1時からゼミ。

先々週のゼミの顔合わせの時には教科書を注文しようかとも考えていたが、なんとなく放っておいているうちに2週間が経過してしまった。

週記(2021/04/19-2021/04/25) - kotatsugameの日記

まだ買っていない。今日も無の状態でゼミに臨むことになった。今日のゼータ関数は、最初はフーンという感じだったが、途中で出てきた公式がものすごい形をしていてあえなく轟沈した。僕がメインにしているほうは少しだけ難しくなったような感じ。少し先にFormal power seriesという単語が見えてかなり興奮した。最後まで質問も発言もせず終了。

「プニキとはじめるリーグ運営 ~野球ゲーム?作って運営します~」が完結していた。

https://ncode.syosetu.com/n4212eh/

非常に面白かった。一気読みしたのでまだ細部の記憶が残っているが、その状態でエピローグとしてその後十数年の話をダイジェストのような形で見せられ、心がしばらく囚われてしまった。作者のブーブママさんの別作品であるVtuberものも、本編完結後定期的に小噺みたいなのがずっと入っていたが、本当に終了するらしい。いったん充電期間に入るとのことで、また新作が読めるのを楽しみにしている。

昨日のCF div.3のシステスが始まっていた。G問題のscanfはTLEしてしまい、なんとなく出しておいた高速入出力が通って何とか全完が保たれるという状態になっていた。ペナルティ的には1WAのカウントも含めて+24だが、僕より上にいた人も数名Gをシステスで落としたようで、順位は8位に上がった。dijkstra解を落としたかったらしいが、入力サイズはなんとかならなかったのだろうか。

AtCoder Jobsに登録し、インターンに応募してみた。

週記(2021/04/12-2021/04/18) - kotatsugameの日記

書類選考で落ちた。どうやらかなり人が集まっているらしく、僕のように内容が薄いエントリーシートは落とされる運命にあるようだ。自分に自信があるフリをしてそれっぽいことを書いておかなければならない。何もできないからと言って何もできないと書くとダメらしい。ともかく、インターンには行きたいので、また別の会社に応募してみた。AtCoderJobsでボタンを押すだけ。

大学の課題をする。まず2週溜めていた論理学の講義を視聴し、ミニットペーパーを提出した。初回・第二回はイントロのような感じだったが、今回から本格的に証明が始まる。導出規則が最初に並べられて、例題を通して扱い方を確認していく形式らしい。第三回はMPP、MTT、DNで、第四回はCPだった。CPはもう使い方からして面白い。今はまだ証明した命題が感覚的に何を意味しているのか理解できるが、もうそろそろ限界だろう。

次に数理統計学。課題はただの計算問題だが、3x3行列の逆行列を求める必要があるし、わざわざ注釈で計算機を使ってもよいと書いてあるから、遠慮なく使うことにした。これまではOctaveで書いていたが、浮動小数点数をそのままレポートに書いて提出するのはちょっと具合が悪い。そこで今回はRubyを持ち出してみた。やっぱり有理数型はいい。逆行列有理数型で求めてくれたのはありがたかった。冷静になると当たり前か。

夜、div.3のシステスがやり直されていた。かなり謎。

ほかにやっておくべき課題はまだ残っていたが、典型90問のコードゴルフを始めてしまった。まったく成果が得られないまま3時間くらい経過したところで、眠気に耐え切れず就寝。午前0時半だった。

05/07(金)

午前8時半起床。ゴミを出した。

そのあとはずっと布団にこもってなろうを読んでいた。最近は「転生したらスライムだった件」を読んでいる。やはり超人気作だけあって面白い。

https://ncode.syosetu.com/n6316bn/

以前TLに流れてきたファンアートが非常にかっこよかったので、そのシーンを読むのを楽しみにしていた。思っていたより早い段階で出会えて、すでに満足。

www.pixiv.net

能力のルビ振りについて気になったことがある。「英雄覇道」と書いて「エラバレシモノ」と読んでいるが、このように熟語の読みに熟語を噛み砕いて言ったような日本語をつけるのは、一時期流行ったのだろうか?他には「デスマーチからはじまる異世界狂想曲」でも見たことがある気がする。

結局昼間も布団から出られず、学食には行けなかった。夜になってようやく空腹がなろう欲を上回ったため、布団から出て学食の夜の部に行った。

途中でAtCoderJobsを確認したところインターンに応募した会社から返信があって、履歴書などを送る必要があるらしいことを知った。慌ててコンビニで調達しようとしたが、データでの提出ならネットにフォーマットが転がっているという話を聞いたので、とりあえずそちらを探してみることにした。

帰ってきてまたなろうを読み、時間になったのでyukicoderに出た。

yukicoder contest 294 - yukicoder

Aはかなり面倒そうだが、AWKで一発だった。Bは非常に難しい。90度回転しても手も足も出ず、実験してOEISに投げても何も得られなかったが、実験した盤面を出力してみると、N=3以降は中途半端な部分が全部埋まっているようだったので、その範囲を数える数式を気合で求めた。小さいところは埋め込むことになる。Cは飛ばしてDに移った。

Dは、やるべきことはわかるので丁寧に実装。連結成分ごとに見ると、1点の値をxと置いたときに他の点はA_0+xA_1-xのどちらか、または両方の形で表せることになる。これでxが一意に定まるならばよし、そうでないならば可能な範囲を求めて、またさらにmax<Kとなるような値も求めておき、最後に引く。

Eは解法ガチャに成功して良い方針を一発で引けた。公式解説は残念ながら読めなかった。公式解説のような方法で考察できれば強いのだろうが、できないものは仕方ないので、どのようにして解いたか記録しておく。

まず、数列Aをまとめることを考える。bitwise ANDが重要なのだから、まとめ方はゼータ変換と呼ばれるようなヤツで、自分を含む集合すべてについての和を求めておく。これを数列Sとしておこう。C_5を例に取り上げて実験してみる。

まず、Bの添え字としてありうるのは5の部分集合である0,1,4,5である。B_5に掛けられることになるAの和というのは、i \;{\rm AND}\; 5=5、つまり5を部分集合に含むようなi全てについての和であるから、S_5である。

B_4に掛けられるのは、同様にしてS_4とな……らない。S_5B_5のほうに吸収されるので、S_4-S_5である。同様にB_1に対してはS_1-S_5B_0に対してはS_0-S_1-S_4+S_5となる。

すべて足すとC_5=B_5S_5+B_4(S_4-S_5)+B_1(S_1-S_5)+B_0(S_0-S_1-S_4+S_5)。この状態でもかなり綺麗な形をしているように見えるが、実際のところSについてはめちゃくちゃ中途半端な和のため、扱えない。そこで、今度はSに注目して整理してみることにした。C_5=S_5(B_5-B_4-B_1+B_0)+S_4(B_4-B_0)+S_1(B_1-B_0)+S_0B_0

これはかなりきれいである。ちゃんと添え字が0まで出てきているし、符号の反転も規則的だ。これはいわゆるメビウス変換と呼ばれるものらしいが、そんなことは知らなくても適当に__builtin_parityを見て符号反転し、ゼータ変換してもう一回符号反転することで全て求まる。それを数列Tとしておこう。T_5=B_5-B_4-B_1+B_0だ。

C_5=S_5T_5+S_4T_4+S_1T_1+S_0T_0となった。添え字がそろっているのもうれしい。詳しく証明したわけではないが、もう見るからにC_k=\sum_{i\subset k}S_iT_iだろう。STに対し点ごとに積を取ってゼータ変換するとACした。

Fを結構長い間考えていたが、解けなかったので、Cに戻った。左から順に見ていくことで、各マスの確率が自分の1つ右についての1次式で書ける。ここで右から順に見ていくことでどんどん確定させていける。有理数が怖かったのでRubyを使った。そのあとまたFを考えていたが、結局解けずに終了。

Fは、まず畳み込みで'i''n'の間に何マスあるペアがいくつ、というのが数え上げられる。ここで止まってしまったのだが、コンビネーションを分解することでまた片方の列をreverseした感じの畳み込みにできたらしい。言われてみれば本当にそうなんだが……。

直後にCF #720 div.2。4完。かなり難しく感じた。

Dashboard - Codeforces Round #720 (Div. 2) - Codeforces

Aから1WAした。B>1が条件で、ABAA(B+1)を出力すればよい。ABで割り切れる、ではなくABで割り切れるだと思っていて、A%B!=0が条件だとしていた。

Bも非常に難しかった。ずっと隣り合うペアに対して操作することだけ考えていた。冷静になると、数列の最小値を選べばもう片方はやりたい放題。僕はminとmin+1を交互に並べたが、TLでは1e9+7を1つおきに挟んだ人もいたらしい。なるほど。

Cは、クエリ回数の制約が二分探索をしなさいと言っているので、判定できそうな質問を探した。結果t=2でx>=p_iが判定できるようだったので、それを使って1つ求める。残りの数字は、今わかったものと組み合わせてt=1でmaxを得たりt=2でminを得たりする。maxになるものとminになるものどちらが多いか確認しておけば、全体の高々半分しか再チェックに回らないため、クエリ回数の制限に通る。微妙に眠い頭でminとmaxと変数が入り混じった式を扱うことになって大変だった。

Dはただの木DFSだと思ったけどWA on pretest 2。「工」みたいなグラフは、真ん中の棒を切るのが一番良いが、適当にDFSすると足の片方を切ってしまう。Eは解けず。

夜中はずっとコードゴルフをしていた。Perlに新手が出た。

atcoder.jp

無向グラフの読み取りにはこれまでmap{push@$_,$_[--$|]for@_=glob}<>という決まりきったイディオムを使っていたが、自己ループの存在が問題にならない場合、@_ごとpushしてしまってもよい。これはかなり適用範囲が広い。

布団に入ったら即座に寝落ちした。午前8時だった。

05/08(土)

午後4時起床。

寝る直前に今日のぶんの典型90問の問題を読んでいたが、まったくわからないまま眠ってしまった。起きて再度考えてもすぐにはわからない。結局実装を含めて1時間半くらいかかった。

解法はこうだ:dfsの行きがけ順に頂点に番号を振り、それでソートして隣り合う頂点のLCAを求めておく。このLCAが深い順に隣り合う2つのペアをマージしていき、グループの代表の点は元の代表の点2つのLCAにしていく。以前までの代表の点と新しい代表の点との間の距離を答えに足す。

今日は午後8時くらいからへのkと一緒にちょっとした配信をする予定だ。VSCode拡張機能で画面共有して行うらしいので、手元にセットアップすることになった。適当にインストールしてC++シンタックスハイライトとVimのコマンドを入れたが、操作性はVimのままGUIの特徴も兼ね備え、さらにIDEっぽいこともしてくれる、かなり便利な環境になった。しかしてIDEではないのだから、コンパイラインタプリタについてはこれまで自分が使ってきたcygwinが対応するというのも嬉しい点。これから競プロを始める人はVSCodeを使うのが一番良いだろう。僕はかたくなにcygwin+Vimで続けるつもりだが。

昨日のPerlコードがさらに縮んでいた。argmaxがかなり上手いが、なんとなく既視感があるので、一度見たけど忘れていただけのテクニックかもしれない。忘れちゃ意味ないよ。

atcoder.jp

そうこうしているうちに配信が始まった。15分くらいで終了。

事前に少しだけ打ち合わせみたいなことをして流れは決めておいたが、セリフはほとんどアドリブであった。改めて聞き直すと、2人が一緒に喋っている瞬間や、僕がそれを恐れて無言だったりボソボソ喋っていて聞き取れなかったりしたセリフがあった。またやはり全体的に滑舌に難がある。せっかく人前で喋るのだから、そういうこともちょっとは考えておきたかった。

ABC200に出場した。全完17位。

KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200) - AtCoder

A、Bはよい。Cは親の顔より見たタイプの問題。Dはdpして復元した。Eは、まず3つの値の総和が特定の値になる場合の数を包除原理を用いて計算し、これを利用して求める組の3つの値の総和がいくつになるか計算した。これはO(N)で、残り1つずつ決めるのにもO(N)かけた。

Fは0と1が切り替わる回数に注目すればよい。この回数がk回のとき、操作回数は\lfloor\frac{k+1}{2}\rfloorとなる。kの偶奇で分ける必要があるが、これは両端の文字が異なるかどうかを見て足す値を制御することで通常の除算にできる。両端の文字としてあり得るものを最大4通り探索して、それぞれに対し0と1が切り替わる回数を計算する。実装の都合上文字列Sが1文字だと面倒なことになるようだったので、この場合だけ先に処理することにした。S="0"S="1"の場合は明らかで、S="?"の場合は愚直に計算した結果をOEISに投げてK2^{K-2}となる。

Dは微妙に噓解法だったらしい。同じインデックスから2通りの列を作成するのが難しそうだったので、2つの列の最後のインデックスが異なる値にできると思って実装していたのだが、これは200 1という数列が反例となって成り立たない。

コードゴルフ。Aはdcで8Bを書いて暫定的な最短だったのだが、Vimに負けた。Vimの8Bは確認していたが、不必要なコマンドがあることに気づかなかった。数値をインクリメントすると、カーソルはその数値の末尾に移動するため、わざわざ$する必要はない。

Bはdc。場合分けを減らすため、2種類の値を両方用意して、適当にスタックの深さをいじってrしている。N%200という値で割り算を試みることで、0の場合はそのまま、そうでない場合はスタックトップの値を潰せる。これはかなり上手かった。Cもdc。

Dは想定解の鳩ノ巣原理がかなり賢い。探索する回数はかなり少ないので、Rakuでも間に合うようだ。またRubyのcombinationは取り出す要素の個数を指定する必要があるが、Rakuは指定しないことで2N通りすべてを(lazyに)列挙してくれるので、その点でも縮んでいる。EFは手つかず。Fは現在の最短コードがアルゴリズム的にかなり上手いようだが、読解していない。

深夜、SRM805に出た。EMの2完で11位。Eが落ちまくったので、コーディングフェーズ終了直後から見たら順位が半分くらいになった。

https://community.topcoder.com/stat?c=round_overview&rd=18678

Eは気合い。端っこで動けなくなるケースは自力で気づけたが、サンプルに入っていて安心感がある。intの3つ組をmapに入れるのはかなり恐怖なので、2つ組に留めておいて、代わりにmapを9個くらい持った。入力を乱数で生成するが、生成方法の疑似コードと一緒にC++等の実装が提供されていたのもありがたかった。

Mは桁DPで、使える数字のうち最も左にあるものを使うという条件を入れることで重複を省ける。実装上は以前に出現したときのdp配列の値を引けばよいらしい。細かいことは考えずに実装したら大体のサンプルがあって、0始まりのケースを抜き忘れていたので抜くと全て合った。……簡単に言ったが、最初の段階で空文字列を抜くために答えから1引いていたのを忘れていて、サンプル1(答えが1になるケース)がずっと0になっていて困っていた。もっと別のケースを見ると1引いているのに気づけただろうが、答えが0になっているのを見るとどうしてもdp遷移のバグを疑ってしまう。

Hも読んだ。中点を列挙してどれだけ覆えるかbitsetで持ち、2つの中点ですべてを覆えるならマッチングみたいなことをして復元できそう、までは考えたが、中点と完全に重なる点の存在・マッチングの結果片方の集合が空になってしまう場合の検出がよくわからなかったので実装せずに終わった。後からkmjpさんの解説記事を読んだが、二部マッチングでよい理由も、片方の集合だけで完全に覆える場合をもとから考えなくていい理由もよくわからなかった。

TopCoder SRM 805 : Div1 Hard TwoGalaxies - kmjp's blog

朝方、しばらくコードゴルフをしてから布団に入り、「転生したらスライムだった件」を読み進めた。午前7時から午後1時半までかけて80話くらい読んで、さすがにまずいと思い就寝。

05/09(日)

午後8時半起床。今日はARCだが、開催時刻がいつもより1時間ちょっと遅いので、ゆっくりしていられた。

昨日の典型90問は、dfsの行きがけ順にソートした後両端をつなげて隣り合う2頂点間の距離を求めると、その半分が答えだったようだ。また、ソートして隣り合う2頂点のLCAを求めておくと、それ以外の点が必要になることはないらしい。これは、ある連続する3頂点をマージするとき、左の2頂点のLCAと右の2頂点のLCAはどちらも真ん中の頂点の親なので、その2つの間にも親子関係がある、ということを一般化するとわかる。

ARC118に参加した。4完で48位、パフォーマンス2762、レートは2712→2717(+5)で1だけhighestを更新した。

AtCoder Regular Contest 118 - AtCoder

Aから難しい。税抜き価格が100円増えると税込み価格は100+t円増えて、その間に被りはないので、t種類の金額が税込み価格として現れない。これを利用して探索範囲を狭め、残りを愚直に計算する。微妙に合わせるのに失敗し、10分くらいかかった。

Bはほとんど明らかなように感じられた。最初はB=\left\lfloor\frac{AM}{N}\right\rfloorとしておいて、足りない分どこに1足すかは足す前と足した後の差を見てソートして決める。しかし今書いていて気付いたが、一つの要素に補正として2以上の値を足すことがない、という事実については証明していなかった。

Cは、3*5*7*112*32*52*72*11を用意して、ほかに偶数かつ35711のどれかで割り切れるものを列挙した。

Dは、まず原始根を取って言い換えることで単純な足し算引き算の問題になることに気づいて興奮したが、実際はほとんど意味なし。a,bそれぞれの位数を{\rm ord}_a,{\rm ord}_bとしたとき(これは原始根を取らなくても計算できる)、{\rm lcm}({\rm ord}_a,{\rm ord}_b)\lt P-1ならば答えはNo。そうでない場合は、100マス計算みたいにして{\rm ord}_a \times {\rm ord}_bマスを埋めてみると、適当な長方形の範囲に重複なく全て出現していることがわかるので、そこをジグザグに辿る。この辿る部分は原始根を取ったところで見えるものではなかった。

提出するとREとWAが出た。オーバーフローを見つけたので、WAもこれだろうと思って提出しなおしたら、普通に間違っていたらしく再度WA。ジグザグに辿っても1に戻ってこれない場合があって、これは取った長方形を高さが奇数になるように置いて横にジグザグに辿ったときに発生する。P=2の場合を特別扱いすることにすると、P-1は必ず偶数になるから、長方形を取り直すことで必ず高さを偶数にできる。その処理を加えてAC。

Eは、サンプル1の2種類のマス目に経路数を書き込んで足し合わせてみたりしていたが、何もわからなかった。解説を読んだが、結局、順列を考えるというよりは、縦と横に被りがないような障害物の置き方と考えるほうがよくて、このとき自分の縦と横を見るdpが出てくるようだ。

コードゴルフ。Cは2*32*53*5のどれかで割り切れる数を列挙するだけでよく、RakuのJunctionがかなり効く。Bは適当にRuby

Aは面倒だと考えていたが、\left\lfloor\frac{100N-1}t\right\rfloor+Nという単純な式で書けてしまうらしく、気づいた時にはdcで提出されていた。この式について考えてみる。

まず、解説の周期100+tについて、そのうち具体的にどこがスキップされるのか考えると、\left\lfloor\frac{tA}{100}\right\rfloorの値が動いたところだと分かる。よって1\le k\le t番目のスキップはA=\left\lceil\frac{100k}{t}\right\rceilによって達成される。ここで、本来A円だったのが税込みでk円増えたということだから、実際にスキップされた金額はA+k-1=\left\lceil\frac{100k}{t}\right\rceil+k-1円となる。

さて、N番目にスキップされた値というのは、まずそこに至るまでに周期が\left\lfloor\frac{N-1}{t}\right\rfloor回繰り返されて、その次の周期における(N-1\bmod{t})+1番目のスキップによるものである。q=\left\lfloor\frac{N-1}{t}\right\rfloorr=N-1\bmod tと置いて立式してみよう。そこまでの周期による(100+t)qと、今注目している周期における\left\lceil\frac{100(r+1)}{t}\right\rceil+r+1-1を足せばよい。tq+r=N-1であることを考えると100q+\left\lceil\frac{100(r+1)}{t}\right\rceil+N-1になる。

\displaystyle 100q+\left\lceil\frac{100(r+1)}{t}\right\rceil+N-1=\left\lceil\frac{100tq+100r+100}{t}\right\rceil+N-1=\left\lfloor\frac{100(tq+r)+99}{t}\right\rfloor+N=\left\lfloor\frac{100N-1}{t}\right\rfloor+N

よって確かに答えが\left\lfloor\frac{100N-1}t\right\rfloor+Nとなることが分かった。

今週木曜日に応募したインターンだが、選考書類を提出するよう言われていたのだった。履歴書のwordファイルを落としてきたりして何とか錬成し、メールで送った。