06/28(月)
先週の週記を投稿してからの話。まずラノベの新刊チェックをした。そういう情報がまとまっているサイトで調べて、気になるものをhontoのサイトでほしい本に追加する作業。本屋では基本的にそれを見ながら本を探している。
今日の典型90問がツイートされた。今日は星2。まともにグラフを作るのは長くて、辺(u,v)
(ただしu<v
)についてdeg[v]++
などした後、deg
配列を見ればよい。あるいは、deg[v]
の更新のタイミングで答えに±1するのでもよいだろう。後者をAWKで実装したら45Bになったので、これを自動で提出する設定にしておいた。
先週の典型077のコードゴルフをしていた。C++でACLを使う。自分の二部マッチングライブラリでも通るようだったが、それをわざわざ実装するのはやっぱり長くなりそう。自分のライブラリは蟻本の二部マッチングから下の記事を参考にちょっと高速化しているやつで、蟻本の実装そのままだと結構シンプルになるが、それで通るのかは確認していない。
しばらく頑張って縮め、現在報告されている最短コードを更新できたのだが、実は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時半に目を覚ます。
— こたつがめ (@kotatsugame_t) 2021年6月28日
毎週午前3時にClassroomに講義資料を投稿する教員がいて、親近感を感じている。
週記(2021/06/21-2021/06/27) - kotatsugameの日記
今週もピッタリ午前3時だった。これは毎週その時間帯に活動しているということで、むしろ生活リズムが安定している側の人だったらしい。
なろうを読んだり動画を見たりして、午前7時前にまた寝落ち。次、午前10時半に起きた。
今日の典型90問を解く。左上から貪欲でよさそう。コードゴルフ的にはかなり面倒そうなので、あとは実際にジャッジが公開されてからということにする。
まだ寝足りない気がしたので、眠気を求めてずっと布団でスマホを触っていたが、どうにも眠れなさそうだったので、諦めて起きた。
大学院について調べてみた。あまり住環境を変えたくないという思いがあるので、東北大学の院に進学したい。あとはまあ、競プロに近いことができればいいなと考えて「情報科学研究科」というところを調べてみた。研究室一覧を見てかなり興味がわいたが、出願の方法を確認すると、ほとんどの研究室でTOEICなどの試験の記録が必要らしい。ないので、もう無理。
英語の試験をさっぱり受けていないので、競プロに関係ありそうな大学院は全滅しているらしい。完全に笑顔
— こたつがめ (@kotatsugame_t) 2021年6月29日
わからん。知らんうちに選択肢が狭まっているのは、何をも決められない僕みたいなやつにとってはいいことなのかもしれん
— こたつがめ (@kotatsugame_t) 2021年6月29日
おとなしく数学科の院に行くことになるだろう。こちらは試験の記録は必要ないようだ。だから周りでTOEICの話を聞かなかったわけなんですね。
今日の典型90問が公開された。問題文をよく読むと、操作回数の最小化をする必要があってちょっとびっくりするが、冷静になると貪欲でよいことの理由から最小化にもなっていることがわかるので、よい。オーバーフローの危険性に気づけたのもよかった。実際、現在存在するテストケースにおいては、配列の値は収まるが答えの値はオーバーフローしてしまうようだ。コードゴルフとしては、Yes・Noのチェックをどれくらい行うかも重要。いろいろ試してみたところ、僕の実装だと一番右下が非ゼロかどうかを見ればよいことになった。正当性はわからないが、ACしているのでこれでよい。Ruby 134Bで満足していたが、実はPerlで書き直すともっと縮む。97Bになった。
先週の土日にyukicoderでコンテストがあったが、その時間は眠っていた。upsolveをする。
灘校文化祭コンテスト 2021 day1 - yukicoder
灘校文化祭コンテスト 2021 day2 - yukicoder
まず1日目から。Aはよい。Bは真面目に解いたが、提出する段階になって実はだいたいYesではないかと感づいた。実際、最短コードを見てみるとのときだけNoらしい。Cはソートする。DはBFS。Eは、任意の2x2領域の和が0で、3つ斜めに並んだマスの和が1であることに気づけば、(1,1),(1,2),(2,2),(2,3)
の4マスを決め打つことで残りのマスを決めていける。実際10x10のマスを生成するコードを書いて確認すると、すべてのマスが1である場合以外は条件を満たさない5x5の正方形領域が存在するようだった。
ここでコードをいったん消して、の場合はの全探索、の場合は全マス1の場合だけ調べるコードを書いたが、WA。冷静になって先ほど書いた実験コードの出力を確認すると、5x5、6x6の場合はギリギリ矛盾しないような決め方が他に存在することに気づいた。このサイズだとマスの全探索はできず、しかし実験コードは消してしまったので、泣きながら再度同じコードを書いてAC。コンテスト中に書いたコードは消さないようにしよう!実はこれ毎月のペースでやってます。
Fから解けないので、2日目に移った。Aは周期の数列になる。Bはどこかで見たことのあるような、適切な比較関数でソートするやつ。
Cを考えていたがWAが取れず、そのうち椅子でちょっと寝てしまったので、これはまずいと布団に移動して再度寝た。午後10時だった。
06/30(水)
午前1時半くらいに一瞬起きたらしい。またすぐに寝て、次に午前5時半に起床。月曜日に縮めた典型073が縮め返されていた。
昨日の続き、C問題を解いた。昨日の時点で分かっていたことは、が偶数なら頂点1に接続する辺の重みをとすることで達成可能であること、がの倍数ならすべての辺の重みをとすることで達成可能であること、またの時は常に達成可能であることの3つ。このうち解法に関係するのは1番目の考察のみであった。
1番目の考察とは逆に、頂点1に接続しない辺の重みをとすることでも達成可能である。これはの時常に達成可能であることの理由となる。さて、これらを別個に考えてもWAは変わらなかった。実はこれらは組み合わせることができる。つまり、すべての辺の重みがであるグラフを考え、ここに辺の重みを足して求めるグラフを構築することを考えると、サイクルの重みに加えることと加えることが独立に行えるということ。2つを組み合わせると加えることは可能なので、これは考えなくてよい。
つまり、となるような整数が存在すれば構築できるということで、これを調べたら通った。ちゃんとすべての場合が尽くされているかはよくわからないので解説を読んだ。が偶数のとき奇数のが達成できないことの証明は面白かった。で構築できないこともよい。あとは、のとき作れないことを調べる必要があるが、解説では全探索していてびっくりした。まあ言うだけならそういうものか。
Dはサイコロ問題だった。これを機会にサイコロライブラリを作ろうと思ったが、設計をどうするかなどいろいろ悩みどころがあるので、後回し。ここで、あさかつの並走者を募集するツイートを見かけたので、yukicoderを途中で切り上げて参加してみた。
当然全問解いたことがあるわけで、単純に出るのでは面白くなかったのでPythonを使ったのだが、思ったより遅くてびっくりした。PyPyで出しなおしてAC。大体の場合は最初からPyPyで出すようにしたほうが良いのだろう。Pythonのほうが速くなるケースもあるという話は聞くが、そのあたりまで調べて覚えておくほどPythonを使う動機はない。
最終的に、定数倍高速化を頑張ってすべての問題をPythonで通しておいた。
全然通らなかったので、ほかの提出を参考に二分探索の判定関数だけ切り出したらかなり速くなった。その状態で6回くらい投げたら通った。
今日の典型を読む。すんなり包除原理が思いつけてよかった。
yukicoderのupsolveに戻る。E問題は総和記号をいろいろ分解するとに対してが分かればよいので、商の値でまとめて遷移するコードを書いた。前は苦手意識があったが、「となる最大のはである」ということを念頭に置くとだいぶ見通しが良くなった気がする。Fは星5だしsolved 2なので読みすらしなかった。
さらに、コンテストとは別に問題が追加されていたので、2問解いておいた。
どちらもBFS。前者は簡単で、各頂点からは毎回全頂点に対して遷移できるか調べる。後者はこの遷移を高速化する必要があるが、ハミング距離1の頂点を調べればよいということで、どのビットが異なるかだけ全探索してmap
などで頂点番号を求めればよい。
学食に行ったり本を読んだりしているうちに今日の典型のジャッジが公開されていたので、解く。問題なくAC。そのままRubyでコードゴルフもしたが、1900ms台と結構ギリギリだった。105B。
ゲーセンに行く。今日は夕食・本屋を挟んで午後3時から午後11時。進捗としては、RebellionでSSを出して、現在解禁してある14の未SSが混沌だけになったことと、13のAJが3譜面出たこと。これで13のAJが99譜面になったので、100譜面目としてHalcyonをプレイしていたのだが、3時間くらい連奏しても出ずに閉店時間となってしまった。
— こたつがめ (@kotatsugame_t) 2021年6月30日
— こたつがめ (@kotatsugame_t) 2021年6月30日
最初はそこそこ押せていたのに、連奏し続けるといたるところに癖がつく。擦りなどを交えてごまかしていたが、「ちょっとヤバそうだけどまだ何とか押せていたところ」で緊張に負けて出してしまった。そういうことが何回かあったが、そのあとも最後まで通ってしまうと特別辛い。ちなみにこの部分はこの後、左手2鍵で押していたのを右手2鍵に変えた。
このタプスラ置いた奴チュウニズムやったことないだろ pic.twitter.com/NNw7Mdjq0o
— こたつがめ (@kotatsugame_t) 2021年6月30日
閉店間際はここがマジで通らなくなった。AJ動画など見ると、いったんスライドを離して素早く流すのがよさそう。僕も今日の始めのほうではちゃんとできていたはずだったが、スライドを離すタイミングを見失った結果全然ダメになった。もしくはタップスライドの速さが違うのかもしれない。
疲労困憊して帰宅。何とか風呂に入り、洗濯機を回した。日記をつけようと思ったが、タイプしている最中に瞼が下りていって、本当のブラインドタッチをしていることに気づく。さすがにまずいと思い、何とか洗濯物を干して即座にベッドに倒れこんだ。即座に就寝。午前1時半だった。
07/01(木)
正午、起床。今日の典型90問はちょっと考えたが、2次元平面にプロットして正方形領域の和をとればよい。
食事してゼミをした。ゼミの間に日記を書いたりしていた。今日も1コマぶんの時間で終わり。二項係数が絡む等式の証明に微分が登場してびっくりした。総和記号の中に現れるという項を消すために、という式変形を行っていた。これでが指数に行き、二項定理を用いることができるようだ。
今日のゼミは1コマ分で終わり。来週もそう。
週記(2021/06/21-2021/06/27) - kotatsugameの日記
ゼミが終わってからもしばらく日記を書いていたが、午後5時くらいになって典型90問のジャッジが公開されたため、通しておいた。
月が変わったので6月の読書記録をツイートした。先月は、何度か週記に書いていたように、なろうにすべてを破壊された月だった。なろうばっかり読んでいてラノベを読んでいないからと言って新刊を買わない理由にはならないので、積読は増える一方である。なろうを読んだ量を記録することも考えたが、難しいし、第一なろうと商業の小説では文章を読むにあたっての精度が違う。結局、文章自体は先月もたくさん読んだが、記録には表れない。
6月の集計
— こたつがめ (@kotatsugame_t) 2021年7月1日
買った:14冊
読んだ:4冊
積読:+10冊
積読(累積):+44冊
典型90問のコードゴルフを少し行う。スクリプト言語だと通りそうになかったので、C言語でコードゴルフして205B。
本を1冊読んだ。「私立シードゥス学院」2巻。全寮制の学園で、寮が複数あってそれぞれ特色があったりし、コテコテの設定が面白い。基本3人称で描かれるが、微妙に各人の内心が入り混じって変な感じがするのと、セリフから発話者の区別がつきにくいので読みづらさはある。日常の謎ミステリとしていい感じだが、帯に「水平思考ミステリ」と書いてあるのがよくわからない。
確かに1話1話、それっぽい問題が最初に書かれていて、それに沿うような形で問題編が描かれ、次に解決編に進むというような構成になっているので、水平思考ゲームを意識してはいるのだろう。しかし日常の謎が水平思考ミステリに翻訳できるというのは、それは当たり前のことではないだろうか?ちょっと特殊なシチュエーションから意図的に情報を抜くことで不可解な状況を作りだす、というのが水平思考ゲームの問題作成であると考えているので、それに照らしてみれば日常の謎を水平思考ゲームの題材として扱うのはほとんど常に可能なように思われる。この本が何か特別なことをしているようには感じられず、帯に特別「水平思考ミステリ」と書くことの意味が見いだせなかった。
と、ちょっと難癖をつけたが、話としては良いと思う。今巻は寮長という存在にスポットライトを当てているようで、各寮の特色を体現している寮長というのも先に述べたようにありがちな設定だが、だからこそ面白い。
さらにラノベを読み始めたが、今日が期限だった論理学のミニットペーパーに気づいた。講義動画を適当に飛ばしつつ見て提出しようと思ったのだが、今日の内容はなんだか哲学的でよくわからなかったというのが正直なところ。Yes・Noで答えられるようなありとあらゆる質問に答えられる機械は意味を理解していると言えるだろうか?という話だった。その部分の講義動画を飛ばさずに見ても、特にコメントが見つからない。しばらくウンウン唸り、画像認識の機械学習でシベリアンハスキーと狼を見分けさせるときに教師データに偏りを持たせると、背景の雪の有無で区別するようになった、という話を書いて提出した。つまり、機械に我々が思う意味を伝えることができていない、ということを言っているつもり。何を書いても的外れな気がして非常に苦労した。
今日の典型90問がRubyで通されていた。通らないと思ったのだが……。実際、通ることを知った今もどうやって通しているのかわからないので、勝てない。
椅子で一瞬寝てしまったので、布団に移動して本格的に寝た。午前0時半就寝。
07/02(金)
午前4時半起床。昨夜読み始めたラノベを読んで、午前7時くらいに再度就寝。その次は午前11時に起床した。
まずいですよ! pic.twitter.com/yF2WWLv7YF
— こたつがめ (@kotatsugame_t) 2021年7月1日
昨日シャワーを浴びていないだけなのに頭皮がかゆくてたまらない。シャワーを浴びると多少目が覚めたので、ゴミを出して学食に行き、さらに床屋にも行った。
髪型の指定するときに笑いながら喋ってしまったため"そういう"人だと思われたらしく、その後ずっと話しかけられる羽目に……
— こたつがめ (@kotatsugame_t) 2021年7月2日
相手はマスクをつけながら髪の毛を切っているわけだから、話しかけられるのはまあ良いのだが、こちらはマスクを外しているのに受け答えしてよいものか困る。まあ無言だと社会性がヤバいので頑張って会話するのだが、相手方はマスクもつけず喋り散らかす自分をどう思っているのだろうか。まあうっかりコミュニケーション能力がありそうな振る舞いをしてしまった自分に非がある。
帰ってきたら今日の典型90問のジャッジが公開されていた。今日のはまあどうやっても解けそうではあるが、短くする方法は特に思いついていない。とりあえず通して、次に昨日の典型を再度考え直していた。昨日は二次元累積和を取ることしか考えていなかったが、二次元imosで計算することで多少コードが縮むようだった。Cで196B。Rubyには全然勝てていないし、計算量がよくなったわけでもない。
今日の典型90問のコードゴルフを行う。まずRubyで書いて、次いでVimでRubyコードを構築する方法で縮めたが、dcで通るのでそれが一番短くなる。10のべき乗をどこまで考えるか、ということについてはループを回していたが、実は桁数を得るコマンドZ
を用い、等比数列の和を求めることで閉じた形で書き表せることに気づいた。これで大幅に縮み、最終的に41Bになった。Z
は0に適用すると1を返す、つまり0の桁数は1であるという風になっていて、視覚的には正しいが数学的にはあまりうれしくないように感じられる。実は変形の過程でではなくの値を求めるように変わっており、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の日記
これについて、もうちょっと精密に理解したいと思い、自分で実際に計算することにしてみた。計算回数、あるいは計算ステップ数を漸化式で表してみて、帰納法ですべてのに対しを言えたと思う。子の数が2つではなく、より一般の場合についても詳しく計算してみた。帰納法の下りはかなり天下り的であるようにも思えるが、との類似性で十分気持ちは伝えられるのではないだろうか。
それらを含めてF問題のスライドを作ったらもう疲労困憊になったので、今週はこれだけ発表することにした。
2021/07/02 定例会 | puzzleknot 公式サイト
yukicoder 302に出た。6完。
yukicoder contest 302 - yukicoder
Aは紙でちょっと実験して、3つの数それぞれはよくわからない振る舞いをしたが、全体の積としてみれば毎回2乗されているだけだとわかる。冷静になってみれば、確かにそう。Bも手で実験したが、ミスで1WA。正解は奇数に対しまたはが負け状態。Cは面倒そうだったがそれっぽいことを書いたら一発で合ったので良かった。DはDP。約数・倍数関係を、因数を掛けたと考えると、数列の総和をキーにして遷移できる。Eは最初、二部グラフにして小さいほうの集合のサイズが答えだと思ったが、提出の直前に黒をわざと連続させることでところどころ入れ替えられることに気づいた。実際出してみるとほとんどのケースでWA。適当に木DPを書いたら通った。Fは、とりあえずソートするまではよくて、そこからしばらく考え込んでいたが、DPのキーと値を入れ替えるだけだった。気づくのが遅すぎた。
Gを考えていたら椅子の上で少し寝てしまったので、布団に移動して再度寝た。午後10時。
07/03(土)
午前3時くらいに目を覚ました。atgolferで更新があったので見てみたところ、昨日の典型と同様、ループを回していたところを桁数と等比級数の和で閉じた形にするテクで縮んだようだ。
ゆきこFのやつ、タスク i の所要時間が w_i で締め切りが時刻 w_i+s_i (までに完了してないといけない)だと思えて、締め切りw_i+s_i の早いタスクから優先的にやる気持ちになるってのを、むかし見てなるほどーってなった
— りーふ@競プロ (@leaf_1415) 2021年7月2日
これまでは毎回式変形で考えていたが、これは直感的な説明でよい。
ラノベを読んだりなろうを読んだりして、朝になった。今日の典型90問はグラフの隣接頂点を調べるのを高速化する問題で、適当にしきい値を定めて「周りからもらう頂点」を作るのがよさそう。実際、しきい値としたとき、次数が以上の頂点は周りからもらうことにし、その後自分に隣接する頂点であって次数が以上の頂点(これは前計算しておく)に伝播する。次数が未満の頂点は毎回周りを見て更新するので、更新はまたは、伝播については次数が以上の頂点が高々個しかないことからとわかって、合わせてとすると最小になる。クエリ回数が105の2倍なのでかなり重そうだが、間に合うことは確かだろう。
午前9時就寝、午前11時半起床。今日は院試説明会がある。
正午からだと思って急いで食事したが、実は午後1時からだったらしい。思いがけず時間が空いたので、シャワーを浴びたり、早々にジャッジが公開された典型90問を通したりしていた。今日の典型90問はやはり重いらしく、しきい値で提出したが600ms弱くらいかかっている。
カメラを映すことを求められるかもしれないので、一応ノートパソコンを出して壁が背景になるように座っておいた。午後1時ちょっと前にZoomに入り、説明会が始まる。あんまりかしこまった場でもなさそうだし、こちらが何か発言を求められることもなさそうだったので、ラノベを読みつつ聞いていた。
いくつかの分野に分かれての懇親会で、僕は数学基礎論を選択したのだが、そこの計算機数学の先生の資料をもらって読んでみたところ、「グラフ理論」やら「ラムダ計算」といった見覚えがあるワードが並んでいて、非常に心躍った。このうちグラフ理論というのは、競プロで取り扱うグラフアルゴリズムとは話が違いそうではあったものの、ラムダ計算だけでも十分魅力的である。ぼんやりと数学基礎論に興味を持っていたが、特に出願の際はこの研究室を希望したいと考えた。
午後3時半ごろに懇親会も終了。ほとんど同じタイミングで読んでいたラノベを読み終えた。「転生魔王の大誤算」3巻。
主人公の魔王は自分がメチャクチャ強いのを自覚しておらず、周りにナメられないように必死になって頑張っていて、周りはメチャクチャ強い魔王様を信奉しているという設定。
週記(2021/01/25-2021/01/31) - kotatsugameの日記
魔王なら魔王らしく泰然自若としていてほしいと感じるが、そういう何のひねりもない魔王像はもはやありきたりすぎるのかもしれない。
週記(2021/01/25-2021/01/31) - kotatsugameの日記
相変わらずナヨナヨした魔王に思うところはあるが、基本的に面白く読んでいるので、面白いのだろう。
懇親会が終わってからずっと日記をつけていた。
橙diffを3問解いた。
前に見て、ラグランジュ補間のライブラリを作るきっかけになったが、verifyだけしてこちらの問題には提出していなかったらしい。貼るだけ。
これは数回考えて解けなかった記憶がある。今日の解法ガチャは大当たりだった。最後に出現したR
、G
、B
の位置をキーにしてdpするとよい。
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を構築する際は気を付ける必要がある。辺についてはである場合だけadd_edge
を呼ぶのがよいだろう。
CF #729 div.2に出た。5完。
Dashboard - Codeforces Round #729 (Div. 2) - Codeforces
Aはよい。Bから難しいが、を足す操作は最後に行うことにしてよいので、結局のべき乗がどれくらいになるかを全探索すればよい。の場合がコーナーケース。Cは答えが以上になる数を数えて足していく。これにはが関係してくるので、ループはすぐ終わってくれる。考えていることと求めるものが微妙にずれており、サンプルを合わせるのに手間取った。Dは面白い。ある+ x
が最後まで残る場合の数を知りたくて、これはx
以上か以下かを01にすればdpできる。x
と等しい値には、インデックスの大小を使って大小関係を定めるのが良い。つまり、優先度付きキューに値とインデックスのペアを入れるような感じ。
E1は2つの列をまとめて挿入dp。数列の後ろから構築して、現在の大小関係と転倒数の差を管理する。あらゆるところを愚直に書いて。E2にはこれを高速化する方針で挑んだが、任意mod畳み込みを含むで、手元で13secかかってしまいコンテスト終了。
E問題はそもそも2つの列をまとめて扱うのがよくなくて、転倒数と最初の項に対して残りの順列を数え上げた表を前計算し、2つ組み合わせるべきだったらしい。
今日9問解いて、これでRating Historyでの表示が7000ACに到達した。
Solved By kotatsugame
— こたつがめ (@kotatsugame_t) 2021年7月3日
Topcoder: 79
Codeforces: 1350
AtCoder: 2993
AOJ: 1265
yukicoder: 1288
library-checker: 25
Sum: 7000
https://t.co/0nO54qH8aU
7000AC!!!
布団に入ってなろうを読もうとしたが、非常に眠かったのですぐあきらめて就寝。午前2時だった。
07/04(日)
午前9時くらいに目を覚ます。ちょっとTLを見たりなろうを読んだりして、1時間もせず二度寝。次に午後2時に目を覚ました。もう一回寝ようと思って布団に転がりながらなろうを読んでいたのだが、今度は眠れず、結局午後5時くらいに布団を出た。
昨日の典型は、「次数が大きいほうの頂点に向かうように辺を向きづける」のでもいいらしい。確かに、向き付けた後にある頂点から辺が本出ているならば、その先の頂点たちはすべて次数以上であるから、が成り立つ。つまり毎回の取得・更新がそれぞれで行えるようになって、これでも計算量が改善されている。
橙diffを1問解いた。
まず1回最小全域木を作ってみて、それで条件を満たさなかった場合は、例えば白く塗られた辺しか存在しないならば、別の辺を選んで全域木に入れる必要がある。この時、クラスカル法で最小全域木を作るならば、最初に選んだ辺を使うようにすると言い換えてもよい。この言い換えから、元の最小全域木に対して追加1本・削除1本しか変化しないことがわかる。このようにして辺を入れ替えたときの重みが最も小さいものを選びたい。ちょうどになるためには、最小全域木で選んだ辺がすべて同じ色である他、辺を入れ替えたときの重みがより小さくなる辺についても同じ色である必要がある。逆に、より大きくなる辺の色は自由なので、そこが自由度になる。
辺を入れ替えた時の重みは、解説では最小全域木のパスに含まれる最大重みの辺を使って計算していたが、毎回最初に使う辺を選んでクラスカル法し直すだけでよい。こちらのほうが簡単。
今日の朝、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である。
RT>この資料、LGV公式の前提条件が違っていそう。これだと証明にある「パスが交差しない場合恒等置換」が示せない。具体的には図のようなグラフが反例になる(と思った) pic.twitter.com/Rc4RxSHv33
— こたつがめ (@kotatsugame_t) 2021年7月4日
[https://twitter.com/kotatsugame_t/status/1411650442996555776:embed#逆に「パスが交差しない場合恒等置換」が言えればよくて、これはi 単純に考えるなら「 逆に、パスの交差に関する条件を全部外せば、一般のDAGに対して始点個と終点個を1つずつ組にして交差しないパスで結ぶ場合の数が数え上げられるかと思ったが、置換の符号が負になりうるためダメだった。なら解ける。 ABC208に出た。5完。ABC全完streakは177から207まで、31で途切れてしまった。 AtCoder Beginner Contest 208 - AtCoder Aはよい。Bは額面が倍数になっているため、大きいほうからどん欲に取ってよいというやつ。Cは適当にソート。Dは見た目に驚かされるが、実はワーシャルフロイドの途中段階を全部足せという問題になる。これはワーシャルフロイド法の証明で、を固定してのループを回している部分は頂点を通るパスを探している、ということを知っていればわかる。Eは桁DPで、積の形で書ける以下の数は少ないので間に合う。if文のミスで、最終的に数字の積が0になる数をうまく数えられておらず1WA。 Fは解けなかった。今週木曜日の部分に書いたようにを掛けるのが効くかと思ってずっと計算していたが、全然きれいな形にならなかった。 コードゴルフをする。A問題はコンテスト中に書いたdcが最短。2回比較を行うが、1回目の比較に成功したら必ず2回目の比較に失敗するようにしている。つまり Bもdcだが、最初に書いていた階乗を生成して大きいほうから割っていくコードからかなり変わった。基数が変わる階乗進法(?)のようなものを考えると、をで割った余りが1桁目にきて、をで割った余りが2桁目にきて、……という風になる。つまり毎回割っていくことで階乗を生成する必要がなくなり、大変に縮んだ。これはしーあるさんのコードを読んで気づいた解法。 Cは取り合えずPerl。先週見たテクを使っている。大きな数の整数除算で誤差が発生するらしく、いちいち余りを引いているのが気になるところ。 インデックスを、対応する値を比較してソートしたい。これはPerlでやるよりbashでやったほうが短い。 DはOctave。ワーシャルフロイドを行う問題はOctaveが強く、実際同様の最短コードは複数存在する。ところで今日のワーシャルフロイドはだった。これまでのワーシャルフロイドを使用する問題は、古い問題が多いということもあるだろうが、僕が知る限りだったので、ここにきて一段階制約が上がった感じ。実際今の最短コードは入力部で縮む余地がありそうだったが、提出してみるとTLEしてしまった。 F問題を通す。「補間」というワードを知ってしまい、すでにげんなりしているが、どのように補完するのかは自分で考えておきたい。maspyさんの記事を読んで頑張る。 まず、コンテスト中にとなることはわかっていた。これはのテーブルを見ると上のマスと左のマスを足していることになり、のマスそれぞれの寄与を考えるとわかる。ここでと置くと、これはの次式と次式(が関係する項を回掛け合わせているため)の積で合わせて次式とわかる。より、和を取るので次数が上がり、はの次式となる。 これでもよいが、のテーブルにおいてとしたとき、累積和を取っているということに気づけば、の次式から回累積和を取るので次式、とただちに言えてしまう。こちらのほうがシンプルか。 次数が分かれば、あとはラグランジュ補間で解ける。補間としては多項式から補間するものと線形漸化式から補間するものの2つあると思っていて、後者はライブラリを持っていないため、それに帰着されたらどうしようと考えていたが、無事ラグランジュ補間で解けた。最初の項を計算するのは、毎回を計算して足していけばよい。こちらは普通に計算しても各要素につき二項係数ので解説と同じ計算量になり、その二項係数をずらす感じで定数時間で計算することにより多少オーダーが改善される。 これで今日AtCoderで7問解き、3000ACを達成した。本当は昨日の7000ACと合わせたかったが、そのために何かするのもなあということでこんな感じになった。 AtCoder 3000AC pic.twitter.com/fAolpIy6x5i,j<k,l
についてパス(i,k)
とパス(l,j)
が交差する」ことを前提にすればよいが、微妙に弱められる。変数が少なくなっているし、たぶん弱まっているはず。(a||b)==a+b
みたいな感じか。スタックに出力を積み、その上にゴミを積んでr
で適切な出力を持ってくる、という方針なので、比較に2回成功してしまうのはまずい。
朝方、日記を書き終わったので投稿しようと思ったが、今日から典型90問のジャッジが必ず朝に公開されることになっていたので、それを解くことにした。時間までは昨日の典型90問のコードゴルフをしていたが、なんの進捗も得られなかった。233B。今日232Bから更新されているので、多分朝のところに書いた「次数が大きいほうの頂点に向けて向き付ける」ことで縮んだと思うのだが、縮む前のコード長にすら届いていない……。
解いて通したら1位になったのでFA獲れたかと思ったが、これまで全問ACしている人の中で最速だっただけで、FAはまた別の人だった。残念。内容に言及しようとしたが、もうすぐこの日記を公開するため、何も書けないことに気づいた。いよいよ来週で終わりである。来週日曜日に全提出が公開されるので、多分しばらくはコードゴルフしっぱなしになるだろう。