週記(2021/06/28-2021/07/04)

06/28(月)

先週の週記を投稿してからの話。まずラノベの新刊チェックをした。そういう情報がまとまっているサイトで調べて、気になるものをhontoのサイトでほしい本に追加する作業。本屋では基本的にそれを見ながら本を探している。

今日の典型90問がツイートされた。今日は星2。まともにグラフを作るのは長くて、辺(u,v)(ただしu<v)についてdeg[v]++などした後、deg配列を見ればよい。あるいは、deg[v]の更新のタイミングで答えに±1するのでもよいだろう。後者をAWKで実装したら45Bになったので、これを自動で提出する設定にしておいた。

先週の典型077のコードゴルフをしていた。C++ACLを使う。自分の二部マッチングライブラリでも通るようだったが、それをわざわざ実装するのはやっぱり長くなりそう。自分のライブラリは蟻本の二部マッチングから下の記事を参考にちょっと高速化しているやつで、蟻本の実装そのままだと結構シンプルになるが、それで通るのかは確認していない。

snuke.hatenablog.com

しばらく頑張って縮め、現在報告されている最短コードを更新できたのだが、実はclimpetさんがツイートし忘れていただけですでにもっと短い解が存在するらしい。残念。

次に典型073のコードゴルフ。以前、今見ている頂点と同じ文字を持つ頂点であるかどうかだけ考慮すればよいという話を聞いていたので、そのようにして持つ値を2種類に減らす。正しい答えが出るようだったので適当に縮めたら、現在の最短コードを更新できた。

なろうを1作読んだ。「世界から天才音楽家と呼ばれた俺だけど、目が覚めたら金髪美少女になっていたので今度はトップアイドルとか人気声優目指して頑張りたいと思います。」というやつ。以前TLで流れてきて、そこそこ好きそうな設定だったので後から読もうと思っていたもの。

https://ncode.syosetu.com/n2658gz/

いざ読んでみると、30話ちょっとですでにエタっていた。セリフのノリもあまり肌に合わなかったので、連載が続いていても読み通せたかは謎。内容については、風呂敷を広げる段階で途切れているので何とも言えない。

今日の典型90問がAtCoderに公開され、自動で提出したコードがちゃんとACできていた。しかし即座にbash 43Bが報告される。どうやらsort|uniq -uで1回しか出現しない要素を得るのが強かったらしい。悔しいのでしばらく考えていたが、Rakuを使用することで40Bまで縮んだ。各行2つの値のmaxを取るのもかなり短いし、出現頻度のカウントはbag一発でできる。1回しか出現しない要素だけ抜き出すというのは、対称差集合を用いて[(^)] listでも求まるようだったが、65536要素以上のlistを適用することができないらしくREしてしまった。REしなくてもTLEになるかもしれない。

ラノベを1冊読んだ。「VTuberなんだが配信切り忘れたら伝説になってた」。元はハーメルンで、ハーメルンから書籍化というのはあまり聞かない(最近偽聖女クソオブザイヤーが書籍化発表されたくらいか)のでびっくりしていたが、帯を見るにマルチ投稿しているカクヨムからの書籍化だったらしい。ちゃんと調べると偽聖女クソオブザイヤーもカクヨムとマルチ投稿だった。以前ハーメルンで読もうとしたときは序盤でページを閉じてしまったが、今回本になったことで再挑戦。

文章としては、ところどころに例のアレネタが挟まれており、商業として大丈夫なのか心配になるような人を選ぶものだと思うが、内容は面白かった、あるいはやけに惹きつけられた。主人公の人柄のくだりは好ましいし、ほかのVTuberとの絡みも微笑ましく感じられる。VTuberにハマる人はそういう関係性にも惹かれているのだろうか。この本を読んで、一度VTuberを見始めると抜け出せなさそうだと感じたので、これからはもうちょっと慎重に距離を置きたい。空想のVTuber(?)はよいが、現実に存在するVTuberにのめりこむのはまずい。

午後7時就寝。

06/29(火)

午前2時半に目を覚ます。

毎週午前3時にClassroomに講義資料を投稿する教員がいて、親近感を感じている。

週記(2021/06/21-2021/06/27) - kotatsugameの日記

今週もピッタリ午前3時だった。これは毎週その時間帯に活動しているということで、むしろ生活リズムが安定している側の人だったらしい。

なろうを読んだり動画を見たりして、午前7時前にまた寝落ち。次、午前10時半に起きた。

