週記（2021/05/31-2021/06/06）

05/31(月)

午前7時、目覚める。午後3時までなろうを読んでいた。yukicoderに問題が追加されたらしいが、今は気にせず放置することにした。午後3時に再度寝落ちして、次に午後7時半に起床。

まず典型90問を解いた。今日は超頂点。うっかり01BFSをしたが、別に辺の重みをすべて1にして最後に2で割っても同じ値が出る。こちらはBFSでよい。コードゴルフはよくわからないのでしなかった。

昨日のABCのC、Eが縮められていた。このうちCはテストケースハックに成功してしまい縮んだ。Eはとりあえず放置。またA問題の最短コードも更新されていて、Vimの単語検索・移動を巧妙に使ってうまいことパターンを区別するコードが登場した。ABC155A-Poorでも同様のコードを見たし、コンテスト中もそれなりに考えていたのだが、どういう思考でこの操作を生み出すのか全然わからない。

atcoder.jp

atcoder.jp

典型90問の004は、これまではPyPyが最短になっていたが、Crystalで更新されていた。自分でも書いてみると確かに縮んで、また取り返すことができた。ロジックは変わっていない。

先週の週記を書き上げて投稿した。先週の平日は本当に一切の予定がなくて、一歩も家から出ずに思う存分生活リズムをぶち壊しながらずっとなろうを読んでいたらしい。振り返ってみればとんでもない一週間だった。またやりたいぜ。

AHC003の参加記を書こうと思って、下書きに初日の分だけ書き残しておいたのだが、結局それから1度もコードを書かずに終了してしまったので、内容は少しだけ週記に移して、記事のほうは削除した。

またコードゴルフをする。mapが頻発するコードは、無理やり同じ形をくくりだしてjoinしてからevalすると短くなるらしい。多分適用できるコードはいくつかあると思うが、このテクが使えるコードというのはおしなべて手順が多いアルゴリズムを採用しているため、その他の点でもまだまだ縮む余地があるだろう。ということで、探して縮めることは今回はしないことにした。

atcoder.jp

昨日のABCのE問題を見る。解説と同様の方針だが、わざわざX座標が同じ値を同時に処理しなくても、直前に見た点とそれによる集合の変化さえ覚えておけばよいらしい。これでRubyのコードが最短になっていたが、Perlでも書けたので縮んだ。その後取り返された。シェルスクリプトで各行に2つ値が書かれたものを数の組としてソートするとき、基本的には-k1n -k2nと書く必要があるようだ。ここで-nk1 -k2とすると、最初のオプション-nが-k2にも適用されるということで先と同じ意味になり、-1B。しかし-nとだけ書くと組の2つ目は辞書順ソートされてしまうらしく、ダメだった。かなりいびつに感じられるが、ここは縮まないのだろうか。

AHC003のシステスが終わったらしいので見に行くと、0点になっていた。びっくりして自分の提出欄を確認したところ、コードゴルフしていて最後に出したTLE解がシステス対象になってしまっていたらしい。これはかなりショック。自明解なので順位的には下のほうだが、しかし0点はちょっと恥ずかしい。

日付が変わってから午前5時くらいまでなろうを読んでいた。そのあとシャワーを浴びてゴミを出し、帰りしなに宅配ボックスから届いていた荷物を受け取った。

昨日Amazonで注文した商品が宅配ボックスに配達されたことを知ったが、取りに行くのは面倒だった。

週記（2021/05/24-2021/05/30） - kotatsugameの日記

また布団に戻って学食の麺コーナーが開店する午前11時半までなろうを読んだ。そろそろいい時間かな、と思って学食に行こうとしたが、ふとAtCoderを確認すると今日の典型90問が投稿されていたので、通してから行くことにした。とりあえずC++で全探索するコードを書いて提出したが、700msくらいあって嫌な予感がする。Rubyでcombination(5)を使って書いたら案の定TLEしてしまった。それではCrystalならば、と持ち出してきたが、こちらもTLE。PyPyもTLEした。

この時点でそう簡単にゴルフ出来ないことに気づき、先に学食に行くことにした。昼休みに入ると人だらけになって待ち時間が嫌なので、その前に食べ始める必要がある。なんとか昼休み10分前に学食にたどり着けた。食事して購買でブラックサンダーを箱買いし、帰宅。

