01/04(月)
先週日曜日は、寝ようとしていたら両親が起床したので一緒に朝ご飯を食べて、さらにレポートを1問進めてから寝た。午前11時半のことであった。
午後6時、起床。夕食は外で食べるということが予告されており、また起こしてもらったため起床に成功した。回転寿司の店に行き、帰りに本屋に寄って帰ってきた。前回本屋に行ってから1週間も経っていないので新刊が出ていたりはしなかったが、棚を入念にチェックして3冊買ってきた。
書籍購入初めです pic.twitter.com/NUt8NTXNy0
— こたつがめ (@kotatsugame_t) 2021年1月4日
夜、レポートを進める。大問は7まであるが、6以降は発展的な問題に位置づけられており、解かなくてもよさそう。また、最低でも3問は解くようにとのことだが、この基準はすでにクリアしている。それでもさらに大問4くらいは解けそうなので、頑張って書いた。
午後10時、完成。父にスキャンしてもらう。その間に風呂に入ったりしており、提出は午後11時だった。今日はこどふぉのdiv.3があり、レポートがあったのであきらめていたが出られそう。出る。
全完した。15位だった。
Aは自明。Bは適当に場合分け。Cは後ろから計算する。Dは値の降順に選べばよい。Eは誤読していて時間がかかったが、まずh<=w
を満たすように交換してよくて、このもとでh
の昇順に並べた後w
の最小値を管理すれば特別なライブラリは何もいらない。
Fは最初入力で与えられるのが白マスかと思っていたが、さすがに違う。よくわからなかったので偶奇を保ったまま座圧して二部マッチングした。座圧周りがかなり怖かったが何とか通った。Gは遠い順に見ればよい。
コンテスト後のTLで見たが、Fは左から2個ずつ黒マスをペアにして見ればよいらしい。1つのタイルで偶数マス埋まることを考えると、一番左の黒マスについて、その上または下のマスは黒マスまたは1x2
のタイルの左のマスに対応している必要がある。次に2番目の黒マスでこの状態は解消され、同様にしてペアにした黒マスの間はそれ自体で完結しなければならない。かなり頭が良い。
今日は本を買ったので、買った本の記録をつける必要がある。ちょうどいいのでこれも年ごとに切り替えることにしよう。
このとき気づいたのだが、今年の読書記録に2020年と書いていたようだ。そのままツイートしたので非常に恥ずかしい。ただせっかく元旦に投稿したので固定ツイートは変更せず、2020年のままである。
はてなブログに投稿しました #はてなブログ
— こたつがめ (@kotatsugame_t) 2021年1月1日
読書記録(2020-) - kotatsugameの日記https://t.co/gHtL21ZLkT
「人生∞周目の精霊使い」を読んだ。最近は「一億年ボタンを連打した俺は……」や「……は時の牢獄で最強を超える」など人の身では不可能な期間の修行を理由にしたチートが多くて、そういう系列の本だと思って購入したが、1巻は結局ほとんど修行時代の話で終わった。マジで修行シーンを書いているとは思わなかった。ループの中で行動を変えたり、緊急回避的にcontinue
したりしていて面白い。こういう無限に強くなれる系の話は修行の辞め時が見つからなさそう、と思っていたが、この作品では「始原の神霊」と契約したところで精霊使いを極めたと判断して修行を終えている。次のループから物語が動きだして、そこで今巻は終わり。
AndroidのTweetDeck用ブラウザがTLに流れてきたのでダウンロードしてみた。かなりよさそう。最近公式のクライアントが落ちやすくて困っているので、乗り換えてもいいかもしれない。通信量削減のために画像や動画のサムネイルを読み込まない設定がほしいな、と思ったが、そもそもTweetDeck自体が通信量的に激重かもしれない。
Androidで動くTweetDeck用ブラウザをつくりました
— さぶうぇいさん (@HiSubway) 2020年12月30日
𝗠𝗮𝗿𝗶𝗻𝗗𝗲𝗰𝗸https://t.co/MFuMiwutrX
TweetDeckをスマホでも使えるようにするTJDeckの後継アプリです
TweetDeckがヌルヌル動いて、Twitter for Androidみたいなサイドバー、かわいいタブナビゲーションで操作できます
ダウンロードしてね pic.twitter.com/IpiIoyZu8g
もう1冊ラノベを読み始めた。「パソコンにおまけでついてるゲームね。爆弾を解除するやつ」「いつも一手目で爆弾を爆発させちゃうから、ゲームは嫌いよ」という発言があった。これに違和感を覚えて調べてみたところ、Windows Vista以降の付属マインスイーパは初手の瞬間に盤面を生成するため、一手目は必ず爆弾ではない(どころか周囲8マスに爆弾は存在しない)ようだ。より古いバージョンでプレイしているのかもしれない。または盤面のリプレイをしているだけかも。
両親が起きたので今日も朝ご飯を食べ、午前8時半に就寝した。
01/05(火)
午後7時、起床。昨日読み始めた「クラスの大嫌いな女子と結婚することになった。」というラノベを読み終えた。かなり面白かった。YouTubeに投稿されていた(?)漫画が原作らしい。これは今週の月曜日に買った本の1冊だった。つまりラノベの刊行予定を見ながら行っている新刊チェックに漏れていたということだが、表紙・タイトル・あらすじを総合してかなり良さそうだったのに何で買ってなかったのだろう。
こどふぉでメッセージが来ていた。昨日のE問題のコードがわからないから教えてくれというもので、どこがわからないのか書かれていなかったのでコード全体にわたってそれっぽいことを頑張って書く。30分もかかり、終わったのは今日のこどふぉdiv.1の直前だった。コンテストが始まってからありがとう見たいなメッセージが来た。
4完して2656→2675(+19)。
AはTLが1sec
だが気合を入れてlog
をつけた。このlog
はpriority_queue
によるものなので、400ms
くらいで通った。
Bは難しいが、結局xy
が平方数のときにx
とy
がadjacent
であるらしい。もうちょっと考えると、素因数分解した後各素数の指数をmod 2
で考えて、完全に等しいペアがadjacent
。さらにこの関係は推移律が成り立つので、数列はグループに分かれる。0秒目におけるグループのサイズが偶数である場合、総積が平方数となるため、同じく平方数となった別のグループとくっつく可能性があるが、1秒目におけるグループはそのあと永遠に変化しない。また、グループが分裂することはない。
よって、0秒目におけるグループの様子さえわかればw==0
とw>=1
の2通りが計算できてよい。素数の指数をbit
で持ったりvector
にしたりすることを考えたが、冷静になると素因数分解する前に戻せばint
1つで表現できる。後から知ったことだが、これは整数をsquare-free
にする操作と同等。
Cはパッと見どんな感じに変化するのかわからなかったので実験コードを書いた。いろいろ試していたが、ふと数列のp
を中心とする区間が単調になることに気づく。あとは単調になっている区間を探せば二分探索で中心が求められそう。単調になる範囲は質問クエリごとに2
増えるようなので、それを間に挟めないような幅で順に聞いて回ればよい。ちょうどp
の位置を聞いてしまうとまずそうなので、毎回隣り合った2マスを質問することにする。かなり怖いのでチェッカーを書いて、oj t/r
で試す。oj t/r
に慣れていないので、ちゃんとオプションを指定できていないのにコードの間違いを探し続けたり、テストが実行できたら楽しくなって無為に何百回も遊んだりしていたが、どうやら通りそう。提出しつつ時間を見ると残り40分になっていてかなり焦る。順位表を見てもCがかなり通されていて、さらにDのほうが簡単らしくヤバい。
まあ40分もあるんだし、とDを読む。二部グラフが思い浮かんで、奇閉路が問題となるが、これもできる。結局連結でさえあればよさそう。問題は構築で、最初条件を勘違いして教師が隣接しても構わず出力していた。結局貪欲に取っていくしかなくて、そこで幅優先探索ではなく深さ優先探索をすること、教師を置いたらその瞬間に隣接する頂点をマークすることさえしておけばよい。提出したら通って、Eは全然通されていなかったので諦めてTwitterをしていた。
heno239がLGM到達していてかなり感動した。で、伝説……。
「僕はリア充絶対爆発させるマン」を読んだ。直截的な表現が多くてびっくり。
明日(狭義今日)は朝の10時半からコンテストがあるので、寝なければならない。しかしなかなか寝られず布団でハーメルンを読んでいた。午前4時半就寝。
01/06(水)
午前10時起床。目覚ましでも起きたし、前日に朝からコンテストがあると伝えていた母も起こしに来てくれた。朝ごはんもゆっくり食べていい感じ。パ研合宿2020第1日「SpeedRun」に出る。
Oが解けなかった。最初はコードゴルフをしつつだったが、途中からコードゴルフしている場合ではなさそうなことに気づき、必死に考察したものの届かず。そのあと他の人の提出を見ていろいろ縮め、昼ご飯を食べようとしたときに解けた。基底を取ることは考えていたが、A
とB
を別々に考えてしまっていた。以下、各問題について。
AはText
。改行が必要らしい。Bはget.comb.max.say
が最短となっている。さすがにこんなはずはないだろうといろいろ考えてみたが、見つからなかった。CはRaku
で∩
演算子を使う。これはASCIIコード範囲では(&)
と書ける。どちらも3Byte
だが、パースの関係で空白が必要なくなる∩
のほうが短くなることがある。今回はどちらも同じ。
Dは場合分け。答えを4通り用意してK/N
でインデックス付けするとよさそう。dc
ではrotate
操作で実現できる。Eも場合分け。AWK
で書くと短くなった。Fは見つからなかった場合のエラー処理が必要かと思ったが、-1
を出力するケースは存在しないらしい。P==1
の場合分けを頑張る。dc
。
Gはゴルフしていない。HはRuby
で書いた。他の言語ではあんまり考えていない。Iはゴルフしていない。Jでは.²
というのが出た。$_²
と同じ。これを適用して縮む問題がほかにあったので縮めつつ、変数の初期化などで改善して最短を奪取。4,6...
だと$_
を初期化しておく必要があるが、これは8,16...
とすれば回避できる。出力する値には余裕があるので、公差を大きめにしてもACできる。
Kはゴルフしていない。Lはdc
。すでに相当短いものが提出されていたが、隙を見つけて奪取した。MNOはゴルフしていない。
昼から4時間程度塾に滞在した。帰省のたびに顔を出している。
今日も塾に行く。採点のバイトをするのだ。水曜日もやたら長く塾に滞在したのは、話の流れで同じく採点していたからだが、今日は初めからバイト目的で向かう。
週記(2020/08/24-2020/08/30) - kotatsugameの日記
今日は年末年始の休み開けであるから、宿題の採点が追い付かないことが予想されていて、手伝いが必要なようなら採点バイトに入るくらいの気持ちで行った。数人とんでもない量の宿題をこなしてきた生徒がいて、僕は任された分が間に合わずヒィヒィ言っていた。結局先生にいくらか戻したが、先生はほかの生徒の指導をしつつ素晴らしい速度で採点しており、年季が違うなあという気持ちに。生徒への指導にしても、今日は言葉に迷うことが多くて残念な結果となった。
対面で指導する(僕が採点している前のテーブルに来て質問したりする)のは感染リスクが高めだなあと感じた。マスクをとる必要がないのでギリギリセーフか。
帰ってきて新春 TechFUL Coding Battle 2021に追加された3問を解いた。逆転チャンスと銘打たれているが、上位陣にとっては当然満点を取らなければならないレベルの難易度。まんまと1ミスしてしまい非常に厳しい気持ちになった。逆転(される)チャンスなんだなあ。
明日の夕方からドカッと雪が降るらしく、土曜日に予定があるので、明日のうちに仙台に帰ることにする。今日早起きだったので昼のうちに新幹線に乗れるだろうという計算。
「僕はリア充絶対爆発させるマン」の2巻と3巻を読んだ。シリーズ完結。正直なんの面白みも感じられなかった。本当は2巻を読了した時点で日付が変わっていて、早く寝なければならなかったのだが、3巻だけ持って仙台に行くのもなんだかなと思って無理して読んでしまった。
午前4時就寝。
01/07(木)
午前10時半起床。食事して荷物をまとめ、家を出る。
母に車で黒部宇奈月温泉駅まで送ってもらう。切符を買おうとしたら、12/23でみどりの窓口の営業が終了しており、学割を適用できない。あきらめて通常料金で買おうとしたところ、駅員さんに「みどりの券売機プラス」という機械の存在を教えてもらう。起動するとどこかのセンターにつながり、学割をカメラで読み取ったりして普通にみどりの窓口で行うようなやり取りののちに学割を適用した切符を発券してもらえた。10分くらいかかった。今日は結構時間に余裕があったので良かったものの、ギリギリだと間に合わないだろう。混んでいる場合もまずそう。今度からは事前に買っておくのがよさそうだ。
ホームは非常に寒い。外を見ると風が結構出てきていることがわかる。駅から自宅まで車で帰る母のことを心配しつつ、乗車。コンセントとフリーWi-Fiを確保し、今日の昼からのパ研合宿2020第2日「パ研杯2020」に備える。
6完で全体8位だった。終盤、部分点を狙うのを完全に忘れていた。
A問題はdc
。空白区切りではなく改行区切りにしても通った。B問題は短くならなさそうなので、H問題のマラソンに行ってしばらくコードゴルフをしていた。
B問題は01BFS
で書いたが実際はDP。C問題はいくらか考えると入次数と出次数の差がポイントになることが分かった。D問題はトポロジカルソート。E問題は各点についてそれが乗る直線の個数を数えたくなって、これは直線の傾きをsqrt
で分けて処理すればできる。制約が2sec
なのでかなり不安になりつつ出したが、450ms
とかなり速かった。
Fを頭に入れて、部分点の考察ができた段階で乗り換えをした。移動の合間も考えていた。レートはある程度自由にやり取りしてよさそうだが、2倍にできるものの範囲は考える必要がある。今度も自由席にコンセントがついている車両だったため、先ほどと同様のセッティングをした後にもうちょっと考察をしたら解けた。
基本は二分探索で、判定問題を解く。L
とR
を混ぜて順に処理する。L
を処理するときは、時系列のL
にレートを全部置いていく。R
を処理するときは、まず対応するL
以前に置いていかれたレートを全部回収して2倍にする。足りていれば余計な分をR
に置いていく。足りない場合は、ほかに置かれたレートを回収してつじつまを合わせるが、このとき時系列順で最近置かれたものから取っていくのが直感的に良い(なぜなら、より古いものはより多くの人に2倍で回収され得るから)。
以上のことを区間0クリアと区間和の遅延セグメント木で処理した。つじつま合わせは二分探索で行った。これを提出したところ、WAがたくさんとTLEが1つ出た。どうやら倍になりすぎてオーバーフローしたらしい。全員分に相当するレートが確保した時点で打ち切ると、TLEが1つだけ残った。オーバーフローを解消したら直ると思っていたが、普通に間に合っていないようだ。
冷静になると、上の操作はdeque
で実現できる。L
以前のレートを回収するのはpop_front
で、つじつま合わせはpop_back
で書ける。これを実装すると爆速で通った。
C問題をゴルフする。Ruby
で書いていたが、Perl
に書き直すと速度でもコード長でも大幅な改善が見られた。謎。残り30分で順位表を見ると、G問題が思ったより通されていた。慌てて考え始めるも、CHT
が見えたあたりで嫌になり始める。オイラーツアーも必要に思えてきて、どうしても実装が間に合いそうにないなとなった。
今日の新幹線はかなりガラガラだった。緊急事態宣言と大荒れ直前の天気のダブルパンチで移動する人が極端に少なかったのだろう。
仙台について、ゲーセンに行く。素手でチュウニズムを頑張る。新曲の99AJ埋めをした。午後8時くらいに夕食を食べようとラーメン屋に行った。
ラーメンパンチという店があって、移転したのだが、跡地もラーメン屋になったことをTwitterで見聞きした。そこへ行ってみたが、たまたま水曜日が定休日らしく閉まっていた。
週記(2020/12/21-2020/12/27) - kotatsugameの日記
ここは今日はスープがなくなったらしく、もう閉まっていた。かなり残念。だし廊というラーメン屋に行った。
ゲーセンを変えてさらにチュウニズム。ちょっと理論値を狙ってみたが、非常に厳しい。何でもないようなノーツでもぽろぽろ落としてしまう。最後に怒槌を数回プレイして、なんとかSSに乗せた。終盤は有名な擦りや餡蜜があるのでそれをした。密度が高すぎてどれだけ失点しているのかわからない。しかし前半がとにかくボロボロ。
帰るときになって、壁のチラシでチュウニズムにおいて200円3クレイベントが開催されていたことを知る。今日は結構お金を使ったのでつらい。
帰りはかなり雪が降っていた。マスクから出る息でメガネが曇って前が見えない。
こんな感じです pic.twitter.com/yk1Qm1xwNz
— こたつがめ (@kotatsugame_t) 2021年1月7日
FHCのTシャツが届いていた。
ゲット pic.twitter.com/MqestaauzK
— こたつがめ (@kotatsugame_t) 2021年1月7日
今日のH問題の最短が奪われていた。p [100]*4e4
にしてWAになり首をかしげていたが、p *[100]*4e4
である。なぜこれに気付かなかったのか。マラソン典型である。非常に悔しい。
帰省前の自分は相当丁寧に部屋の食糧を食べつくしていっており、夜中にお腹が空いてつらい思いをした。午前4時就寝。
01/08(金)
午後6時半起床。親から実家の屋根の写真が送られてきた。めちゃめちゃ積もっていて、ちょっと見たかったなあという気持ちになった。土曜日の予定が、コロナのせいか雪のせいかはわからないが消滅した。
パスタをゆでて食べた。yukicoderに出る。D以外の5完。Bは直後に追加されたチャレンジケースで落ちてしまった。
Eは式を根から各頂点とそのLCA
まで、それぞれの距離に分解して計算すればよい。適当にガチャガチャしていたら合わせるのに時間がかかってしまった。Fは既出。
2*(区間長)<=総積が正しい条件らしい。次のように証明できる:
週記(2020/12/07-2020/12/13) - kotatsugameの日記
証明に関してはこれ(引用の続きの文)でよい。当時のコードをコピーして少し書き換え、提出したところ、WA。ちょっと計算量がヤバいことは知っていたのでTLEするかもなとは考えていたが、WAとは……。
探してみるといろいろバグが見つかる。そもそも上の問題は+
とか*
をそのまま出力する問題なので、書き換えでミスしていた。それと制約の違いを直し忘れていたのと、オーバーフロー。それでもWAが取れなかったので、コードの根幹部分を一気に書きなおしたところ、通った。謎。ちなみに計算量がヤバかったのも直している。間の1
が連続する箇所は切り分けるが、その区間の演算についてもbit
全探索していた。そこは抜いておいて積に相当するか和に相当するかで変えればよい。
チャレンジされて落ちているBを放ってこどふぉdiv.2に出る。Eにめちゃくちゃハマってギリギリ全完。今日もスクリーンキャプチャしていた。
Aはギャグ。先頭は98
にするしかなく、このとき8
を境に折り返すことで989
にできて、一番よい。Bは値の総和を求めるのだと勘違いしていた。hill
やvalley
だけを取り出したvector
を作ってそこだけ見たところWAで、冷静になると値を隣に合わせるのがよく、このとき差分は回りを少しだけ見れば計算できるのでよい。
Cはそれぞれの総和と最小値だけ持ってうまいことやる。AtCoderで似た問題を見たことがあったが、今回の場合難しいのはそこからだろう。リンクを貼るために問題を探していたが、ABCで出題されたと思い込んでいたため見つからず、TLに聞いた。
Dは明らか。Eは同じ値の頂点のペアに対して、それぞれを根にしたときのもう片方の頂点以下の部分木に入る頂点に1
加算して、最後に0
だった頂点を見つければよさそう。適当に根付き木にしたとき、加算は木上のimos
法でできる。ペアの列挙については、同じ頂点を何回も見る必要がないのでペア数はO(N^2)
ではなくO(N)
になる。部分木の頂点をmap
に入れて保持し、更新時に同じ値の頂点が見つかったら1
加算の操作を行う。マージテクで間に合う。
根付き木にしたときに、ある頂点とその部分木に含まれる頂点のペアを処理するところでミスし続けていた。imos
法において-1
してキャンセルしなければならない頂点は、上にある頂点ではなく、そこから1歩ペアの頂点に向けて進んだ頂点でなければならない。これは部分木をマージしてから処理するのではできず、マージ前に部分木ごとに行う必要があった。
「見習い巫女と不良神主が、世界を救うとか救わないとか。」を読んだ。ストーリーはそこそこいい感じだが、ひたすら読みにくかった。三人称視点で書かれているのに急に主人公の一人称視点で感情が書かれたりするからだと推測したが、ではどう書けばよかったのかとか、他の三人称視点の作品ではどうしているのかは知らないので、これが本当に的を射た指摘であるかはわからない。
振り返ってみれば、本を読んでも内容にはほとんど触れず、読みやすかっただの設定が好みだのしか言っていない気もする。読むときに何も考えていないからそうなってしまうのだが、これからは意識的に内容に触れる感想を書くようにしたいと思った。
布団に入ってハーメルンを読み、正午就寝。予定が消滅したので思うさま生活リズムを崩壊させているが、レポート提出などで昼に起きなければならない用事はほかにもある。
01/09(土)
午後6時半起床。目を覚ましてしまったものは仕方がないが、もう数十分くらいは寝ておきたかった。この時間から二度寝するとまずそうなので起きる。
コンビニに行って食べ物を買う。サラダを2つと菓子パンを4袋、あとお菓子を少し。かなり空腹だったのでうっかり山ほど買ってしまった。
ARC111に出た。5完23位。パフォーマンスは3079でレートは2654→2704(+50)。大成功。直前まで作業していたため、画面を録画するのを完全に忘れていた。
Aは解法が降ってきた。C++
でコーディングしたら結構時間がかかってしまったが、このくらいだったら最初からdc
で書いてもよかったかもしれない。提出してからB問題に進む前にdc
でコードゴルフしたところ、12B
になって現在も最短コードである。難易度的には、ABCの300点問題というよりはAGCの300点問題だろう。
Bは既出。UF
に辺の数も持たせようとして、ライブラリを書き換えるのではなく最初からフルスクラッチしようとしたら、typoしてしまった。1WA。
Cは置換なのでサイクルに分けることを考える。2頂点以上のサイクルがあったとき、そこにすでに疲れた人がいるとダメで、そうでない場合はできそう。実際、一番体重の重い人はサイクル内のどの荷物を持っても疲れないので、この人を使ってサイクルを縮めていけばよい。
Dはパッと見難しいが、制約がこれでもかというくらいに「解が存在する」ことを主張しているので、まあそれを使うんだろうなあとわかる。冷静になると、異なるc
を持つ頂点を結ぶ辺の向きは決定できて、そうでないものはループの一部にならなければならない。あとはループになるように辺を向きづけるが、これは、できる。ある頂点からdfs
すると、どこかのループに乗ってスタートした頂点まで戻ってこれる。そのループを縮約して同様に進める。実際には縮約せず、ただのdfs
でできる。
Eはとても面白かった。まずA+Bi
とA+Ci
の差を考えることでi
としてあり得る範囲が求まる。その中で(A+Bi)//D
と(A+Ci)//D
の差は0
または1
。こういう考察はABCで見たことがあったので、すぐにたどり着けた。floor_sum
をちゃんと使っているのも面白い。
A+Bi
がD
の倍数のとき、困る。僕は拡張ユークリッドの互除法で解いて実際に個数を求めたが、A+Bi
の代わりにA-1+Bi
を使えばよかったらしい。
Fは解けなかった。要素ごとに考えて、更新クエリがk
回来たときある値になる場合の数を計算する。max
とmin
がいい感じに補い合い、1..M-1
のどれでも同じくM^(k-1)(2^k-1)
通りだと分かった。あとはクエリの区間についての処理だったが、できなかった。インデックスi
が含まれる場合の数はi(N+1-i)
だが、これのi=1..N
におけるj
乗和をj=1..Q
において求める必要が出てきた。式変形の方針を間違えたのだろう。ほかにも考えなければならないことは残っていて、これができたとしても解けたとは思えないが、ともかくコンテスト中はこれにかかりきりになって終わった。
シグマが絡む計算の式変形が苦手であることが分かってきた。何とかしなければならない。
午前2時からSRM797。EasyとMedを解いて18位、レートは2328→2389(+61)。highestである。画面の録画をした。
Easyはどこまで上がるかを全探索した。最初、あんまり上がらなくても回り道すると行けるということを完全に見落としたまま実装し始めてしまい、ちょっと時間がかかった。
Medは難しい。期待値の関係を行列にして解くやつかと思って行列ライブラリを貼ったが、サイズが5000x5000
になるので違う。冷静になると、行列の各行の非ゼロ要素は高々10
個で、また関係する項の添え字もi
に対してi+1
以下となるため、i
の小さいほうから順に計算していける。
具体的には、i
を計算する際にj<i
なるx_j
をa_j*x_i+b_j
という形で保持しておく。このとき、x_i=a'*x_{i+1}+b'*x_i+c'
という式にまとめられるので、ここからx_i=a*x_{i+1}+b
に直して、それをj<i
なるj
の式に対して代入する。これで次にi+1
を計算する際も同様の条件が満たされたままにできる。N
を項の数としてO(N^2)
。実は、「前に1進む確率がp
なら期待値は1/p
」と「後ろ向きならx_i-x_to+1
のコストで戻ってこれると考えてよい」でO(N)
で計算できるらしい。すごい。
遷移関係を求めるのも少しややこしいが、こちらにもO(N^2)
かけてよいので、やりようはいくらかある。僕はZ-algorithm
を使用して判定を定数時間で行えるようにしたうえで全探索した。やっていることはKMP
法のfailure-function
なので線形時間でも可能らしいが、名前を知っているだけで内容は知らないため実装できない。
自作のmodint
を貼ったらコンパイルエラーが山ほど出て、結局直せなかったので普通にmod
を取りつつ書いた。
Hardは意味不明。サンプルを手で解いて実際に条件を満たすことを確認するのに30分くらいかかった。
ラノベを1冊読んだ。「デスゲームから始めるMMOスローライフ」。スローライフ系の話は実はほとんど興味がなく、この作品は特に主人公やヒロインがチートだったりもしないので、完全に僕の趣味・嗜好からは外れていた。買ったのがもう4年も前なので、当時何を考えていたかはわからない。当時はちょうど、毎月新刊をチェックして新作を買うことを覚えたころだったが、資金は潤沢ではなかったので、現在のように「積んでいる本の続刊を買ってさらに積む」みたいなことはあまりしていなかったらしい。このシリーズは4巻まで出ているが、2巻までしか買っていなかったので、最近古本で3巻と4巻を購入して揃えた。
設定におけるSAOとの類似性がいくつもあってモヤモヤしたが、まあデスゲームを書くなら大なり小なり似てしまうのだろう。内容的には主人公がヒロインとずっと戯れているシーンが続くだけで、僕は面白くないと感じたが、続刊の帯によれば重版したらしい。
yukicoderの問題をいくつか解いた。
この問題はA
、B
、C
が正整数であると書いてあるのを見落としてWAしてしまった。自分の最初のACコードが落ちるケースを発見したので、試しにほかの提出を確認してみたところ、いくつか落ちるコードが存在したので、チャレンジしておいた。
布団に入ってハーメルンを読む。最近は紙の本に注力していてネット小説はあまり精力的に読んでいなかった。今日やっと1作読み終えたが、これも1か月くらいかかった。
東方Projectのオリ主系、好きかもしれない。
週記(2020/12/07-2020/12/13) - kotatsugameの日記
これを受けて読み始めた作品だったはず。1話の冒頭で東方先代録という作品が紹介されているが、これは途中で止まっている。
上位存在・長命種が人間の発展を見守ったり導いたりする話が好きだと言っている
週記(2020/09/28-2020/10/04) - kotatsugameの日記
「古代スタート」というタグがよさそうであることに気づいた。
午後1時、就寝。
01/10(日)
午後3時くらいに腹を壊してトイレに駆け込んだ。午後8時起床。ABC188に出る。
全完したが、Fに非常に時間をかけてしまった。今日も画面録画をしたが、どういう動画にするのがよいか迷う。コードゴルフの作業も結構録画してあるので、そちらをメインに動画を構成するのもいいかもしれない。
Fの2WAはビットシフトのオーバーフロー。1LL
ではなく1
と書いていた。久しぶりにやらかしたので結構びっくりしている。↓と同じ問題であることに気づけなくて残念。AtCoderでメモ化再帰が頻出しているような気がする。そんなに使うとは思わなかった。
コードゴルフは現時点で全勝。Aはrange
とかminmax
とか考えてしまうが、差の絶対値を見ればよい。符号付のままでも、絶対値に関して切り上げ除算することで-2..2
を-1..1
に圧縮すれば次の問題と同じになる。
BはRaku
で書くだけだが、全完後にちょっと書き直したら1B
縮んでびっくりした。遅きに失したかと残念がっていたが、蓋を開けてみれば最短だった。
Cは最初から左半分と右半分のmax
を比較する方針を取れたのがよかった。Dはコンテスト中は座圧してから解いたのでコードゴルフする気はなかったが、解説を読んでイベントソートでよいことを知り、縮めた。
Eは制約が優しいので順に見ればよい。辺をソートすると隣接リストを作らなくてもよくなる。Fはさすがにコンテスト中の方針(桁DP)でコードゴルフする気にはなれなかったが、解説でメモ化再帰解を知り、縮めた。Ruby
でゴリゴリ縮めた後、仕上げにVim
に移植したら一気に8B
削れてびっくり。
Haskell 1000AC pic.twitter.com/7gcHYwN70f
— こたつがめ (@kotatsugame_t) 2021年1月10日
1000ACはこれでAWK
、bash
、bc
、C++
、Haskell
、Julia
、Pascal
、Perl
、Ruby
の9言語。次はC
でも狙おうか。
言語別AC数のページを見るたびに、Perl6
とRaku
が区別されてしまっているのが非常に気になるので、とりあえずIssueを立てた。プルリク用のコードもすでに書いたが、最初からプルリクを送り付けるのがなんだかためらわれて、まずお伺いを立てる感じ。別にそんな変な遠慮いらないのかもしれないと今になって思った。
新春 TechFUL Coding Battle 2021が終了した。最終順位は5位。12問目は非常に難しく、最初はO(3^N)
にいくらかゴミがついた計算量で通そうとしていたものの、断念。遷移をもうちょっとよく考えると、ビット列を左から順に処理していってもよいことに気づき、i=1..N
に対してi
桁目だけ処理するO(2^N)
のループを書いたら解けた。15問目はS==T
で1WA。
yukicoderを数問解いた。
(1+sqrt(2))^n
の整数部分を求める問題、みたいなのをTLで見たことがあるはずだが、肝心のアイディアを思い出せなかった。何らかの数とペアにして、そのペアの数の絶対値が非常に小さいことを利用することまでは思い出せたのだが……。結局解説を読んでAC。考察メモを見返した感じ、a+b
とab
を利用してa^n+b^n
を求めるということができていなかっただけにも見える。