今日の典型90問を解く。左上から貪欲でよさそう。コードゴルフ的にはかなり面倒そうなので、あとは実際にジャッジが公開されてからということにする。

まだ寝足りない気がしたので、眠気を求めてずっと布団でスマホを触っていたが、どうにも眠れなさそうだったので、諦めて起きた。

大学院について調べてみた。あまり住環境を変えたくないという思いがあるので、東北大学の院に進学したい。あとはまあ、競プロに近いことができればいいなと考えて「情報科学研究科」というところを調べてみた。研究室一覧を見てかなり興味がわいたが、出願の方法を確認すると、ほとんどの研究室でTOEICなどの試験の記録が必要らしい。ないので、もう無理。

おとなしく数学科の院に行くことになるだろう。こちらは試験の記録は必要ないようだ。だから周りでTOEICの話を聞かなかったわけなんですね。

今日の典型90問が公開された。問題文をよく読むと、操作回数の最小化をする必要があってちょっとびっくりするが、冷静になると貪欲でよいことの理由から最小化にもなっていることがわかるので、よい。オーバーフローの危険性に気づけたのもよかった。実際、現在存在するテストケースにおいては、配列の値は収まるが答えの値はオーバーフローしてしまうようだ。コードゴルフとしては、Yes・Noのチェックをどれくらい行うかも重要。いろいろ試してみたところ、僕の実装だと一番右下が非ゼロかどうかを見ればよいことになった。正当性はわからないが、ACしているのでこれでよい。Ruby 134Bで満足していたが、実はPerlで書き直すともっと縮む。97Bになった。

先週の土日にyukicoderでコンテストがあったが、その時間は眠っていた。upsolveをする。

灘校文化祭コンテスト 2021 day1 - yukicoder

灘校文化祭コンテスト 2021 day2 - yukicoder

まず1日目から。Aはよい。Bは真面目に解いたが、提出する段階になって実はだいたいYesではないかと感づいた。実際、最短コードを見てみるとN=1のときだけNoらしい。Cはソートする。DはBFS。Eは、任意の2x2領域の和が0で、3つ斜めに並んだマスの和が1であることに気づけば、(1,1),(1,2),(2,2),(2,3)の4マスを決め打つことで残りのマスを決めていける。実際10x10のマスを生成するコードを書いて確認すると、すべてのマスが1である場合以外は条件を満たさない5x5の正方形領域が存在するようだった。

ここでコードをいったん消してN\le 4の場合は2^{N^2}の全探索、N\gt 5の場合は全マス1の場合だけ調べるコードを書いたが、WA。冷静になって先ほど書いた実験コードの出力を確認すると、5x5、6x6の場合はギリギリ矛盾しないような決め方が他に存在することに気づいた。このサイズだとマスの全探索はできず、しかし実験コードは消してしまったので、泣きながら再度同じコードを書いてAC。コンテスト中に書いたコードは消さないようにしよう!実はこれ毎月のペースでやってます。

Fから解けないので、2日目に移った。Aは周期N+1の数列になる。Bはどこかで見たことのあるような、適切な比較関数でソートするやつ。

Cを考えていたがWAが取れず、そのうち椅子でちょっと寝てしまったので、これはまずいと布団に移動して再度寝た。午後10時だった。

06/30(水)

午前1時半くらいに一瞬起きたらしい。またすぐに寝て、次に午前5時半に起床。月曜日に縮めた典型073が縮め返されていた。

昨日の続き、C問題を解いた。昨日の時点で分かっていたことは、Tが偶数なら頂点1に接続する辺の重みを\frac T 2とすることで達成可能であること、TNの倍数ならすべての辺の重みを\frac T Nとすることで達成可能であること、またN=3の時は常に達成可能であることの3つ。このうち解法に関係するのは1番目の考察のみであった。

1番目の考察とは逆に、頂点1に接続しない辺の重みを\frac T{N-2}とすることでも達成可能である。これはN=3の時常に達成可能であることの理由となる。さて、これらを別個に考えてもWAは変わらなかった。実はこれらは組み合わせることができる。つまり、すべての辺の重みが0であるグラフを考え、ここに辺の重みを足して求めるグラフを構築することを考えると、サイクルの重みに2加えることとN-2加えることが独立に行えるということ。2つを組み合わせるとN加えることは可能なので、これは考えなくてよい。

