以下の内容はhttps://kotatsugame.hatenablog.com/entry/2023/03/27/234517より取得しました。


週記(2023/03/20-2023/03/26)

03/20(月)

午後4時半少し前に起床。12時間近く寝ても眠いがインターン先定例会に出席しなければならない。頑張って布団から這い出した。

先週はMuscatキャンプに出ると言って休んだので進捗報告は2週分まとめて。しかしその2週間でできたことはドキュメント整備のみであった。

勉強会は労働組合とか労働紛争の話。エンジニアは気軽に転職する、あるいはできるという印象があって、働く環境を改善しようとしたときは会社に要求を出すのではなくとっとと転職してしまうんじゃないかと思っており、このあたりの話には残念ながら全く興味を持てなかった。実際にどうなのかは知らないし質問してもよくわからない。まだ遠い話だと考えている自分がいる。

午後7時半くらいに終了。その後先週の週記を書き進めていたが、びっくりするほど集中力がなく全然進まなかった。午後11時半ごろ、5hいくつかと土日の分を丸々書けていないまま投稿した。

ECRに備えていたがCFが繋がりにくい。大丈夫かと思っていたら15分こどふぉった後コンテスト自体が消滅した。

今週のセミナーは水曜日、しかも自分は発表しないから、今日この後しないといけないことがない。先週の週記を完成させる気力も湧かないので久しぶりにラノベを読むことにした。朝までかけて2冊読了。

1冊目、「灰原くんの強くて青春ニューゲーム」4巻。ヒロイン数名から好意を向けられていた主人公がついに一人を選択する巻だった。バンドを組み文化祭のライブで思いを伝えるというかなり劇的な展開で面白かった。バンドの練習時も、実力で少し劣る主人公だが卑屈にならず何とか食らいつこうと努力を続けているので、読んでいて好感が持てる。ただ、一人を選択することはそれ以外の人を選択しないということであり、そういう暗い面もしっかり描かれていて少し辛い気持ちにはなった。

2冊目、「双星の天剣使い」2巻。特に感想が思いつかない。国の中枢にいる権力欲の強い無能キャラに対するヘイトを強く掻き立てられて、それ以外に記憶に残ったシーンや展開がなかった。面白くなかったわけではないはずだが……。

3月末から4月末にかけての新刊チェックをした。毎月のようにほぼラノベばかり注文。今月は25冊だった。

さらにラノベを読み進め、午前11時就寝。

03/21(火)

午後7時から2時間ほど起きてなろうを読んでいた形跡がある。

03/22(水)

03/21 午後11時起床。月曜日に消滅したECRの代わりの日程が今日だと思い込んでわざわざ目覚ましをかけておいたが、全然そんなことはなかった。

それから二度寝をすることもなくなろうやラノベを読んでいた。朝までかけて2冊読了。

1冊目、「反逆者として王国で処刑された隠れ最強騎士」。逆行転移モノ。主人公だけでなくヒロインも逆行しているため、未来のことを知る仲間がいる安心感が強い。主人公は最強騎士とされているが、今のところひたすら頑丈なだけに見える。そういう最強もあるのかもしれないが自分としては特に好みではない。

2冊目、「お隣の天使様にいつの間にか駄目人間にされていた件」8巻。正直、主人公とヒロインがひたすらイチャイチャし続けるのにはもう飽きが来てしまった。その証拠に買ってから2か月ほど積んでいた。まあこれについては読むタイミングを逃しただけで、同様の理由で積んでいる中には現在進行形で面白いはずのシリーズもある。

2冊目を読み終えたのが午前9時頃。そこからシャワーを浴びて食事し、外出の準備をしたら午前10時の10分前になった。慌ててセミナーに向け出発した。

今日は大学の教室が使えないらしく、別の建物のホワイトボードが置いてあるスペースでセミナーを行うことになっていた。少し遠かったこともあり微妙に遅刻。

同級生の発表は前回詰まっていたところを無事終えて次の補題を示すまでだった。結構複雑なステートメントで大変。教科書の証明では事実だけ書かれている部分を確認するのにMengerの定理が必要で、もはや注釈もいらないくらい有名な事実として扱われるんだなあと感じた。