典型90問のコードゴルフを続ける。mapでまとめてdpすることも考えたが、こちらも間に合わない。どうやら全探索するしかなくて、C言語を持ち出す必要がありそうだ。5重ループなど書いていられないから、再帰関数で実装することにする。入力部をまとめたり関数呼び出しのところで頑張ったりreturnを書かないようにしたりして、121Bのコードが出来上がった。相変わらずC言語はよくわからない。このコードは手元では動かないので、毎回コードテストで試すことになるが、ちょうど出力の末尾に改行が必要だったというテストケースのミスを修正した後のリジャッジと被って、実行は毎回かなり待つことになった。

月が変わったので、5月ぶんの読書記録の集計をした。

まだパソコンにかじりついているつもりだったが、椅子の上で少し寝てしまったこともあり、しょうがなく布団に移動した。午後3時、就寝。

06/01(火)

午後9時くらいに少し目を覚まして、午前0時まで布団でなろうを読み、また寝た。

06/02(水)

午前4時半、目を覚ます。二度寝するつもりだったが、実際は午前9時まで布団でなろうを読んでいた。今日は応募したインターンの2回目の面接の予定なので、もう二度寝できない時間になってしまった。仕方なく起きる。

午後1時からAtCoderJobsで応募したインターンの1次面接があった。

週記（2021/05/17-2021/-5/23） - kotatsugameの日記

生協の購買が開くのを待ってから学食に行こうと思って、それまではコードゴルフをしていた。昨日の典型90問がCrystalによって縮められていた。combinationsがTLEすることを確認してもう無理だと考えていたが、普通に再帰をするとよい。これは、毎回掛け算していたのが再帰1ステップで1回だけに抑えられた結果、定数倍の5が消えたことによるものだろう。また、普通のcombinationsだと最初にすべてArrayに溜めてしまうので、each_combinationsを使用してイテレータを用いるとよいのではないか、とも考えたが、こちらも結局TLEしてしまった。

それで、再帰関数を使う方法でしばらく格闘していたら、現状の最短である101Bと同じ長さのコードが完成した。かなりびっくりなことをしているので、もしかしたらもっとシンプルなコードなのかもしれない。とりあえず今はこれ以上縮められなさそう。

そのようなことをしていたら、午前11時半になってしまった。面接は正午からなので、それまでに大学に行って学食で食事する、というのは難しそう。ギリギリ購買で買い物するくらいはできると考え、自転車を一所懸命に漕いで向かった。思ったより早くついたので問題なくパン等を購入し、帰宅。急いで食べて、歯に食べかすがついていないことを確認し、Zoomに入った。

30分くらいCEOから会社の説明を受け、残りの時間はエンジニアの方々と質疑応答を行った。せっかくCEOから直々に会社の説明をしてもらったのに、特に質問などをひねり出すことができず、しばらくカメラの前で唸っていた。また、途中で自分の将来像のようなことを聞かれたが、こちらもすぐには思い浮かばず、恥じ入るばかり。エンジニアの方々に対しても特に聞きたいことなど用意しておらず、そういう面談があることは知らされていたのだから、準備しておけばよかったなあとひとしきり後悔していた。こちらは質問をひねり出すことができて、1日の流れであるとか、コーディングスタイルについてを聞くことができた。比較対象がないわけではあるが、まあ良さそう。

1時間ちょっとで終了。かなり感触が良い。前回の面接のときには、応募者がかなり多いため働ける日程に余裕がある僕は選考プロセスが遅れるかも、という話があったものの、今日聞いた感じだともう来週には会議にかけて下さるらしい。これどのくらい日記に書いていいのかわからないな。前回（1回目）の日記では怖がって具体的なことは何も書かなかったが、今回はいろいろ書いてしまった。マズかったらこっそり教えてほしい。

布団に倒れこんでしばらくなろうを読んでいた。眠気が襲ってきたが、振り払い、ゲーセンに行くことにする。

今日はかなり調子が悪かった。特に最初のほうは1曲ぶん集中が持たず、ノーツは見えているのに手が動かない、エアーでミスを出す、など散々だった。最後のほうはちょっとだけ持ち直して、新曲の99AJ埋めは一段落ついた。

午後7時を回ったあたりで食事しようと思い、ゲーセンを離脱。どこのラーメン屋に行こうか考えながらうろうろしていたらたいぺーからDMが来て、一緒に食事することになった。