つまり、T=2k+(N-2)lとなるような整数k,l\ge 0が存在すれば構築できるということで、これを調べたら通った。ちゃんとすべての場合が尽くされているかはよくわからないので解説を読んだ。Nが偶数のとき奇数のTが達成できないことの証明は面白かった。T=1で構築できないこともよい。あとはN=7T=3のとき作れないことを調べる必要があるが、解説では全探索していてびっくりした。まあ言うだけならそういうものか。

Dはサイコロ問題だった。これを機会にサイコロライブラリを作ろうと思ったが、設計をどうするかなどいろいろ悩みどころがあるので、後回し。ここで、あさかつの並走者を募集するツイートを見かけたので、yukicoderを途中で切り上げて参加してみた。

当然全問解いたことがあるわけで、単純に出るのでは面白くなかったのでPythonを使ったのだが、思ったより遅くてびっくりした。PyPyで出しなおしてAC。大体の場合は最初からPyPyで出すようにしたほうが良いのだろう。Pythonのほうが速くなるケースもあるという話は聞くが、そのあたりまで調べて覚えておくほどPythonを使う動機はない。

最終的に、定数倍高速化を頑張ってすべての問題をPythonで通しておいた。

atcoder.jp

全然通らなかったので、ほかの提出を参考に二分探索の判定関数だけ切り出したらかなり速くなった。その状態で6回くらい投げたら通った。

今日の典型を読む。すんなり包除原理が思いつけてよかった。

yukicoderのupsolveに戻る。E問題は総和記号をいろいろ分解すると1\le i\le mに対して\left\lfloor\frac n i\right\rfloorが分かればよいので、商の値でまとめて遷移するコードを書いた。前は苦手意識があったが、「\left\lfloor\frac n i\right\rfloor=rとなる最大のii=\left\lfloor\frac n r\right\rfloorである」ということを念頭に置くとだいぶ見通しが良くなった気がする。Fは星5だしsolved 2なので読みすらしなかった。

さらに、コンテストとは別に問題が追加されていたので、2問解いておいた。

No.1576 織姫と彦星 - yukicoder

No.1577 織姫と彦星2 - yukicoder

どちらもBFS。前者は簡単で、各頂点からは毎回全頂点に対して遷移できるか調べる。後者はこの遷移を高速化する必要があるが、ハミング距離1の頂点を調べればよいということで、どのビットが異なるかだけ全探索してmapなどで頂点番号を求めればよい。

学食に行ったり本を読んだりしているうちに今日の典型のジャッジが公開されていたので、解く。問題なくAC。そのままRubyコードゴルフもしたが、1900ms台と結構ギリギリだった。105B。

ゲーセンに行く。今日は夕食・本屋を挟んで午後3時から午後11時。進捗としては、RebellionでSSを出して、現在解禁してある14の未SSが混沌だけになったことと、13のAJが3譜面出たこと。これで13のAJが99譜面になったので、100譜面目としてHalcyonをプレイしていたのだが、3時間くらい連奏しても出ずに閉店時間となってしまった。

最初はそこそこ押せていたのに、連奏し続けるといたるところに癖がつく。擦りなどを交えてごまかしていたが、「ちょっとヤバそうだけどまだ何とか押せていたところ」で緊張に負けて出してしまった。そういうことが何回かあったが、そのあとも最後まで通ってしまうと特別辛い。ちなみにこの部分はこの後、左手2鍵で押していたのを右手2鍵に変えた。

閉店間際はここがマジで通らなくなった。AJ動画など見ると、いったんスライドを離して素早く流すのがよさそう。僕も今日の始めのほうではちゃんとできていたはずだったが、スライドを離すタイミングを見失った結果全然ダメになった。もしくはタップスライドの速さが違うのかもしれない。

疲労困憊して帰宅。何とか風呂に入り、洗濯機を回した。日記をつけようと思ったが、タイプしている最中に瞼が下りていって、本当のブラインドタッチをしていることに気づく。さすがにまずいと思い、何とか洗濯物を干して即座にベッドに倒れこんだ。即座に就寝。午前1時半だった。

07/01(木)

正午、起床。今日の典型90問はちょっと考えたが、2次元平面にプロットして正方形領域の和をとればよい。

食事してゼミをした。ゼミの間に日記を書いたりしていた。今日も1コマぶんの時間で終わり。二項係数が絡む等式の証明に微分が登場してびっくりした。総和記号の中に現れるk^nという項を消すために、k^n=\left.\left(x\frac{dx}x\right)^n x^k\right|_{x=1}という式変形を行っていた。これでkが指数に行き、二項定理を用いることができるようだ。