月曜日の日記でも書いたように今回は自分の発表はなく、午後1時解散。学食で食事しラノベを受け取った。帰宅早々布団に横たわり、しばらくラノベを読んでから午後3時就寝。

その後、午後8時から1時間ちょっとの間は起きてハーメルンを読んでいたらしい。

03/23(木)

午前3時に起床し、ずっとラノベを読んでいた。3冊読了。

1冊目、「異世界でチート能力を手にした俺は、現実世界をも無双する」13巻。今回は現代パートがメインか。前の巻で急に生えてきたスクールアイドル計画が描かれたが、描写が非常にあっさりしていて結構残念だった。レッスンパートもライブパートもほぼトラブルなく、あまりにもスムーズに進行していった。

2冊目、「魔王城、空き部屋あります!」。面白かった。魔王の尊大だが真面目なキャラが好ましい。勇者と魔王の確執がずっと暗い影を落としていたのもラストで解決されて良かった。

3冊目、「お兄様は、怪物を愛せる探偵ですか?」。設定はほぼ「虚構推理」と同じ。しかしちゃんと面白かったし、主人公とヒロインの関係もラノベ風味になっていて、ただのコピーという印象はなかった。ミステリ部分では推理を重ねるより証拠を集めて事件を解決していたので、あまり探偵モノだとは感じなかった。

正午くらいに寝落ちし、午後5時ちょっと前に目覚ましで起床。1on1に臨んだ。ここ数日ずっとラノベを読んでいるばかりで進捗が一切ない。ドキュメントに書く内容についてしばらく相談し、1時間程度で終了した。その後布団に戻ってまた寝た。

午後10時起床。1時間ほどラノベを読み、「囚人諸君、反撃の時間だ」を読了。主人公の反骨精神ばかりが目立ち実力が追い付いていないように感じてしまった。

シャワーを浴びて午後11時半からECR145。

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

Aは全部同じ数字の場合不可能、3つが同じ数字の場合6手、それ以外は4手でできる。全部サンプルにあって優しい。

Bは答えを二分探索する。原点からマンハッタン距離がa以下の領域に点を隣接しないように端から詰めていくと、(a+1)\times(a+1)の正方形が斜めになった形に綺麗に並ぶ。つまり(a+1)^2\ge nなる最小のa\ge 0を求めればよい。

Cは累積和が先頭を含めdistinctで、転倒数がn(n+1)/2-kであるという条件になる。転倒数とそれを達成する累積和の一例を持ってdpすると復元の手間がなく楽。O(n^3)状態がそれぞれO(n)要素持つので空間的にも余裕。

Dは操作のコストから、まず操作回数を最小化し、その上でremoveの回数を最小化する問題となる。ソート後の0と1の境目を全探索するとremoveだけでソートする際の操作回数を求められる。境目のすぐ隣にない文字はswapを使って移動させるよりremoveしたほうが操作回数が少ないから、swapする対象としては境目の両隣しか考えなくてよい。そこをswapするかしないか判定し、毎回コストを求めた。

Eは難しかった。c+dを固定し、c-dに着目して解いた。この値は操作のたびに-2v変化するが、上限と下限が存在する。つまりx\leftarrow \mathrm{clamp}(x-2v,l,r)という操作を繰り返し最後のxを求めるという問題になった。最初のxとしてはl,l+2,l+4,\dots,r-2,rが存在する。それぞれに対し現在の値がどうなっているかを上手く表現した。

グラフにすると傾き0の区間、傾き1の区間、傾き0の区間の三つに分かれた状態にしかならないから、これを管理すればよい。適当に実装したらすんなり合った。後から振り返ってみると傾きが変わる点の座標を追っていたらしい。後から気づいたがc-dではなくcそのものを管理すれば変な係数2が付かない答えも直接出るから少し楽だった。

Fはちょっと簡単。始点を決めた時の答えは、b=1の点では満タンまで給油し、そうでない点では次の点にたどり着けるまで給油するという戦略が正当。燃料が余ったらその分はb=1の点で給油したものだから、なかったことにしてコストから引けばよい。