仙台駅まで行って待ち合わせ、駅前のラーメン屋に入った。「味噌乃屋 田所商店」という店で、かなり昔に1回だけ入ったことがあった。その時どうだったかは覚えていないが、今日はあまり口に合わなかった。味噌ラーメンは好きなはずだが……。

ラーメン屋を出て本屋に入った。駅前の丸善は棚の配置の変更やらの真っ最中らしく、今日はラノベコーナーに行けなかった。仕方なく文庫コーナーだけ見て、前に買った本の続刊1冊と、新作1冊を買った。

本屋を出て、さてゲーセンに戻ろうかと思ったが、たいぺーはもう帰るつもりらしい。帰りしなに僕の自転車のチェーンに油を差してくれるそうなので、僕もゲーセンに行くのをあきらめてついていくことにした。たいぺーと別れて家まで自転車を漕いだわけだが、油の威力はすさまじく、力を入れてペダルを踏んでも音が全然しない。ありがたいことだ。

帰ってきて、今日の典型90問を解いた。bitsetを使うと書きやすい。Rubyで多倍長整数を使い縮めておいた。

米澤穂信さんの新刊が出るらしい。

しばらくなろうを読んだりしていたが、やはり眠気がすごい。午前1時就寝。

06/03(木)

正午、起床。ゼミがあるからと念のため目覚ましをセットしていたが、まさかそこまで爆睡するとは思っていなかった。危ないところだった。

今日の典型はすでに投稿されていたようだ。コードゴルフしていたらゼミの開始時間を見逃してしまった。2分遅れで慌てて入室したら、ちょうど僕がどうしたのかを話しているところだったようだ。急いで謝ろうとしたがマイクをオンにしたりミュートを解除するのに手間取った。

ゼミを聞きつつ今日の典型90問を解く。今日はいつもの\mathbb{F}_2線形代数。コードゴルフで基底を取る操作は、基本的にnoshi基底を使っておけば間違いない。

1度は取られたものの、入力を読みつつ溜めずに毎回基底に入れていく感じのコードを書いたらかなり縮んだ。bitの入力が2通りあるのがかなり厄介で、これはどうしようもなさそう。

ゼミが終わった。学食の夜の部が開く午後5時を待って学食に行き、そのあとまたゲーセンに行くことにする。チュウニズムのマップが全然終わらない。来週のアップデートで終了するイベントについては今日で終わらせておく必要があるというわけだ。昨日食事のあとゲーセンに行かなかったが、もし行っていたとしても昨日のうちには終わらなかっただろう。

このグルグルはずっとただの曲線だと思っていたが、アットマークらしい。びっくり。

しばらくなろうを読んでいたら午後5時前になったので、学食に行った。閉店直前の購買で飲み物を買い、学食で夜ご飯を食べて1日ぶんのミールカード1200円を使い切ろうとしたが、最後にダメ押しで買ったシュークリームが完全にはみ出てしまった。学食のシュークリームは硬くて不味い。正直、お金が余っていたとしても買わないほうがいい。買わないほうがいいことは分かっているはずなのに、レジ前に置かれているから、ミールカードの残額が微妙っぽい場合などについつい買ってしまいがち。今回もそれだが、実は微妙じゃなくてすでに使い切られていた……ということだった。

ゲーセンに向かっていたら街中でクラスメイトに会い、挨拶をした。学食とかでよく会う人。

今日の成果はまあまあ。マップやイベントは何とか限定アイテムをすべて集め終えることができた。また、12+の未AJが1個減り、ついにラスト1個になった。12+の未AJが減るのは本当に久しぶりな気がする。この譜面は今日たまたま選曲したものだが、一発でAJを出すことができた。ラストの鍵盤は相変わらずよくわからないが、指は動いてくれた。

ほかにも5譜面くらい13のAJを99AJにしたりなど。低難易度譜面で脱力を意識していたらエアーで赤をたくさん出すようになってしまい、困った。高難易度については、HAELEQUINの前半がかなりうまくなっていることが分かったが、結局ラストのホールド鍵盤地帯ゲーなのでどうしようもない。

じっくり午後11時までゲーセンにいて、さて帰ろうと思ったところ、駐輪場が閉まっていた。

昨日は（別に深夜まで止めていたわけではないが）別の駐輪場に止めていたが、そこはゲーセンから少し遠かった。そこで別の駐輪場があったことを思い出し、今日はそちらを使ったわけなのだが、24時間営業ではないことをすっかり忘れていた。どうしようもないのでまた明日来る。明日来れなければさらに追加料金が必要になってしまう。