今日のゼミは1コマ分で終わり。来週もそう。

週記(2021/06/21-2021/06/27) - kotatsugameの日記

ゼミが終わってからもしばらく日記を書いていたが、午後5時くらいになって典型90問のジャッジが公開されたため、通しておいた。

月が変わったので6月の読書記録をツイートした。先月は、何度か週記に書いていたように、なろうにすべてを破壊された月だった。なろうばっかり読んでいてラノベを読んでいないからと言って新刊を買わない理由にはならないので、積読は増える一方である。なろうを読んだ量を記録することも考えたが、難しいし、第一なろうと商業の小説では文章を読むにあたっての精度が違う。結局、文章自体は先月もたくさん読んだが、記録には表れない。

典型90問のコードゴルフを少し行う。スクリプト言語だと通りそうになかったので、C言語コードゴルフして205B。

本を1冊読んだ。「私立シードゥス学院」2巻。全寮制の学園で、寮が複数あってそれぞれ特色があったりし、コテコテの設定が面白い。基本3人称で描かれるが、微妙に各人の内心が入り混じって変な感じがするのと、セリフから発話者の区別がつきにくいので読みづらさはある。日常の謎ミステリとしていい感じだが、帯に「水平思考ミステリ」と書いてあるのがよくわからない。

確かに1話1話、それっぽい問題が最初に書かれていて、それに沿うような形で問題編が描かれ、次に解決編に進むというような構成になっているので、水平思考ゲームを意識してはいるのだろう。しかし日常の謎が水平思考ミステリに翻訳できるというのは、それは当たり前のことではないだろうか?ちょっと特殊なシチュエーションから意図的に情報を抜くことで不可解な状況を作りだす、というのが水平思考ゲームの問題作成であると考えているので、それに照らしてみれば日常の謎を水平思考ゲームの題材として扱うのはほとんど常に可能なように思われる。この本が何か特別なことをしているようには感じられず、帯に特別「水平思考ミステリ」と書くことの意味が見いだせなかった。

と、ちょっと難癖をつけたが、話としては良いと思う。今巻は寮長という存在にスポットライトを当てているようで、各寮の特色を体現している寮長というのも先に述べたようにありがちな設定だが、だからこそ面白い。

さらにラノベを読み始めたが、今日が期限だった論理学のミニットペーパーに気づいた。講義動画を適当に飛ばしつつ見て提出しようと思ったのだが、今日の内容はなんだか哲学的でよくわからなかったというのが正直なところ。Yes・Noで答えられるようなありとあらゆる質問に答えられる機械は意味を理解していると言えるだろうか?という話だった。その部分の講義動画を飛ばさずに見ても、特にコメントが見つからない。しばらくウンウン唸り、画像認識の機械学習シベリアンハスキーと狼を見分けさせるときに教師データに偏りを持たせると、背景の雪の有無で区別するようになった、という話を書いて提出した。つまり、機械に我々が思う意味を伝えることができていない、ということを言っているつもり。何を書いても的外れな気がして非常に苦労した。

今日の典型90問がRubyで通されていた。通らないと思ったのだが……。実際、通ることを知った今もどうやって通しているのかわからないので、勝てない。

椅子で一瞬寝てしまったので、布団に移動して本格的に寝た。午前0時半就寝。

07/02(金)

午前4時半起床。昨夜読み始めたラノベを読んで、午前7時くらいに再度就寝。その次は午前11時に起床した。

昨日シャワーを浴びていないだけなのに頭皮がかゆくてたまらない。シャワーを浴びると多少目が覚めたので、ゴミを出して学食に行き、さらに床屋にも行った。

相手はマスクをつけながら髪の毛を切っているわけだから、話しかけられるのはまあ良いのだが、こちらはマスクを外しているのに受け答えしてよいものか困る。まあ無言だと社会性がヤバいので頑張って会話するのだが、相手方はマスクもつけず喋り散らかす自分をどう思っているのだろうか。まあうっかりコミュニケーション能力がありそうな振る舞いをしてしまった自分に非がある。