これを少し弄ると、b=1の点にたどり着いた時点で残っている燃料をなかったことにしてもよいとわかる。すると円環をb=1の点の直前で切ることで各区間を独立に考えることができるようになる。始点sを決めたときちゃんと計算する必要があるのはsが含まれる区間のみである。

区間の先頭から各点までたどり着くためのコストは、先頭から計算すれば全体O(n)で求まる。これを見れば区間の中でsより前の部分に対するコストが求まる。sより後ろの部分は、b_s=1ならその区間を全部通るためのコストになり、b_s=2ならその先で最も近いb=1の点までの距離に2を掛けたものになる。後者の考え方でb=1の点がない場合も処理できる。

G。それぞれの人は自分より小さいindexでaが最大の人と試合を行うから、a_{p_1},a_{p_2},\dots,a_{p_n}という列において累積MAXを更新する要素を考えたくなる。そのような要素を取り出した列がa_{i_1}\le a_{i_2}\le\dots\le a_{i_m}となっているとしよう。ただしi_m=nである。まず、a_{i_{j+1}}-a_{i_j}\gt kが必要となる。

累積MAXを更新しない要素a_lがどこに並ぶか考える。a_l\le a_{i_j}なる最小のjを取ると、a_{i_j}-a_l\le kならa_{i_{j+1}}より後ろに並んでいる必要があり、そうでないならa_{i_j}より後ろのどこに並んでいてもよい。

以上の考察を元に挿入dpをした。aを降順に見れば、累積MAXを更新する要素として先頭に並べるか、後ろのほうに並べるかという遷移が考えられる。a_{i_j}という要素が累積MAXを更新すると決めたとき、a_{i_j}-k\le a_lなる要素a_lはすべてa_{i_{j+1}}の後ろに並べる必要があるので、このタイミングでまとめて並べておく。すると残っている要素はa_{i_j}の前に並べてa_{i_{j-1}}としてもよいし、後ろの任意の位置に並べてもよい。これで遷移が書ける。

20分残してノーペナ全完、4位。Gが全然解かれなかった。

実況動画を投稿し、食事してからはずっと先週の週記を書いていた。

www.youtube.com

集中が切れたタイミングでTLを見ると言語アップデートコンテストの話題が流れてきた。コードゴルフで使う言語くらいちょっとテストしようかな、と思って少し触っていたが、なんとRaku・OctaveVimがない。

Language Test 202301 - AtCoder

追加する言語を提案するスプレッドシートに名前だけ挙がっていて、実際のインストール方法が何一つ書かれていなかったようだ。Vimについては今見るとちゃんと埋められていたので、残りのRakuとOctaveを前回のスプレッドシートを参考に埋めておいた。一応手元のUbuntuで動作は確認している。

Octaveは現在AtCoderで使えるバージョンだと行列積がバグり散らかしている。これも最新版ではちゃんと直っているようだ。このバグのせいで露と消えた最短コードがいくつかあるはず。

昼前に一瞬外出した。学食で食事しラノベを受け取って帰ってきた。さらに週記を書き進め、何とか土曜日のオンサイト終了までは書き上げた。

しばらくコードゴルフして午後4時就寝。

03/24(金)

午後9時起床。20分からyukicoder 382に出た。

yukicoder contest 382 - yukicoder

Aは添え字を二つずつペアにしてz=xまたはz=yとなるものを探す。Nが奇数のときは余った一つが勝手に決まるのでクエリ回数がピッタリに収まる。かなり素早く思いつけてFAだった。

Bは3点を(0,0),(x,y),(y,x)と固定し、2(x-y)^2=x^2+y^2+1となるような(x,y)を探した。どちらかを全探索すると2次方程式を解くことでもう片方も求まる。ちょっと時間はかかったが無事一組見つけることができた。

ちなみに2(x-y)^2=x^2+y^2-1という式を立てると解は存在しない。xについて解くと\sqrt{3y^2-1}が整数になる必要があるが、平方数を3で割った余りが-1\equiv 2になることはないから。これは後から気づいたことで、コンテスト中はたまたま当たりを引いただけだった。