今日は徒歩で帰る。帰りに夕食を食べることにする。いつもの立ち食いそば屋は空いているかわからず、24時間営業らしいマクドナルドを見つけたのでそこで食べた。僕が来たタイミングだけかなり忙しかったらしく、注文するまでも結構待った。日付も変わろうとしているのにUber Eatsの配達員が来ていてびっくりした。ビッグマックのセットを満腹になりつつ食べて、そこから30分以上歩いて家に帰ってきた。かなり疲労困憊。明日の行きは電車にしよう……。

シャワーを浴びて僕がゲーセンにいる間に縮められていたコードの粗探しをし、日記を書いたら、朝方になってしまった。布団に入ってすぐに寝た。午前5時半だった。

06/04(金)

午前11時半に目を覚ました。自転車を取りに行こうと思ったが、外は雨が降っていた。明日からまた晴れるらしい。駐輪場は1日60円で、さらに回数券を買っているので実際のところ1日あたり50円しかかからない。2日や3日でどこかへ移動されるわけでもなし、今日は取りにいかないことにした。

起きた時点ですでに典型90問が投稿されていたが、今日はそんな短くなる気がしなかったので、放置して布団でなろうを読んでいた。午後4時半になって布団から出て活動を開始し、まずはその典型90問を通しておいた。

ダブリングで解く方法と周期を検出して解く方法の2つが考えられる。このうち周期を検出する方は似た問題を以前ゴルフしたことがあった。確認するとちょっと縮む余地を見つけたので、そちらも更新しておいて、ほとんど同じコードで今日の問題も解いた。

atcoder.jp

と思っていたらPerlに抜かれてしまった。いろいろ奮闘した結果、桁和と元の値の和を求める部分がうまくいって縮んだ。桁和を求めるのは、単純に考えればeval s/\B/+/grとなる。あるいはmap 1..$_,/./gでもできることはできるが、長さも同じだし、今回は使わなかった。さて、s/\B/+/grの部分であるが、これをs//+/grにすると文字列の先頭と末尾にも+がくっついてしまう。このうち先頭は問題ないが、末尾につくのが困りどころ。そこでs//+/gr.$_としてみると、ちょうど末尾の+を使って元の値との和も一緒に求められるようになった。ここが最短を奪取したときの更新ポイントだった。

今日のサークル解説会の準備をする。yukicoderが午後8時スタートになった影響で、こちらも開始を1時間早めて午後7時スタートにしている。先週もずれたし、どうやら来週もずれそうだ。毎週金曜日に活動する上での宿命と言えよう。とりあえずF問題のスライドを作って、ほかの問題をどうしようか悩んでいたところ、祖母から仕送りが届いた。

仕送りの片づけをしていたところ解説会の時間になってしまったので、今週は僕のF問題と、もう一人E問題を解説してくれた人の発表だけになる。解説会には結局3人しか来なかったが、予定通り行った。

2021/06/04 定例会 | puzzleknot 公式サイト

終わってからしばらく院試について調べていた。まだ何も決めていないし考えようともしていない。困った……。出願までは残り1か月くらいしかないようだ。

yukicoder 298に出た。5完。

yukicoder contest 298 - yukicoder

Aはよい。BはNが偶数なら明らかで、奇数の場合は3 6を先頭に入れたりしておけばよい。N\le 5の場合は、N=1ならOKで、それ以外は構築不可能。Cは素因数ごとにカウントして最大値を求める。カウントについては、エラトステネスの篩っぽくやれば十分間に合いそうで、実際最大ケースでも間に合う。

Dを読んだがわからなかったので、solvedが多かったFに移った。大きな値と小さな値に分けて全探索することを思いついてしばらく格闘していたが、最大ケースとして10^{10}ではなく10^9を使っていたので2回ほどTLEを出してしまった。ここで気づいて、全然間に合っていないことが発覚。さらに奮闘して、なんとか手元では間に合うくらいの速さになったが、yukicoderのジャッジでは間に合わないようだったので、もうちょっと頑張る必要が出てきた。最終的に、小さな値は43までをmapを使って全探索し、それ以降は5重ループで全通り試すことで3500msくらいで通った。43まで探索するという根拠は、44\times 45\times 46\times 47\times 48\times 49\gt 10^{10}であるから。