帰ってきたら今日の典型90問のジャッジが公開されていた。今日のはまあどうやっても解けそうではあるが、短くする方法は特に思いついていない。とりあえず通して、次に昨日の典型を再度考え直していた。昨日は二次元累積和を取ることしか考えていなかったが、二次元imosで計算することで多少コードが縮むようだった。Cで196B。Rubyには全然勝てていないし、計算量がよくなったわけでもない。

今日の典型90問のコードゴルフを行う。まずRubyで書いて、次いでVimRubyコードを構築する方法で縮めたが、dcで通るのでそれが一番短くなる。10のべき乗をどこまで考えるか、ということについてはループを回していたが、実は桁数を得るコマンドZを用い、等比数列の和を求めることで閉じた形で書き表せることに気づいた。これで大幅に縮み、最終的に41Bになった。Zは0に適用すると1を返す、つまり0の桁数は1であるという風になっていて、視覚的には正しいが数学的にはあまりうれしくないように感じられる。実は変形の過程で(0,R]-(0,L-1]ではなく[1,R+1)-[1,L)の値を求めるように変わっており、Zを使っても一貫性のある値が得られたというわけ。

ラノベを読んだ。「史上最強オークさんの楽しい種付けハーレムづくり」5巻。ひどい題名なのであまり公然とは言及できないが、内容はテンプレ異世界転生チーレム無双なので、面白くないということはない。

今日のサークル解説会の準備をする。今日はABC207-Fの2乗の木DPを扱うことにした。

僕が知っているのは計算量T(N)T(N)がT(l+r)=T(l)+T(r)+lrT(l+r)=T(l)+T(r)+lrを満たすことからT(N)=O(N2)T(N)=O(N2)を示す方法で、シンプルだがなんだか騙された感があった。細かい理論を知らないからかもしれない。

週記(2021/06/21-2021/06/27) - kotatsugameの日記

これについて、もうちょっと精密に理解したいと思い、自分で実際に計算することにしてみた。計算回数、あるいは計算ステップ数f(N)を漸化式で表してみて、帰納法ですべてのNに対しf(N)=O(N^2)を言えたと思う。子の数が2つではなく、より一般の場合についても詳しく計算してみた。帰納法の下りはかなり天下り的であるようにも思えるが、f(l+r)=f(l)+f(r)+lr(l+r)^2=l^2+r^2+2lrの類似性で十分気持ちは伝えられるのではないだろうか。

それらを含めてF問題のスライドを作ったらもう疲労困憊になったので、今週はこれだけ発表することにした。

2021/07/02 定例会 | puzzleknot 公式サイト

yukicoder 302に出た。6完。

yukicoder contest 302 - yukicoder

Aは紙でちょっと実験して、3つの数それぞれはよくわからない振る舞いをしたが、全体の積としてみれば毎回2乗されているだけだとわかる。冷静になってみれば、確かにそう。Bも手で実験したが、ミスで1WA。正解は奇数Aに対し(A,A)または(A,A+1),(A+1,A)が負け状態。Cは面倒そうだったがそれっぽいことを書いたら一発で合ったので良かった。DはDP。約数・倍数関係を、因数を掛けたと考えると、数列の総和をキーにして遷移できる。Eは最初、二部グラフにして小さいほうの集合のサイズが答えだと思ったが、提出の直前に黒をわざと連続させることでところどころ入れ替えられることに気づいた。実際出してみるとほとんどのケースでWA。適当に木DPを書いたら通った。Fは、とりあえずソートするまではよくて、そこからしばらく考え込んでいたが、DPのキーと値を入れ替えるだけだった。気づくのが遅すぎた。

Gを考えていたら椅子の上で少し寝てしまったので、布団に移動して再度寝た。午後10時。

07/03(土)

午前3時くらいに目を覚ました。atgolferで更新があったので見てみたところ、昨日の典型と同様、ループを回していたところを桁数と等比級数の和で閉じた形にするテクで縮んだようだ。

これまでは毎回式変形で考えていたが、これは直感的な説明でよい。

ラノベを読んだりなろうを読んだりして、朝になった。今日の典型90問はグラフの隣接頂点を調べるのを高速化する問題で、適当にしきい値を定めて「周りからもらう頂点」を作るのがよさそう。実際、しきい値Kとしたとき、次数がK以上の頂点は周りからもらうことにし、その後自分に隣接する頂点であって次数がK以上の頂点(これは前計算しておく)に伝播する。次数がK未満の頂点は毎回周りを見て更新するので、更新はO(1)またはO(K)、伝播については次数がK以上の頂点が高々\frac{2M}K個しかないことからO\left(\frac M K\right)とわかって、合わせてK=\sqrt{2M}とすると最小になる。クエリ回数が105の2倍なのでかなり重そうだが、間に合うことは確かだろう。