Cは実験。k+2\le Nなら2点swapができるらしい。k+1=Nならrotateとそのreverse合計2N通りのみを作れる。適切に場合分けすると後者で一致させられるかの判定問題になって、Z-algorithmで解ける。サンプルを見てなぜかk=1なら不可能だと思い込んでしまい2WAした。

Dはほとんどギャグ。行列式を順列に関する和と見て、和を取る順番を入れ替えて各順列が答えにどれだけ寄与するか考える。順列を固定したとき、計算に関わる要素以外に-1があると場合の数がPの倍数になるため寄与は0。よって考えるべき順列はA=-1なる要素をすべて含むようなもののみである。

線形性によってA=-1なる要素は0+1+\dots+P-1=P(P-1)/2だと思ってもよい。P\ge 3のときこれはPの倍数なのでまた寄与が0になる。P=2のときは1なので、残りの部分の寄与を計算する。-1が存在しない行・列を集めて行列式を計算すれば求まる。

Eはほとんど解けていたがN=6だけ構築できず時間内に通せなかった。ジャッジ詰まりでコンテストが10分伸びてもなお間に合わず、さらに2分弱遅れてAC。順位としては4完9位だった。

Eの基本方針は「最後に消えるのが右端の列で縦に並んだ3個」というパターンを2列ずつ伸ばしていくというものだった。3個が消える代わりに、それが下から3行に縦に並ぶことをトリガーとして次の列が消え始めるようなパターンを組んだ。

こう決めた後はひたすらペンシルパズルを頑張る問題なので、以下では結果だけ提示する。サンプルのN=3をベースにすると次のようになった。伸ばすときの2列は、登場する数字こそ変わっているもののパターンとしては同一である。

012    01267    0126712
549    54589    5458039
549    54689    5468139
500 => 50055 => 5005500
141    14186    1418631
229    22779    2277229

これでN=3,5,7,\dotsが可能。N=4はサンプルにある。N=6,8,\dotsについては右端に3列追加できるようなパターンを用意し、上のようにN-3列作った後くっつけた。これに関しても数字の違いを除き同一のパターンを使用している。

012    012558    01267    01267008
549    545883    54589    54580883
549    546779    54689    54681229
500 => 500449    50055 => 50055449
141    141664    14186    14186114
229    227339 ,  22779    22772339

N=1は自明、N=2は不可能。以上で解けた。コンテスト中にN=6が作れなかったのは、スタートの3列を上のものとは別パターンにしていて、うまく3列を追加できなかったからである。コンテスト終了直後にサンプルが流用できることに気づいた。非常に悔しい。

GitHubSSH鍵が変更されたらしい。正直よくわかっていないが、確かにgit pullすると以下のページにあるものと同様のエラーメッセージが出る。その下の手順に従って~/.ssh/known_hostsを更新し、何とかエラーメッセージもなく動くようにした。知識がほとんどなく大変だった。

github.blog

ラノベを読んでいたら寒気を感じて布団に潜り込んだ。その後当然のように寝落ちしたらしい。具体的な時刻を記憶していない。午前2時は回っていたと思う。

03/25(土)

午前7時過ぎ起床。昼までずっとラノベを読んでいた。2冊読了。

1冊目、「無能と言われ続けた魔導師、実は世界最強なのに幽閉されていたので自覚なし」2巻。この巻は主人公の無双シーンがほぼなく、ヒロインの一人の過去が語られるだけのちょっと印象の薄い巻だった。しかしラスト、主人公がその力を解き放つ直前で終わっていることに注目したい。こうやって1冊で話が終わらないラノベは最近見ていないので結構びっくりした。続刊が確定しているのだろうか。次巻が楽しみな終わり方だったので、そうだと嬉しい。

2冊目、「ネットの『推し』とリアルの『推し』が隣に引っ越してきた」。自分好みのシーンがたくさんあって良かった。以下ネガティブなことを言うので、基本的には面白かったということをまず強調しておく。

一度冷静になってしまうと、主人公が作った料理を自分の手作りだと言ってSNSにアップしたり、ホラーゲームが怖いからと言って主人公を隣に侍らせながら配信したりする女性VTuberというのがかなりマズいことに目が行く。主人公も彼女を炎上させたいわけではないから積極的に協力してはいるのだが、彼女が配信で手料理についてコメントを求められた際に何を言えばいいか困っているのを少し放置してからかうという描写があって、そんな些細なことですら危うく見えて読んでいてストレスを感じた。