Dに戻った。popcount(ab)%2には特に良い性質はないらしい。ここで、1からNを2つに分割するとき、まず数列Xにすべて入れておいてからYに要素を移し替えることを考えて、このときのf(X)-f(Y)の差分を見ることにした。試しに計算してみると、どうやら差分は要素ごとに独立な値になるらしい。a!=bなるa、bについてpopcount(ab)%2==0であったとすると、a、bがそれぞれXからYに移動する際にf(X)-f(Y)から1ずつ引かれることになるわけだが、まずf(X)から1引かれて、さらにaとbが両方Yに所属した段階でf(Y)が1増えると考えると納得できる。a==bの場合もちょっと注意すれば同様にできて、結局差分のうちいくつかを選んで足し合わせることで目的の値が得られるか？という部分和問題になった。

Eに進んだ。しばらく実験していると、1が書かれたマスが互いに影響しないなら綺麗な形になることが分かったが、影響し合うときにどうなるかが全然わからない。解けずに終わった。Gは見もしなかった。

upsolveはせず、そのままECR110に出た。全完。

Dashboard - Educational Codeforces Round 110 (Rated for Div. 2) - Codeforces

Aはよい。Bは偶数をより先頭に持ってくるのがよくて、このときもともと互いに素でなかったペアに加え、偶数と奇数のペアであって互いに素であるようなものの個数だけ良いペアが増える。Cは...010と...101に分けて数えるが、...???はどちらにもカウントされてしまうので引いておく必要がある。ちょっとインデックス周りが怖かったが、サンプルを合わせたら通った。

Dはセグメント木のように自分の子の値から自分の値を計算する。セグメント木の中間ノードごとに処理を変える必要があるので、自分でベタ書きした。普段使うセグメント木のインデックスと入力される文字列のインデックスでちょっと混乱したが、入力された文字列を全部反転して意味も反転してやるとうまくいった。

Eは、LCAをダブリングで求めるときに使うような親の列を動的に構築する。これは1、1+1、1+1+2、……のように作れる。この上で、クエリに答える際はどこまで使い切ったかを探し（二分探索してもよいが、BIT上の二分探索のようにすることでlogが1つ落とせる）、そこから1歩ずつ降りていくようにして使っていく。毎回1番上まで登ってしまい1TLE。

Fは難しい。文字列aとbについて、それぞれに含まれる文字を多重集合として見たときに一致していない場合はf(a,b)=1337。さらに文字列がすべて異なるという条件からa\ne bなのでf(a,b)\gt 0で、しかも文字列を両方ソートしてしまえば必ず一致するからf(a,b)\le 2となる。よって、f(a,b)=1となるような組だけ数え上げればよい。L=|s_1|として\min(n^2 L,26nL^2)くらいの計算量で解いた。

n^2Lのほうは簡単で、すべてのペアに対して先頭と末尾からできるだけ一致させた上で、残った真ん中の部分を考える。ペアのどちらかでその部分がソート済みであればよい。

26nL^2のほうは難しい。ローリングハッシュを使った。各文字列に対してソートする区間を決め打つと、それより前とそれより後ろは適当に前計算できる。ソートする区間については文字ごとの出現頻度を管理し、同じ文字が連続するハッシュを累積和などで計算しておけばよい。ここに定数倍の26がかかっている。そのようにして1つの文字列から複数のハッシュを作り、その他の文字列の（区間をソートしない）ハッシュであって今作ったハッシュたちに含まれるものの個数を数える。f(a,b)=1ならばaをソートするかbをソートするかのどちらか一方でしか作れないから、重複を気にする必要はない。

ローリングハッシュは、素数は1000000993を使い、基数はランダムな値2つを使用した。一発で通ってハッピー。

今日の典型90問が大幅に縮んでいた。実験してみたところ、毎回周期を検出する必要はないらしく、どこかで必ず周期4735のループに入るようだ。では毎回K \bmod{4735}を使用すればよいかというとそうでもなくて、ループに入る前に終わってしまうのはマズい。4735の倍数を順に試していくと、33145でACできた。その方針で縮めていくと何とか現在報告されている最短を更新することができた。

午前6時就寝。

06/05(土)

午後2時起床。今日の典型は全然わからなかった。まともに解けないと思って検索してみると、そのものズバリなライブラリが出てきた。