午前9時就寝、午前11時半起床。今日は院試説明会がある。

正午からだと思って急いで食事したが、実は午後1時からだったらしい。思いがけず時間が空いたので、シャワーを浴びたり、早々にジャッジが公開された典型90問を通したりしていた。今日の典型90問はやはり重いらしく、しきい値K=650\sim\sqrt{2\times2\times10^5}で提出したが600ms弱くらいかかっている。

カメラを映すことを求められるかもしれないので、一応ノートパソコンを出して壁が背景になるように座っておいた。午後1時ちょっと前にZoomに入り、説明会が始まる。あんまりかしこまった場でもなさそうだし、こちらが何か発言を求められることもなさそうだったので、ラノベを読みつつ聞いていた。

いくつかの分野に分かれての懇親会で、僕は数学基礎論を選択したのだが、そこの計算機数学の先生の資料をもらって読んでみたところ、「グラフ理論」やら「ラムダ計算」といった見覚えがあるワードが並んでいて、非常に心躍った。このうちグラフ理論というのは、競プロで取り扱うグラフアルゴリズムとは話が違いそうではあったものの、ラムダ計算だけでも十分魅力的である。ぼんやりと数学基礎論に興味を持っていたが、特に出願の際はこの研究室を希望したいと考えた。

午後3時半ごろに懇親会も終了。ほとんど同じタイミングで読んでいたラノベを読み終えた。「転生魔王の大誤算」3巻。

主人公の魔王は自分がメチャクチャ強いのを自覚しておらず、周りにナメられないように必死になって頑張っていて、周りはメチャクチャ強い魔王様を信奉しているという設定。

週記(2021/01/25-2021/01/31) - kotatsugameの日記

魔王なら魔王らしく泰然自若としていてほしいと感じるが、そういう何のひねりもない魔王像はもはやありきたりすぎるのかもしれない。

週記(2021/01/25-2021/01/31) - kotatsugameの日記

相変わらずナヨナヨした魔王に思うところはあるが、基本的に面白く読んでいるので、面白いのだろう。

懇親会が終わってからずっと日記をつけていた。

橙diffを3問解いた。

D - 見たことのない多項式

前に見て、ラグランジュ補間のライブラリを作るきっかけになったが、verifyだけしてこちらの問題には提出していなかったらしい。貼るだけ。

E - RGB Sequence

これは数回考えて解けなかった記憶がある。今日の解法ガチャは大当たりだった。最後に出現したRGBの位置をキーにしてdpするとよい。

D - 旅行会社高橋君

2辺連結成分分解する。した後も木の任意の2頂点間の距離を求めるクエリに答える必要があり、それはライブラリになっておらず毎回書いているが、かなり面倒。蟻本のLCAの実装を使っているが、これはdfsした後parentの配列をダブリングで求める必要があって、手数が多いと感じる。ので、それのライブラリを整備することにした。Library Checkerを探すとズバリLCAを答える問題があったので、これをverifyに使う。

library/LCA.cpp at master · kotatsugame/library · GitHub

そういえば、こういう頻出のライブラリを整備していないのには理由があって、グラフや木を表現する構造体をちゃんと設計してから、それに沿うように作りたいという思いがあった。現状では、強連結成分分解や2辺連結成分分解といった分解後のグラフにも興味があるものは、隣接リストをvector<vector<int> >で返すようにしている。LCAも隣接リストの形で受け取れるようにするのがよいかと思ったが、現状はadd_edgeだけ実装してある。同じ辺を2回張るとまずいので、隣接リストからLCAを構築する際は気を付ける必要がある。辺(u,v)についてはu\lt vである場合だけadd_edgeを呼ぶのがよいだろう。

CF #729 div.2に出た。5完。

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

Aはよい。Bから難しいが、bを足す操作は最後に行うことにしてよいので、結局aのべき乗がどれくらいになるかを全探索すればよい。a=1の場合がコーナーケース。Cは答えがk以上になる数を数えて足していく。これには{\rm lcm}(1\dots k)が関係してくるので、ループはすぐ終わってくれる。考えていることと求めるものが微妙にずれており、サンプルを合わせるのに手間取った。Dは面白い。ある+ xが最後まで残る場合の数を知りたくて、これはx以上か以下かを01にすればdpできる。xと等しい値には、インデックスの大小を使って大小関係を定めるのが良い。つまり、優先度付きキューに値とインデックスのペアを入れるような感じ。