2冊目を読み終えたのが正午を少し回ったところだった。そこから急いでシャワーを浴びて食事し、午後1時からUTPC2022に出た。

UTPC 2022 - AtCoder

書く

食事して少し日記を書き、午後9時からABC295に出た。

AtCoder Beginner Contest 295 - AtCoder

Aは面倒。紛れがないようまずC++で書き、直後にsedでも提出しておいた。この問題のコードゴルフはどれだけテストケースハックできるかという戦いになるので、とりあえず放置して次に進んだ。

Bはよい。Cは同じ要素を集めて個数を2で割ったものの総和。最初にRubytallyを使って通し、すぐ縮む問題だったのでPerlAWKでも書いておいた。

Dはすべての数字が偶数回ずつ出現していれば嬉しい列である。文字が小文字アルファベットで考える対象が回文という強化版が既出。この方法でZero-Sum Rangesと同様に数えればよい。

D - Yet Another Palindrome Partitioning

EはA_K\ge xである確率をx=1\dots Mで足し上げると求める期待値になる。それぞれの確率はA_i=0なる要素のうちいくつをx以上にするか全探索すれば計算できる。

Fは面倒だった。区間[L,R]を桁数が等しい区間に分解してそれぞれ求める。桁数を固定した後は主客転倒で、Sが現れる位置を全探索してそれぞれ区間に入る値を数え上げた。まずSより上の桁としてあり得る値の区間を二分探索で求める。区間の端に対してはSより下の桁もちゃんと考える必要があるが、適切に算数を行えばよい。区間の端でなければ下の桁はなんでも入れられる。

Gはやるべきことはすぐわかったのに実装に手間取った。根(頂点1)から葉への方向に辺が向きづけられた木が与えられて、後退辺を追加しながら強連結成分を管理する問題。後退辺の始点と終点が同じ強連結成分に属するまで、始点が属する成分とその「一つ上」の成分をマージしていけばよい。マージ回数が全体で高々N-1回になる。

この「一つ上」の成分とは、正確には今見ている成分の中で最も根に近い頂点の親が属する成分となる。これはクエリ2の答えにもなっているからどのみち取得できる必要がある。UFを使いつつこの値だけ持っておけばよかったのに、なぜかマージテクによって成分の全頂点を管理しようとしてしまった。

Exは簡単め。上の行から順に見つつ、一番上から今見ている行までずっと1が続いているマスがどれかという2^M通りの状態を持つdpを行った。新しい行を追加する際は最も左にある0の位置を固定すると、それより左は行に対する操作で1にできるから何でもOK、それより右は列に対する操作でしか1にできない、という制約になる。

後者については?をどう決めるかも考える必要がある。とりあえずできるだけ1にしておいて後から?があるbitに関してのみ上位集合の和を取るゼータ変換を行うことで、まとめて遷移を計算することができる。行のループと最左の0を決めたループの内側で毎回ゼータ変換を行うので計算量O(NM^22^M)、ただし定数倍2分の1がつき、1secだった。

ノーペナ全完6位。5位とも7位とも10分近く差が開いている。AやCで少しコードゴルフしていた時間がなくても順位は変わらないようだった。

少しだけコードゴルフ。Aはいろいろ試した結果、and・not・thatはそのまま、the・youは単語の先頭にあるものを探すというのがACできるギリギリだった。特に単語の一部だけ探そうとするとことごとくWAになった。かなり丁寧にテストケースが作られているらしい。

Cはコンテスト中のAWKが最短になっている。DもPerlで縮めたが負け。他は手付かずである。

このABCの動画を投稿してすぐ布団に入り、しばらくスマホを触った後午前1時から仮眠を取った。

www.youtube.com

午前3時少し前に起床し、すぐUniversal Cup 9回目。今日はQingdaoセット。

The 2018 ICPC Asia Qingdao Regional Contest - Dashboard - Contest - QOJ.ac

書く