Offline-Dag-Reachability(DAGの到達可能性クエリ) | Luzhiled’s Library

さて、今日はいよいよ自転車を回収しに行く日だが、その前に生協の弁当を受け取ったり典型90問を通したりしておきたい。ということで出かけるのを待っていた。生協の弁当は早くに届いたが、典型90問の公開はかなり遅かった。なろうを読みながら待っていたが、結局出かけるのは午後7時過ぎになってしまった。

地下鉄に乗って仙台駅まで出る。水曜日に入った本屋は、今日はラノベコーナーにたどり着けた。よくよく考えるとこのコーナーは水曜日も存在して、ただ見つけられなかっただけにも思える。その後別の本屋もはしごしてラノベの新刊を買いそろえた。大学生協で注文しようと思っていたが、せっかく本屋に来たので、という感じ。また、水曜日に言及した米澤穂信さんの新刊も購入した。その後食事して駐輪場に向かった。

駐輪場に入る際、管理人さんがいたので挨拶しておいた。それが効いたのかわからないが、延滞分の駐輪券を1日分おまけしてもらえた。非常にありがたい。浮いた1日分を使って別の駐輪場（24時間営業）に移動し、そこに止めて今日もゲーセンに行った。

今日は「小悪魔の遊園地」でSSSを出した。追加されたときにSSSを出せなかったので敬遠していたが、やってみると今日はかなり上手く、すぐに乗った。特に中盤の意味不明な鍵盤地帯が意味不明ながらあんまり崩れなかったのがよかった。基本的に四鍵のように押そうとしているが、手の位置がずれることもあって実際は押せていない。グチャっとなっている。

今日はよくわからない鍵盤がうまい日かと思ってGiselleを選曲してみたが、こちらは全然ダメ。GCJR3もあるので早々に帰宅した。今日買った本を写真に撮ってツイート。

GCJR3に出た。Abdで183位。

Code Jam - Google’s Coding Competitions

通過可能性はないと思っていて、そんな精神状態でA問題を読んだので、即座に逃げ出したくなった。文字数が偶数の場合が難しいが、同じ文字が4個以上あれば2個組にして消してもよさそうだと思ったのでそのようにし、さらに2個以上残った文字を組にして消すかどうかをbit全探索した。0の扱いなどでミスっていたが、文字数8の入力を全通り試して愚直解と比較してデバッグしたら通った。

bはこれまたbit全探索。\binom{6}{3}^6くらいになる。dは座標圧縮後の数列を全探索して、そこでいったんゲームをプレイし、その結果に応じて組み合わせを使い元の値を復元する感じ。

このあたりでもうわからなくなったので諦めてしまった。Bは基本的に最大流で、うまいことコストを設定することで特定の位置から順に使われるようにしたり、あるいは四角形が存在する限りそれをflipし続ける、というアルゴリズムでも構成できるらしい。どちらもよくわかっていない。cは実は全探索できる、らしいが、こちらもあんまり考えていない。

へのkさんが25位で通過していてすごい。本当に強い。

布団にダイブしてなろうを読んでいたら寝落ちしてしまった。午前2時半だった。

06/06(日)

午前7時、目を覚ます。午前9時くらいまでなろうを読んで、また寝た。

次に目を覚ましたのは午後6時だった。yukicoderでお誕生日コンテストが開催されているようだが、見送ることにした。昨日のECR110はシステスが終了しており、全問通って8位だった。

昨日の典型90問は、昨日の時点でRubyの120Bが報告されていた。64個ごとに分割する以外の解法があるのだろうと思って解説の公開を待っていたのだった。公式解説自体は64個に分割するものだったが、drogskolさんが別の解法をツイートしていた。

i8vV5r - Online C++0x Compiler & Debugging Tool - Ideone.com

昨日はうしさんのライブラリを参考にして解いたため、(A_i,B_i)というクエリを処理するときにはdp[A_i]|=1<<iとしていた。そうではなくdp[u]|=1<<uとし、すべてのペアについて問題を解くことにすれば、頂点番号uに対しては1..uに対応するbitしか保存しなくてよいため、必要なメモリが\frac{N^2}2くらいになるらしい。またこれを多倍長整数で扱うとより簡単になるようだ。確かにRubyで書くとTLEもMLEもしなかった。その方針でちょっと頑張ってみたところ、何とか119Bを達成でき、最短を奪取した。