E1は2つの列をまとめて挿入dp。数列の後ろから構築して、現在の大小関係と転倒数の差を管理する。あらゆるところを愚直に書いてO(N^5)。E2にはこれを高速化する方針で挑んだが、任意mod畳み込みを含むO(N^3\log N)で、手元で13secかかってしまいコンテスト終了。

E問題はそもそも2つの列をまとめて扱うのがよくなくて、転倒数と最初の項に対して残りの順列を数え上げた表を前計算し、2つ組み合わせるべきだったらしい。

今日9問解いて、これでRating Historyでの表示が7000ACに到達した。

布団に入ってなろうを読もうとしたが、非常に眠かったのですぐあきらめて就寝。午前2時だった。

07/04(日)

午前9時くらいに目を覚ます。ちょっとTLを見たりなろうを読んだりして、1時間もせず二度寝。次に午後2時に目を覚ました。もう一回寝ようと思って布団に転がりながらなろうを読んでいたのだが、今度は眠れず、結局午後5時くらいに布団を出た。

昨日の典型は、「次数が大きいほうの頂点に向かうように辺を向きづける」のでもいいらしい。確かに、向き付けた後にある頂点から辺がm本出ているならば、その先の頂点たちはすべて次数m以上であるから、m^2\le 2Mが成り立つ。つまり毎回の取得・更新がそれぞれO(\sqrt M)で行えるようになって、これでも計算量が改善されている。

橙diffを1問解いた。

E - Bichrome Spanning Tree

まず1回最小全域木を作ってみて、それで条件を満たさなかった場合は、例えば白く塗られた辺しか存在しないならば、別の辺を選んで全域木に入れる必要がある。この時、クラスカル法で最小全域木を作るならば、最初に選んだ辺を使うようにすると言い換えてもよい。この言い換えから、元の最小全域木に対して追加1本・削除1本しか変化しないことがわかる。このようにして辺を入れ替えたときの重みが最も小さいものを選びたい。ちょうどXになるためには、最小全域木で選んだ辺がすべて同じ色である他、辺を入れ替えたときの重みがより小さくなる辺についても同じ色である必要がある。逆に、より大きくなる辺の色は自由なので、そこが自由度になる。

辺を入れ替えた時の重みは、解説では最小全域木のパスに含まれる最大重みの辺を使って計算していたが、毎回最初に使う辺を選んでクラスカル法し直すだけでよい。こちらのほうが簡単。

今日の朝、TLでLGV公式というのを耳にして、資料を読んでいた。

https://www.ioi-jp.org/camp/2017/2017-sp_camp-kumabe2.pdf

この3ページ目にあるLGV公式の前提は誤っている(と思う)。反例も以下のツイートのように構成できているはず。このグラフでLGV公式と同様に行列式を求めると、[2,1,1;1,2,1;1,1,2]で4となるが、本来は0である。