午後3時半に布団に入るまではずっと日記を書いていた。布団に入ってからはしばらくハーメルンを読み、午後5時就寝。

03/26(日)

午後11時起床。時間をかけて布団から這い出し、半からのCF #860 div.2に出た。

Dashboard - Codeforces Round 860 (Div. 2) - Codeforces

Aはすべてa_i\le b_iと並べ替え判定する。Bは後ろから見るとその時点で選べる人なら誰を勝者としてもよい。出現したかを持つフラグ配列を毎回全部ゼロ埋めするのは計算量的に少し怖かったので、入力を読みながらa_{i,j}として現れた要素だけゼロ埋めした。

C。同じ値札cを付けられる区間[l,r]の条件を考えると、b_l,\dots,b_r\mid cかつc\mid a_lb_l,\dots,a_rb_rとなる。よって\mathrm{lcm}(b_l,dots,b_r)\mid\gcd(a_lb_l,\dots,a_rb_r)を判定すればよい。このことからlを固定したとき条件を満たすrは左端がl区間をなすことが言える。

実際に区間に分割していく際は右端のrを選んで損しない。各lに対してセグ木上の二分探索でrを求めdpした。実行時間的にも問題なく通ったが、コンテスト後にただの貪欲でよいことに気づいた。まったく同じことが2週間前にもあったのに、何も成長していない。

dpをした。後から貪欲でよいことを知った。

週記(2023/03/06-2023/03/12) - kotatsugameの日記

Dは面白かった。常にa=0なら明らかに不可能、それ以外は必ず可能。これまで置いた要素の和、つまり累積和が[0,\max-\min)の範囲から外れないように貪欲に要素を置ける。正の数が残っているのに置けないとき、現在の和が-\min以上になっているため、残っている負の数のどれを置いても負にならず範囲を外れないから。

E。まずf([a_1,\dots,a_n])の値を考える。a_1=1a_2=n-2とすることでaがmultitestになるためf\le 2である。f=0の判定はa_2,\dots,a_nがいくつのtestに分かれるか求めればよいだけ。f=1の判定は、a_1を書き換える場合f=0とほぼ同じで、そうでない場合どこかの項を書き換えるその項を先頭とするtestを作ることになる。

実はそのようにして作れるtestの数の最大値がa_1以上であることをチェックするだけでよい。書き換える位置を適切に変えることでtestのマージができるからである。

ある項を書き換えるときその右ならどの位置でも次のtestの先頭にできるため、累積MAXを持ちながら右からdpすることで求める最大値が手に入る。testへの分割も右から順に計算できるので、自動的にaのsuffix全てに対してfを求めることができる。

Fは全く分からなかったが偶然エスパーに成功した。まずaを適当に分配する。1個足りないので人数最大のクラスだけ1少なくしておく。この状態からスタートし、人数の昇順に、自分以上の人数を持つクラスとaを適切に入れ替えて条件を満たすようにした。最後に残ったクラスだけ追加する要素で調整する。念のためという気持ちで実装したらサンプルが合い、出したらそのまま通って仰天。

これが正当であるためには、任意の正整数nについて「どんな2n-1個の数からでもn個適切に選ぶと和をnの倍数にできる」という性質が成り立たなければならない。ここで2nではなく2n-1なのは、上で人数最大のクラスだけ1個足りないことを反映している。これは実は真で、EGZ theoremという名前が付いた定理らしい。証明方法はいろいろあるようだが以下のpdfに載っているものが必要最低限で分かりやすかった。

https://math.unice.fr/~pauly/Erdod-Ginzburg_Ziv.pdf

Fで1時間近く考察が進まなかったが何とか全完、17位。動画を投稿した。

www.youtube.com

ずっと日記を書き続け、午前10時過ぎ就寝。まだコンテストページが公開されていないがこの後午後3時からAtCoderでパ研合宿のコンテストがあるらしい。それまでには起きる予定。

先週は5hやオンサイトが立て込んでかなり疲れており、その反動からか今週は結構な時間をラノベを読んで過ごした。最近読めていなかったのでこの機会に10冊ばかり消化できて満足。




以上の内容はhttps://kotatsugame.hatenablog.com/entry/2023/03/27/234517より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14