2時間くらいなろうを読んで、午後9時からABC204に出た。全完9位。

A問題はif文を書くのは長そうだったのでちょっと考えていた。どうやら(-x-y)%3で良いらしい。Bもdcだろうなとは思いつつ、こちらは時間を気にしてとりあえずRubyで書いた。CからはC++を使用した。Cは各点からBFS。Dは大体半分になる部分和を探せばよい。

Eは難しいが、コストが下に凸っぽいので三分探索できると思い、書いた。しかしWA。コスト関数t+C+\frac{D}{t+1}を微分してみると1-\frac{D}{(t+1)^2}になるためt=\sqrt{D}-1で最小になるらしい。これを直接計算し、その周り10個くらいを調べたら通った。Fは行列累乗。

Eはfloorを取ると傾きが0になる箇所が出てきて三分探索できないらしい。逆に、floorを取らない値で三分探索すれば通る。floorを取る・取らないでargminが変わらないことも簡単に証明できるが、一応TLで見た言及ツイートのリンクを貼っておこう。

コードゴルフ。Aはよい。Bはdcで書いたが、コンテスト後に縮められた。数列の要素数が少ないので、毎回zを使ってチェックしても間に合う。dcのテクがまだあまり発達していないころはループといえばこの形だったが、今は105オーダーのループを回すためにそれ以外の方法がいろいろ得られており、そちらに気を取られてしまった。

CはPerl。2200ms超えで全然間に合っていないようだった。mapで書いていたのをforに直しつつ別の個所も弄って通したのだが、コードは少し長くなってしまった。ふと気づいて答えを保存する変数を$\から$%に変えたところ、たった+2Bでかなり速くなってくれた。それでも2050msほどだったが、このくらいなら十分実行時間のブレで説明がつくということは知っていたので、同じコードを何回か投げて通した。$\は基本的に文字列を保存する変数なので、数値としてインクリメントしたりするのは遅い。DはRuby。EFは手つかず。

CF #724 div.2に出た。5完52位。

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

Aから難しかった。僕は条件を満たすか数列の要素数が300を超えるまでめいっぱい要素を追加する方法で解いたが、pretestで1400msくらいあってかなり不安だった。システスも問題なく通ってくれたが、冷静になって考えるともっとちゃんと解ける。まず負の数がある場合は数列の要素がどこまでも大きくなるので必ずNOで、負の数がない場合は数列全部のgcdを取り、その倍数を現在の最大値まで埋めておけばよい。また数列の要素の最大値が100以下なので、もっと単純に0..100を出力するだけでも解ける。

Bは全探索。答えは必ず3文字以下になる。Cは難しかったが、各文字列に対して文字列全体の'D'の個数と'K'の個数の比で分割しなければならないことに気づくと解ける。具体的には、各prefixに対して'D'の個数と'K'の個数の比を計算し、mapでカウントすればよい。

Dは毎回2要素しか増やせないので、中央値としてはすでに存在する要素のうち1個までしかずれることができない。逆に追加する値の絶対値を十分大きく取っておけば、以前に中央値として出現した値以外を考慮しなくてよくなる。よって、その以前に中央値として出現した値をsetなどで管理し、直前の中央値と現在の中央値の間に別の要素が挟まっていればNOとなる。

Eは面白かった。まず0は盤面のどこにでも置ける。0を置く場所を決定すると、1を置く場所も決定してしまう。なぜなら、1の隣には0がなければならず、また逆に0の隣でまだ決まっていないマスには1しか置けないからだ。1を置く場所が決定すると、なんと2を置く場所も決まる。これも先ほど同様、2の隣には1が存在しなければならないことと、まだ決まっていないマスには2以上の値しか置けないため、特に1の隣には2しか置けないことからわかる。このようにして、0を置く場所を決定するだけですべてのマスが決まってしまう。つまり、現在未定のマスから0を置くマスを決める場合の数を答えればよい。1点、注意として、0を置くマスは必ず1つ以上なければならない。

Fは全然わからなかった。実は後手必勝らしい。終了した盤面を適当な位置から切り開いてみると、おおよそABABAB_ABA_Bのような形になっていなければならない。つまりAとBは合わせて偶数個あるので、最後に行動できたのは後手、というわけだ。とはいえこれが分かったところで、何をどう数え上げるのかについてはいまだわからないまま。