[https://twitter.com/kotatsugame_t/status/1411650442996555776:embed#逆に「パスが交差しない場合恒等置換」が言えればよくて、これはijとパスj->k(ただしk

単純に考えるなら「i,j<k,lについてパス(i,k)とパス(l,j)が交差する」ことを前提にすればよいが、微妙に弱められる。変数が少なくなっているし、たぶん弱まっているはず。

逆に、パスの交差に関する条件を全部外せば、一般のDAGに対して始点N個と終点N個を1つずつ組にして交差しないパスで結ぶ場合の数が数え上げられるかと思ったが、置換の符号が負になりうるためダメだった。\bmod 2なら解ける。

ABC208に出た。5完。ABC全完streakは177から207まで、31で途切れてしまった。

AtCoder Beginner Contest 208 - AtCoder

Aはよい。Bは額面が倍数になっているため、大きいほうからどん欲に取ってよいというやつ。Cは適当にソート。Dは見た目に驚かされるが、実はワーシャルフロイドの途中段階を全部足せという問題になる。これはワーシャルフロイド法の証明で、kを固定してO(N^2)のループを回している部分は頂点kを通るパスを探している、ということを知っていればわかる。Eは桁DPで、積の形で書けるK以下の数は少ないので間に合う。if文のミスで、最終的に数字の積が0になる数をうまく数えられておらず1WA。

Fは解けなかった。今週木曜日の部分に書いたように\left(x\frac{d}{dx}\right)^Kを掛けるのが効くかと思ってずっと計算していたが、全然きれいな形にならなかった。

コードゴルフをする。A問題はコンテスト中に書いたdcが最短。2回比較を行うが、1回目の比較に成功したら必ず2回目の比較に失敗するようにしている。つまり(a||b)==a+bみたいな感じか。スタックに出力を積み、その上にゴミを積んでrで適切な出力を持ってくる、という方針なので、比較に2回成功してしまうのはまずい。

Bもdcだが、最初に書いていた階乗を生成して大きいほうから割っていくコードからかなり変わった。基数が変わる階乗進法(?)のようなものを考えると、P2で割った余りが1桁目にきて、\frac P 23で割った余りが2桁目にきて、……という風になる。つまり毎回割っていくことで階乗を生成する必要がなくなり、大変に縮んだ。これはしーあるさんのコードを読んで気づいた解法。

atcoder.jp

Cは取り合えずPerl。先週見たテクを使っている。大きな数の整数除算で誤差が発生するらしく、いちいち余りを引いているのが気になるところ。

インデックスを、対応する値を比較してソートしたい。これはPerlでやるよりbashでやったほうが短い。

週記(2021/06/14-2021/06/20) - kotatsugameの日記

DはOctave。ワーシャルフロイドを行う問題はOctaveが強く、実際同様の最短コードは複数存在する。ところで今日のワーシャルフロイドはN\le 400だった。これまでのワーシャルフロイドを使用する問題は、古い問題が多いということもあるだろうが、僕が知る限りN\le 300だったので、ここにきて一段階制約が上がった感じ。実際今の最短コードは入力部で縮む余地がありそうだったが、提出してみるとTLEしてしまった。

F問題を通す。「補間」というワードを知ってしまい、すでにげんなりしているが、どのように補完するのかは自分で考えておきたい。maspyさんの記事を読んで頑張る。

maspypy.com

まず、コンテスト中にf(N,M)=\sum_{i=0}^N i^K \binom{N+M-i-1}{M-1}となることはわかっていた。これはf(n,m)のテーブルを見ると上のマスと左のマスを足していることになり、m=0のマスそれぞれの寄与を考えるとわかる。ここでa_n=n^K \binom{N+M-n-1}{M-1}と置くと、これはnK次式とM-1次式(nが関係する項をM-1回掛け合わせているため)の積で合わせてK+M-1次式とわかる。f(N,M)=\sum_{i=0}^N a_iより、和を取るので次数が1上がり、f(N,M)NK+M次式となる。

これでもよいが、f(n,m)のテーブルにおいてm\leftarrow m+1としたとき、累積和を取っているということに気づけば、m=0K次式からM回累積和を取るのでK+M次式、とただちに言えてしまう。こちらのほうがシンプルか。

次数が分かれば、あとはラグランジュ補間で解ける。補間としては多項式から補間するものと線形漸化式から補間するものの2つあると思っていて、後者はライブラリを持っていないため、それに帰着されたらどうしようと考えていたが、無事ラグランジュ補間で解けた。最初のK+M+1項を計算するのは、毎回a_nを計算して足していけばよい。こちらは普通に計算しても各要素につき二項係数のO(M)で解説と同じ計算量になり、その二項係数をずらす感じで定数時間で計算することにより多少オーダーが改善される。

これで今日AtCoderで7問解き、3000ACを達成した。本当は昨日の7000ACと合わせたかったが、そのために何かするのもなあということでこんな感じになった。

朝方、日記を書き終わったので投稿しようと思ったが、今日から典型90問のジャッジが必ず朝に公開されることになっていたので、それを解くことにした。時間までは昨日の典型90問のコードゴルフをしていたが、なんの進捗も得られなかった。233B。今日232Bから更新されているので、多分朝のところに書いた「次数が大きいほうの頂点に向けて向き付ける」ことで縮んだと思うのだが、縮む前のコード長にすら届いていない……。

解いて通したら1位になったのでFA獲れたかと思ったが、これまで全問ACしている人の中で最速だっただけで、FAはまた別の人だった。残念。内容に言及しようとしたが、もうすぐこの日記を公開するため、何も書けないことに気づいた。いよいよ来週で終わりである。来週日曜日に全提出が公開されるので、多分しばらくはコードゴルフしっぱなしになるだろう。