/ 最近 .rdf 追記 設定 本棚

脳log[2024-09-21~]



2024年09月21日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2024 秋(ABC372)があった。脳みそがスポンジ化している。このごろは最初に問題をざっと読むんだけど、E までは普通に解けると思って、F 問題に時間をかけて考えて解けるかどうかだと見通しを立ててから A の実装に取りかかった。番狂わせの D 問題。E 問題を終了 20 秒前に提出するのがやっとだった。■A 問題「delete .」。String#tr メソッドは文字の削除もできます。つい最近他の人の提出で見るまで知らなかったけど、String#delete というメソッドもあります。■B 問題「3^A」。N が出力の制約だと気がつくまで時間がかかった。10 万個の数字を出力してもいいんですかと確かめるつもりで問題とサンプル(の上の方)を眺めてもまだわからなかった。制約さえ把握できたらあとは3進数。Integer#digits メソッドは基数を引数に取る。■C 問題「Count ABC Again」。つどカウントするわけにはいかないから、置換前に ABC の一部であればカウントを1減らし、置換後に ABC の一部であればカウントを1増やす。これも実装で下手をして答えが合わなかった。クエリの x を2回使うので、x を変更するのではなく別の変数にコピーしてから変更していたのだけど、最後に別の変数を参照するところで x を使用していた。■D 問題「Buildings」。来ました D 問題。21:26 に C 問題を提出してから 22:25 に D 問題を提出するまでほぼ1時間ぐだぐだやっていた。問題が全然頭に入ってこないの。いったい何を数えるんだよー。問題を完全に理解したのが 22 時 20 分! 理解したら実装は5分。「ビル i とビル j の間にビル j より高いビルが存在しない」という i と j のペアを数えるんだけど、えっとね、i のビルの高さはなんにも関係ないんだよ。サンプル1の解説とサンプル1の出力例を突き合わせて自分の理解の誤りが明らかになったのが 22 時 20 分だったのだ。出力形式もやっかい。合計じゃないんだよ、さりとて j を基準にした数字でもないんだよ。問題を解く筋道を規定されるようでとことん振り回された。解法は後ろから見ていって増加列の列を管理する。いや……ただの増加列なのか。無駄なことをしたかも。■E 問題「K-th Largest Connected Components」。一読してスター型のグラフに殺されるなどうしようかなと考えたときに k が 10 以下との制約が目に入って解けたと思った。連結な頂点のことを隣接頂点だと勘違いしていたのに気がついて途中で UnionFind を(頭の中から)ひっぱり出してきた。連結な頂点に自分自身を数えることも最初はわかっていなかった。Array#max メソッドの戻り値がソート済みではないと知らなかった。そんな感じで実装に 15 分。D 問題のせいで解ける E 問題を落とすのは悔しすぎるので残り 20 秒で間に合って良かった。■F 問題「Teleporting Takahashi 2」。30 分から1時間を残してじっくり考えたかったけど、すべては D 問題のせい。■F 問題。K×N の表を作成していて、K と N がどちらも大きいんだけど、k 行目の値を決めるのに斜めに k 項の和が欲しい。k の2乗はダメだ。左にあって一番近い意味のある頂点が t 個前にあるとして、k-t 番目の値を参照すればいいのかな。■■■F 問題。TLE×8TLE×27TLE×12。なんで最初が一番ましなのか。最初だけ送っていて、あと2つはもらっている。TSP 問題ではもらう方が速いのだけど、逆に遅くなる理由がどこにあるのかわからない。■AC! でも Ruby の他の提出では全部で4つの AC がいずれも 1500 ms 前後しかかけていない。自分のはやっとで 2055 ms。25 % 遅い。正直なにが AC と TLE を分けたのかもわかっていない。他の人の提出を読んだ(眺めた)けど、なんか遷移がシンプルだよね。DP のために用意する配列のサイズが N+K だったり N から継ぎ足して N+K だったり、最初から最後まで N だったりもする。自分は 2M×K の2次元配列(※)を使った。明らかに何かが違って効率が悪い。むむむ。※ C 言語では2次元配列と配列の配列(jagged array)を区別するけど、Ruby には片方しかないので……。■たぶんだけど、ある頂点の場合の数を記録している添字をずらしていくことで1つ先への移動をノーコストで行うんだと思う。初期にはそういうことも考えていたけど、移動したら移動元には場合の数が残らないはずなのに、考え違いをしていて一歩ずつ加算していかなければいけないような気がしていた。今日も実装を始めたときにはまだその勘違いをしていて、過大な答えが出たりしていた。勘違いで解法を潰してしまっていた。提出 #58036342 (AC / 1430 ms)。ほらね、1500 ms グループの仲間入り。提出の中でなんで y から x を引いてまた x を足してるのかはわかりません。差分が生きるような気がしたけど、気の迷いだった。


2024年09月19日 (木) [AtCoder] 精進。CodeQUEEN 2024 決勝の FG。E までしか解けなかった 20240823 の続き。時間をおくと勝手に解けるメソッド。なお、その時間が余命より短いか長いかはわかりません。■F 問題「Divide the Cake」。円環に切れ目ということで前々回の ABC370-F Cake Division を思い出す。ダブリングで解けるかなと考えてみるけど、解けない。どういう問題か。切れ目を1つ選んだとき、その切れ目から1切れ、2切れ、……、N-1 切れのまとまりのいずれもが、1切れあたりの平均において全体の平均を下回らないような、そういう切れ目を見つける。問題には選ばれなかった残りのピースの平均との比較が書いてあるけど、全体の平均と比較するのと同じことでしょう。平均をどう扱うか。累積和を1で割ってみたり2で割ってみたり3で割ってみたりするようでは O(N^2) になってしまう。濃度の二分探索では必要な溶質の質量との差分で考える。平均との差分の累積和を考えてみる。1切れの和、2切れの和、……、N-1 切れの和までの N-1 項の累積和のいずれもが0以上なら、どういう切り方をしても平均を下回ることがない。2周分の累積和をセグメント木に乗せて、N 回、N-1 幅の区間最小値を尋ねた。平均を考えるのに小数は使いたくないから、N で割る代わりに乗ってる数を N 倍した。そうすると全体の平均は元々の数の総和になる。それとの差分の累積和を考える。提出 #57894314 (AC / 636 Byte / 596 ms)。■G 問題「Quintuple Scoop Ice Cream」。二分探索っぽさがあるよね。衝撃の青 diff だった ABC227-D Project Planning みたいに、うまく判定する方法があるのではないか。わからないけど。あるフレーバーを選べる上限は 3K 個まで(1段目と3段目と5段目に)。1つのフレーバーを 3K 選んでしまったら、他のフレーバーは 2K までしか選べない。どのフレーバーも 2K 個までは何も考えずに使えるとも言える。2K を超えるフレーバーが1種類だけだったら、追加で K 個まで使える。2種類以上あったら……全部合わせて K 個まで追加できる。あとは使えるだけ使い切って 5K に足りているかどうかで判定する。提出 #57906057 (AC / 723 Byte / 351 ms)。判定するだけではなかった。トッピング例を構成しなければいけない。ABC362-F Perfect Matching on a Tree の解答を構成するのにプライオリティキューみたいな道具が必要ないように(20240713)、K 個ずつ5段にうまく並べたいと思ったけど、すっきりきれいにはできなかった。5段目を置くときに同じトッピングが最大で3個になるんだけど、必ずしも (A,B,A,C,A) にはならなくて、(A,B,C,A,A) とか (B,A,C,A,A) みたいなケースが考えられる。K 行に渡って泥臭く並べ替えた。■最後の H 問題はまだ。


2024年09月18日 (水) 自分ルールというものがある。自分のやることはたとえば8割が決まっていて(あれの場所はここ、これの順番はこう、こういうことはしない、などなど)、2割がどうでもよかったりする。そして他人。他の人にも守ってほしい譲れないルールというのは、多くても2割ほどではないか。そうすると全体の8割がどうでもいいことだということになる。2対6対2が、8対2になったり2対8になったりする。これをうっかりいつでも8対2にしてしまうと、8割のルールを押しつけようとしてしまうと、突き詰めれば「他人は自分ではない」という不満を常に抱き続けることになる。他人が他人として、尊重すべき別の個として見えていないとそうなる。強力な連帯感で結びついた集団の強さもあるかと思う。その幻想がまったく共有できないことは、しようのないことなのです。


2024年09月14日 (土) [AtCoder] 今日は AtCoder Beginner Contest 371 があった。今日も冴えなかった。C も D も E もやるだけのはずだけど、正しく実装できない。それぞれ 34 分、8分、21 分かけている。そして F もやるだけではある。ややこしいし時間が足りないし、X の制約のせいで BIT に SortedSet の代わりをさせることができなくて TLE を避ける方法がわからないけども。■A 問題「Jiro」。ABC のそれぞれを中心に置いて比較結果を並べたときに << もしくは >> になっているかどうか。これも4、5分かけたんだよね。どうにもすっきり実装できなかった。ソート関数に比較関数を渡すことも考えたけどやらなかった。他の人の提出を見ると、入力から2つを2回選んで比較するだけで答えが出せるみたい。■B 問題「Taro」。b=='F' は無視する。b=='M' のとき a が最初かどうか。これも実装で下手をして次男にも Yes と答えていた。■C 問題「Make Isomorphic」。N の制約が8以下ということで、8!*8*8/2 小なり 130 万なので頂点番号の入れ替えを全通り試すだけ。答えが合わなくてずーっとあれこれしていて、ついに明らかになった原因は、辺の操作コスト A を受け取るときに -1 していたことだった。勝手にコストを減らしてはいけない(二度と役に立たない戒め)。頂点番号を0始まりに補正するコードに引きずられて、コピペでもないのにマイナスしていた。グラフが2つと三角形のコスト表という、入力を受け取るのが一番難しい問題だった。■D 問題「1D Country」。累積和と二分探索。これ D 問題かなあ。二分探索の境界のイコールの有無と、数列の添字と累積和の添字の区別に注意をする。こういうことをどこかで読んだことはないんだけど、C++ の2種類の二分探索が lower_bound と upper_bound なのって、イテレータの半開区間の下限がイコール付きで上限がイコールなしなのを踏まえた命名であって、本来それだけの意味しかないよね? C++ を離れたら通じないよね?■E 問題「I Hate Sigma Problems」。主客転倒で数字ごとに寄与する範囲の数を数える。ここまで 20 秒かからないのに結局 21 分かけてるのはなんで? 2つ目のシグマが j=i から始まってると認識したのが遅かった。そこからはまともに範囲の選び方を考える(考え直す)ことができなかった。範囲の選び方が N*N かな N*(N-1)/2 かな N*(N+1)/2 かなと定まらないのは 20240831 とまったく同じ展開。他には余事象を試してみたり、答えが合わないせいでいつまでも思いつく限りのテキトーをやっていた。愚かだ。■F 問題「Takahashi in Narrow Road」。集団を寄せて移動するのは ABC365-F Takahashi on Grid を思い起こさせる。違うのは集団の中ほどで分裂することがあることかな。それでも集団の数は N 個を超えないし、クエリごとに集団の数が0個以上減る一方、増える数は最大で1個なので、ソートした状態で集団(端の位置、幅(=数)、累積数)の管理ができれば良さそう。併合分裂は N+Q のオーダー。でも道具がない。X の値域が広いために BIT で管理するためにはとりうる値が予め列挙できなければいけないが、できない。■■■予め値を列挙しておかなくても自動的になんとかしてくれる BITSet を盆栽したけども、普通に BIT を使う場合より 2.5 倍くらい遅くなった。たとえば制限時間5秒の問題 ABC365-F への提出で 2675 ms かかっている #56361608 が 2.5 倍遅くなると TLE になるんだよね。ABC371-F への Ruby での提出が未だゼロなのは、つまり、あきらめなのですか? 制限時間3秒だしなあ。■■■F 問題。提出 #57862947 (Ruby / TLE×3)。普通に配列の要素を削除・挿入しただけだけど、35 ケースは通った。TLE のケースが実際にどれだけかかるのか、4秒なのか、30 秒なのか。C++ で map を使ったものは 289 ms で通った>提出 #57864113 (C++ / AC)。C++ で提出時刻が早いものを見てると、LazySegtree を使うものが多いみたい。それはどういう解法か……。■F 問題。Ruby で通った! 提出 #57872364 (Ruby / AC / 1772 Byte / 1047 ms)。値が大きいから座標は BIT の添字にできないけど、累積人数を BIT の添字にすることはできる。N=9 だとして、座標左から 2,3,4 人の3つの集団があるとすると、BIT の 0 から N+1 の範囲に 0,2,2,5,5,5,9,9,9,9,10 という値を記録する。両端は番兵(提出コードで番兵を使っていないのは(69 行目と 86 行目)、バグがあると番兵が機能しないからなのですね。普通に処理対象にされて削除されてしまう番兵さん……)。座標は累積人数(2,5,9)を添字にして配列から引く。BIT 上の二分探索で隣の集団を見つけることができるけど、対数時間がかかるのをケチってこれも配列(Pv,Nx)に記録した。なんとかなってしまうものだなあ。そうするとコンテストで通せないのは精進が足りないせいってことになる。それは……つらい。■実は累積人数をキーにする発想は C++ で map を利用するときに必要に迫られて出て来たものだった。最初は、座標をキーにしてソートしておきながら、値のひとつである累積人数を参照して二分探索をしたいと思っていたが( T 番目の高橋くんを見つけるために)、そういうことをする比較関数を渡すことはできなかった。それは当たり前の話で、キーについてソートされているなら、キーについてしか二分探索はできない。値である累積人数で二分探索できると思ったのは、座標でソートした結果が累積人数でソートした結果と同じだと知っていたからで、だけど座標をキーにするのも累積人数をキーにするのも同じことだとはまだ気がついていなかった。■■■F 問題。LazySegtree で解いていた何人かが座標を補正することで高橋くんの幅をゼロにしているようだった。なんのこっちゃ。たとえば t 番目の高橋くんが座標 g に移動するとき、t+1 番目の高橋くんは g+1 を下限とするように、t+2 番目の高橋くんは g+2 を下限とするように移動しなければいけないし、逆を見れば t-1 番目の高橋くんは g-1 を上限とするように、t-2 番目の高橋くんは g-2 を上限とするように移動しなければいけないのだけど、t 番目というのを座標に織り込んでしまうことで、全員が同じ座標を目指すことができる。これは BIT を使う場合にも嬉しいことがあって、座標の数が N+Q 個に絞られるので座標圧縮ができる。提出 #57916028 (AC / 1503 Byte / 1366 ms)。最初の提出よりやや短く素直に実装できてるけど、座標の補正(35 行目と 41 行目)がややこしい。特に目的地の補正の必要性と、どう補正するかが、なかなかわからなかった。要するに、今やっとわかったけど、1人目の高橋くんだった~という座標に初期位置をずらし、1人目の高橋くんだったら~という座標に目的地をずらしているのだ。こういうテクニックは過去に2回利用したことがあり、そのときはポテンシャル云々と勝手に呼んでいたけど、今回のように目的とメリットが見えにくいなかで発想するのは難しい。実際に座圧できるというメリットがあったんだけど、テクニックを提示されてさえすぐにそうとは気付けなかった。


2024年09月12日 (木) 昔コンビニで働いてたときに「お箸つけますか」と尋ねると「いらない、家で食べるから」とか「いらない、箸持ってきてるもん」みたいに「なぜいらないのか」をいちいち説明してくる人がたまにいて、すごく嫌だった - Togetter [トゥギャッター]」■わりと共感する声が多くて困惑してる。まるで理解できない。もとのツイートとは別の人だけど、そういう考え方もあるのかなと思ったのがこれ。「コンビニ店員やってるときにこれはいやだなあ。コンビニ接客なんぞに自分の大事な人格を使いたくない。ヒト型の機械でありたい。お友達の誘いを断るときなんかにはもちろん理由添えますよ、ごめんなさい暑さで参ってて公園いけないんです(あなたが嫌いなんじゃないよやむをえないことなのよ)とか、でもコンビニの箸ごときにそういう体温入れたくない〜!!!」 要するに、正反対のものを求めているのだ。自分は人間を機械扱いすることに気が咎めるけど、レジの向こうでは機械でありたいと望まれていた。「いりますか」「いらない」を望まれていた。すでにこちらが非人間の扱いだった(自分が欲しい返答しか許容しないというのは傲慢なのよ。機械なら嫌とも感じずにこなしなさい)。自分はこういう人間のふりをした機械には、人間のふりをしているという理由で腹が立つので、さっさと人間をやめて機械になってもらっていいかな。機械の動きしかしないのがヒトの顔を貼り付けて立っていることがもうトラブルの種なんだ。実際にトラブルを起こすと老害って声で埋め尽くされるのを見てきているので自戒するけども。こういうミスマッチがあるなあと「老害」に感情移入して眺めていたのだ。だけど機械になりたがっているとは想像もしなかった。マニュアル人間って、機械にしかなれない人間を指す言葉だと思っていた。元々のツイートについては何が嫌か書かれていないので真意はわかりませんよ。


2024年09月07日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#9(AtCoder Beginner Contest 370)があった。解ける問題が順当に解けたというだけでここ数回の調子の悪さが底を打ったのかと喜びたくなる悲しみ。茶パフォとか緑パフォとかありえないんだから。今日は青パフォ。嬉しいけど手放しではない。たぶん F 問題に壁があっただけ。高すぎる壁が普段 F 問題が解けない自分と普段 F 問題を通している人を同じ早解きの土俵に放り込んだだけ。■A 問題「Raise Both Hands」。考えずに3通り場合分け。シンタックスエラーがいつまでも解消できなくて悪戦苦闘していた。代入がそうであるように、解釈がひと通りなら演算子の優先順位にこだわらない融通が Ruby には期待できるのだけど、今日のはたぶんハッシュリテラルとブロック構文とキーワード引数のお呼びでないどれかがシンタックスを奪い取って、あげくエラーを出していた。波括弧と => が組み合わさったらハッシュリテラルしか解釈のしようがないやろと期待したのだけど。しかもエラーが Hash の 'key'=>'value''value' の部分を指して「syntax error, unexpected string literal, expecting local variable or method」と出るから意味がわからなかった。'key'=>'value''key'=>value に書き換えたからって有効な構文にはならんやろ。なんかよくわからん => がある、というエラーなら解釈違いだと理解できたのだけど。■B 問題「Binary Alchemy」。1-indexed なのがやっかいといえばやっかい。Ruby での提出を見ると WA がちらほらと、B 問題にしては多い目に確認できて、だいたいどれも元素1に対して元素2から N を作用させているようだった。無視できないレベルでパターン化できそうな間違え方だと思った。■C 問題「Word Ladder」。要素数最小が最初に求められているので、S の各文字を T の各文字に一致させていく操作しかできない。操作には S の文字を大きくする操作と小さくする操作がある。前から小さくし、後ろから大きくする。■D 問題「Cross Explosion」。BIT を使ったけど本当は D 問題に BIT は使いたくない。Ruby での他の人の提出を見ると、同じように BIT を使っている人のほかに UnionFind を使っている人がいた。これはまったく想像がつかない。ほかに BIT より効率的な実装をしている人もいた(#57555275)。■E 問題「Avoid K Partition」。わりと途方に暮れる制約。DP がしたいんだけど、K がでかいし A もでかいので、この2つで状態数を抑え込むことはできない。数列を左から見ていって現在の要素を終端とする全累積和を列挙することはできるけど……。自分が解けなくて4年のあいだ問題を開いて考えて実装しては答えが合わなくて閉じるということを繰り返していた ABC017-D サプリメントに似てるのかな。この問題を思い出して、似てるなら時間内には解けないだろうなと恐れていた。A 数列の2番目以降の要素について、直前に区切りを入れた場合と入れない場合を考えていく。制約を乗り越えるポイントは、区切りを入れない場合に DP 配列をそのまま次の要素にパスできるように状態を記録すること。全体に一律に加算するなら、実際には加算せず加算する値だけを記録する。初期値を決めるところで手間取った。どう初期値を決めても N 個の A 数列を処理すると答えが合わなかったので、最初の1要素を取り出して初期値とした。■F 問題「Cake Division」。完全に途方に暮れる制約。答えの形式から何か手がかりが得られたりしないかな。しないか。■D 問題。BIT より効率的な実装をしようとしたら UnionFind の Find 関数みたいなものを書いていた。UnionFind 解ってつまりそういうこと? 提出 #57562030 (AC)。各マスに上(下左右)にある壁の位置を記録しておき、このマスに壁がある、というところまでマスを辿る。辿った結果を書き込むことで経路圧縮になる。■■■精進。F 問題。二分探索はわかる。その中で、N 個の切れ目のそれぞれを1カット目とする N 個の累積和について解の判定をするのもコンテスト中にやっていた。そのとき気付かなかったのは、ある切れ目を1カット目とする累積和が最適解を満たさない場合、その切れ目は最適解を満たすどの切り方においてもカットされないということ。つまり答えの2項目目がこのようにして数えられる。そしてもうひとつわからなかったのがダブリング。コンテスト終了後に目に入ってきていた。あとは実装するだけだけど、他の部分が Nlog^2 だからと尺取りできるところで2つ目の log を付けると TLE になるので、オーダーに影響しない定数倍の改善にも励む。■提出 #57605764 (AC / 480 Byte / 4781 ms)。これはコンテスト中には通せません。オーダー的には問題ないはずの提出 #57604731 (TLE×60) がサンプル以外通らなかった。これをコードテストで9秒、7秒と改善していった結果がさっきの AC。定数倍改善に1時間近くかけた。やったことは主に3つ。1.二分探索を尺取りで置き換え。2.N 回のコールバック(ブロック実行)を伴うメソッド呼び出しを N 引数のメソッド呼び出しで置き換え。3.判定関数をこころを込めてインライン展開。コピペをしたくないからペナルティを承知で関数化していたので、代わりにトリッキーなことをしてる(lastcut 変数)。■この問題を DP 的な状態をたたみ込む視点で眺めると、ある切れ目でカットするというとき、それが何カット目であろうとも以降に起こることは同じであり予め計算して結果を流用できるということ。ややこしいのは円環であることから、1カット目の位置に応じてありうる最終カットの位置が変わるということと、1カット目の位置を変えた N 通りを並行して考えないといけないあたり。だけど2周分だけ考えれば間に合う。


2024年09月05日 (木) [AtCoder] 精進。ABC369-G「As far as possible」。なにやら「貪欲法」「HLD」の文字が目に入ってきていた。だからといって、なるほど、そう言われてみればそうか、とはならなかったので、なかなかに難しい。同じ問題がまた出てもやはり解けないだろう。実装の練習だと割り切ってどのように実装するかを考えた。BIT……セグメント木(ちゃんとしたやつだと区間加算をしながら区間 max を取得したりできるの?)……オイラーツアー……マージテクの巻き戻し……。■提出 #57459978 (AC / 1442 Byte / 1308 ms)。マージテクは必要なかった。最も遠くがどれだけ遠いかだけを葉から根へ積み上げていった。候補の中から最も遠くへ通じている枝を選ぶのにはプライオリティキューを使った。■Ruby によるすべての提出を見るとゴルファーがひとりいるだけだった。提出 #57339115 (173 Byte / 936 ms)。あきれるほかない。入出力とソートをしているだけにしか見えない。短く、そして速い。そんなのおかしいよ。■こちらのブログ「ABC369 - merom686's blog」から「木全体で一つのvectorに突っ込んでしまえる」「自分は子への辺を2回走査したが、解説の実装例では1回しかやってなくて」「最大値を更新するタイミングでそれまでの最大値を(最大値である可能性が今なくなったので)vectorに入れていた」というのを手がかりにして、なんとか1パスで、最大値を取り合うような実装をひねり出した。提出 #57461586 (AC / 321 Byte / 822 ms)。提出したあとでもまだ化かされてる気がしてる。答えが見えなければ実装法も見えない。難しすぎる。■■■けんちょんの解説が上がっていた。「AtCoder ABC 369 G - As far as possible (3D, 黄色, 600 点) - けんちょんの競プロ精進記録」。そこに「ここで重要な考察として、 K = 2, 3, \dots のときは、頂点 v_{1} を使うものとしてよいことがわかる」と書かれているが、自分が思考停止してしまったのがここで(つまりわからなかった)、K=2 の場合に K=1 の答えを選ばない最適解があるような気がしてしまったのだった。読んでも頂点の位置関係がうまく把握できなかったので自分で考えますよ。K=1 の頂点 V1 とは異なる V2、V3 を青木君が選んだとする。他に根 V0 と、V2、V3 の LCA として C0 が頂点として存在する。V0=C0 の場合もある。いま、V1 と V2、V3 との LCA が C0 より根に近いか、V2、V3 の方に近いかを考える。LCA が C0 と一致する、もしくは V2(V3) に近いとすると、V2(V3) を V1 に置き換えた方が青木君の得になる。置き換えても V1、V2 と V3 との関係は変わらない一方、LCA より先は V2 より V1 の方が長いのだから。LCA が C0 より根に近い場合も頂点を置き換えた方が青木君の得になるし、LCA と C0 との距離の分だけよりスコアを稼ぐことができる。K=3、4... についてはわからないけど、けんちょんのページには書いてありますよ。コンテストのことを考えると難しいのは、「K=2 の場合に K=1 の答えを選ばない最適解があるような気がしてしまった」ときに、それは最適ではないのではないかと疑って、自分の直感を否定するような証明を考えることができるのかということ。できないんだよなあ。たぶんこうでしょで深く考えないのが自分の性分であれば。間違いだとはっきりするまで間違いを疑ってもいいことないじゃない。


2024年08月31日 (土) [AtCoder] 今日は AtCoder Beginner Contest 369 があった。■A 問題「369」。提出直前にサンプルを試すんだけど、3パターンが網羅されてるのは優しい。サンプル1のパターンを数え間違えていた。■B 問題「Piano 3」。問題文の「最小」のワードがどこに起因するのか考えてしまったけど、最初にどこに手を置いていたかで疲労度が変わってくるのね。それが確認できれば、片方の手を全く使わない場合にランタイムエラーを出さないように注意するだけ。■C 問題「Count Arithmetic Subarrays」。すべての範囲の選び方を数えるにしては C 問題らしからぬ制約の大きさ。一瞬考えた。ある範囲を等差数列として切り出したなら、その一部が別の等差数列の一部になることはないので、線形時間で数えられる。しかし詰まった。端っこの1要素が隣の範囲とオーバーラップするんだよね。要素数1の等差数列を過不足なく数えなければいけない。それとは別に、等差数列の長さが最大で L だとわかったとき、範囲の選び方が数えられなくても詰まった。最初は長さの2乗だと思った。それは右から左への範囲も含んでいる。次に手の指を使って長さ5の範囲を数えて、「え、階乗?」ととんちきな驚き方をして、違う違う 5*4*3*2*1 ではなく 5+4+3+2+1 だから…… n の場合は……1から n までのシグマ k は……わかんない、みたいなあほさで時間をとかしていた。頭が働かないときってあるよね。いつもこうじゃないよ、ほんとだよ。■D 問題「Bonus EXP」。ABC365-D AtCoder Janken 3 が解けなかったときのことを覚えている(20240803)。直前の2状態を記録・更新する DP。■E 問題「Sightseeing Tour」。N が 500 以下ではなく 400 以下であるあたりに温情を感じる。クエリが 3000 以下。クエリあたりの辺の数が5本以下。辺の並びと辺の向きを総当たりすると 3840 通り。3000×3840<1200万は通る。あとは全点間距離を O(N^3) で求めておけばいい。ということを確認してから飛ばした。400^3=6400万は N≦500 だった過去問に比べれば手心が加わっているといえるが、N≦300 でないと十分ではない。サーバースペックが向上していれば結果はわからないが、我が身で確かめるつもりがない。@翌日。たぶん実装したらしたで、今日になるまですっかり忘れていた多重辺への対応漏れで WA を出していただろう。ちゃんと自己辺はないけど多重辺はあるかもって明記してあったのにね。いっつも「単純」だから対応に慣れていない。■F 問題「Gather Coins」。問題自体は難しくない。よくある問題。BIT で列をキーとした情報を管理更新しながら行方向に処理を進めていけば効率的に数えられる。答えを提出しようとしてびっくりしたよね。経路の復元をしなければいけない。情報の持ち方に迷って何度もやり直しているうち、いつの間にか ABC360-G Suitable Edit for LIS でやった LIS の履歴の操作みたいなことをさせられていた(20240701)。提出 #57333067 (AC / 980 Byte / 653 ms)。時間内には通せませんでした。■tinsep19 さんの BIT を使わない提出 #57315658 を見て思ったんだけど、普通に(順方向に)経路を記録しながら LIS をするんで良かったんやろか。やってみた。F 問題の BIT なしバージョン。提出 #57336605 (AC / 690 Byte / 823 ms)。やっぱりやってることは LIS なんだなあ。ただし、履歴が必要。複製せずに履歴を分岐させたいので、リンクリストの頭を継ぎ足していく感じで LIS の記録をした(i を記録したのは無駄だった)。git のコミット履歴的な。そうすると、答えを作成するためにリストを後ろから前からたどらなければいけないややこしさは同じだった。■見たことのある解ける問題が6問並んでいて ABCD の4完は冴えないなあ。■■■精進。E 問題。提出 #57365216 (AC / 694 Byte / 3035 ms)。丁寧に 25 分かけて素直に実装したら、制限時間4秒のところ3秒強で一発 AC だった。Ruby が負っている定数倍のハンデについて認識を改める必要があるのかな。それでも昨日のムーブとしては、解ける問題のうち配点の高い F を優先するので間違ってなかった。両方を解く時間はどのみちなかったのだし、E 問題に至っては Ruby を使っている限りどうにもならない可能性もあったのだから。■精進2。E 問題。提出 #57365396 (AC / 692 Byte / 1965 ms)。前半のワーシャルフロイド部分のループをたぶん半分にしたらケースごとにばらつきがあるけど最大で倍くらい速くなった。無向グラフであることを利用したってことになるのかな。時間外ならこういうのも楽しいけどね。ところで、ループ部分をイチから書き直して、途中で再度書き直したんだけど、その結果が2行だけ数文字だけの差分になってるのちょっとすごい。まるでそこだけちょちょいと修正したみたいじゃないか。ところでところで、最初の提出からそうしてるんだけど、後半部分に D 問題プラスアルファの解答がまるまる入ってるんだよね。D 問題と同じ DP をしている。直後の E 問題がこれでは D 問題さんの立つ瀬がない。■■■取り繕います。普段なら 5+4+3+2+1=155*6=30=15*2 から、n+(n-1)+...+1=n*(n+1)/2 というふうに左辺と右辺が繋がって、終点と始点が一致していてはいけない場合(nC2=n*(n-1)/2)との区別を確かめてからスクリプトに埋め込むんだけど、最初の階乗のせいで何も考えられなくなった。全体の和(5+4+3+2+1=15)を数えているあいだに何を数えているのかを忘れ、目的を思い出しているあいだに数えた和を忘れるという始末。深刻だ。


2024年08月24日 (土) [AtCoder] 今日は日立ヴァンタラプログラミングコンテスト2024(AtCoder Beginner Contest 368)があった。ペナルティでぼろぼろになりながらすべりこみで ABCDE の5完で満足してるんだけど、E と同配点の F が通されすぎでは?■ A 問題「Cut」。pop(K) かなと思ったけど、出力のしやすさから rotate(-K) にした。irb で確かめたら rotate(K) ではなかったから rotate(-K) にした。下から K 枚といういやらしい設定はちゃんと読めていた。■ B 問題「Decrease 2 max elements」。偶奇によらず A.sum/2 で間違いないことを確かめたと思ったらサンプルの2に殺された。場合分けをして祈りながら出した。こんなにはらはらさせられる B 問題はそうそうない。あ、シミュレートできる制約なんだ。無駄に考えてしまった。でも 100×100×100=100万のオーダーだと見積もるのも簡単ではないね。■ C 問題「Triple Attack」。シミュレートします。その際に、1周期(T を3増やして体力を5減らす)を超える処理は周期数を数えて一括して計算します。サイクルはどこから数えても1周した結果が同じだということを都合良く利用します。■ D 問題「Minimum Steiner Tree」。シュタイナー木とは見かけた名前だけど中身は知らない。調べませんよ。頂点を輪っかに並べて最小限の頂点と辺を選ぶアルゴリズムがあった気がしたけど、覚えていない。調べませんよ。テキトーに根を決めて、深さを計って、最も深い所から浅いほうへ向かって、必須の頂点を種にして、1つだけの共通祖先に行き着くまで親を取り込んでいくようにした。根に収束していくので頂点数程度の操作回数。テキトーに根を決めていいのか考えたけど、木は頂点間のパスが一意に決まるのでどこが根とか関係なさそう。終了条件を間違えて1ペナ。無条件にテキトーに決めた根までさかのぼってしまっていた。中断するときは、最も浅いところにある指定された頂点を取り込み忘れないようにする。X で見たけど、テキトーに決める根を V1 なり Vk なり必須の頂点の1つにしておけば何の面倒もなかったらしい。それは……頭がいいね。調べないと書いた2つ目は Auxiliary Tree という名前だったと X で見て思い出した。読めない名前はそのぶん手がかりが少なくて思い出しにくいかもね。そしてこれはこの問題には不適だったとも書いてあった。■ E 問題「Train Delay」。問題文が難しい。サンプルも利用して理解したところでは、ある1つの電車が遅延したとき、遅延によってできたはずの乗り換えが不可能にならないように、連鎖的に後ろの電車を遅延させていくと、遅延の合計はいくつになりますか、というもの。答えに選択要素はなく、無駄なく遅延させていけば答えになる。効率的にやるのが難しい。最初は電車の組み合わせを考えた。ある駅で発着する電車と電車で相互作用をさせる(相互ではない)。30 分かけて書いたこれは TLE だった。遅延の伝播をアドホックにやるのではなくトポロジカルソート順にやるのかと思って5分で書き直したものは、1つだけ TLE が減ったけどまだ TLE だった。たとえば半分の電車が駅1を発ち、半分の電車が駅1に着くとき、電車と電車の組み合わせは M^2 のオーダーなのだから、TLE はしかたがない。こういう、ダメな理由は、いざ TLE が出るまで考えないのです。途方に暮れていた時間を含めて 25 分でイベントソート版をでっちあげたら、総取っ替えの大手術だったにもかかわらず、TLE なしの WA×2 で筋が良い。その後5分で AC に至る。終了1分前。WA の原因は同時刻の発着を必ずしも着→発の順に処理していなかったこと。着イベントと発イベントを時系列順に再生しながら、駅ごとに最後に到着した電車の時刻(遅延込み)を記録しておくだけで伝播する遅延を確定していける。提出 #57090926 (AC / 397 Byte / 1847 ms)。昨日の日記(20240823)に「イベントを時系列順に並べることで考えるべき対象が限定できる」と書いていたことを思い出せたのが打開のきっかけ。■ F 問題「Dividing Game」。配点が同じなので最初に実装を始める前に F 問題まで問題を読んでいた。「ゲーム、Nim、Grundy 数、うっ、頭が……」ということだけ確認してから A 問題からの実装を始めた。F 問題が簡単だとは言わない。自分には解けない。答えに至る論理の道筋を納得しながら辿ることができないので。Nim の必勝法とか XOR のあたりで論理がお隠れになる。だから他の人も同じように解けないでいて欲しいのだけど、順位表を見ると 2454 人が通している。それはおかしいよ、俺に優しくないよ。ちなみに E 問題の方は 327 人。問題文が難しいし長かったからね、読みたくないからしかたないね。■自分のすべての提出。■精進……失敗。G 問題「Add and Multiply Queries」。前々回の F 問題 Maximum Composition を思い起こさせる設定。セグメント木なのかな、自分には乗せられないなと思っていたけど、「A,Bは正なのと、3つ目のクエリの条件より、区間内にB[i]が2以上な物は高々log(10^18)個程度しかない。B[i]=1の部分は、v+=A[i]をした方が良いのは明らか。よって各クエリに対し、B[i]=1の部分はBITを使ってA[i]の和を一気に加算し、B[i]>1のところだけ加算と乗算どちらを取るか両方試していこう。」というのを読めば自分でも実装できる。提出 #57100689 (TLE×1)。こんなのってないよ。■最近タイプミスが多すぎるんだけど、たぶん爪が長い。白い部分が長いもので 6 mm ある(モニターの前に裁縫用のメジャーがあります)。短いのは 0 mm。むしろマイナス。ついつい噛んだり裂いたりしてなくなってしまいがちなので、触らないようにして最近は保護が行き過ぎている。長い爪というのは他の爪を攻撃しやすいのであり、また、長い爪というのは側面のちょっとしたささくれからぺりぺりと裂かれやすいのであり、攻撃力が高く防御力は低く、たいへん失われやすいものであるので、衝動を抑えていられる限りアンタッチャブルにしておきたいと思っているが、不便だな。ということをこの場所に書いているからには、不便を感じる機会が他にはあまりないということなんだな。■■■精進成功。G 問題。提出 #57153896 (AC / 918 Byte / 1161 ms)。配列の全長が高々 60 だとわかっていれば、長さ N の仮想配列に対する対数オーダーの処理を提供する BIT を使う必要はなくて、普通の配列に線形オーダーの基礎的な操作を施す方が定数倍がいいという話。というより、「次」を見つけるのに対数時間ではなく定数時間で済むという付加価値が大きいのかな。これでネタバレを恐れずに Ruby で唯一の AC だった konayuki さんの提出 #57098548 (AC / 1861 ms) を見に行ったら、クエリ3の答えをメモしていた。そう、1ケースだけだから、どういうクエリに弱いかを特定して対処しようと自分も考えていた。でもテストケースが見られないとなかなかわからないよね。■ちょっと勘違いをしていた。クエリ3の計算結果に制約があるのであって、1<Bi (i=1..N) なる要素の数が制約されているわけではない。だから B 数列の2以上の要素を管理するのに BIT ではなく Array を使うのにはリスクがある。ほとんどがクエリ2であるテストケースがあったら O(QN) で TLE だった。


2024年08月23日 (金) [AtCoder] 精進。CodeQUEEN 2024 決勝の ABCDE。配点の通り ABC の ABDDEFFG みたいな問題セットだったと思う。6問目は解けてないし7、8問目は問題を読んでもいないけど、5問目までは ABC の ABDDE とか ABDEE みたいな感じの難しさ。■ A 問題「Welcome to AtCoder Land 2」。参加者に必ず何かを持ち帰ってもらう問題。提出 #57008363 (AC)。■ B 問題「Decode Time Signal」。こういう問題は、問題文で与えられたモールス符号の表をいかに手を加えずに利用するかだと思う。プログラムというのは可変部分をデータファイルや設定ファイルに押し出して、最小限の共通部分をコードにすることで、複雑さを抑えながら最大限の表現力が得られるもの。符号表を手作業で Ruby スクリプト(Hash リテラル)に加工するようなことは避けたい。提出 #57008436 (AC)。そういうお前は %w[...] リテラルに加工したけどな。■ C 問題「Attraction on Rainy Day」。配点は ABC-D。30 分かかった。KN≦2000万だから O(KN) が通らない可能性があって、余分に考えてしまった。DP なんだけど何をキーにして何を記録するのかひと目ではわからない。変数は「現在時刻」「濡れた量の総和」「アトラクションに乗った回数」。時刻ごと乗った回数ごとに濡れた量の総和を最小化する DP をする。スタートとゴールに近いときは考えるべき乗った回数が制約されるので、そこでループの回数をケチった。提出 #57009112 (AC / 1387 ms)。■ D 問題「Attend Many Events」。450 点。難しかった。30 分プラス2ペナ。頂点と辺とイベントの数がいずれも 1000 以下なので、いずれか2つの組み合わせが 100 万のオーダーで許される制約。イベントに参加するしないを総当たりはできないけど、イベントを時系列順に並べることで考えるべき対象が限定できる。つまり、あるイベントに参加するというとき、人の位置と時刻がそのイベントによって固定される。そのイベントに参加できるかどうかは、最後に参加したイベントもしくはスタート地点との距離によって決まる。過去のイベントを見て参加可能かどうか、それまでにいくつのイベントに参加しているかを見て最大のものを選んで現在のイベントに第3のパラメータとして記録する。O(KK) で許された。2地点間の距離は予め求めておく。2乗のアルゴリズムが許されるのでダイクストラ法を使わないで BFS/DFS でもたぶん大丈夫。提出 #57009717 (AC / 274 ms)。一度 WA を出した原因は、過去のイベントの中にはどうやっても参加不可能なものがあるということを適切に取り扱えていなかったこと。イベントに参加できていなかったのなら、その時刻その地点に居たという事実が存在しない、ということをきちんと反映させる。ところで、2乗のアルゴリズムを全頂点で実行したら3乗になってやばいのでは? なんで全点間距離を愚直に求めて許された? だからこその 1000 以下という、次の E 問題より小さい、2乗掛ける log が許されるやや小さめの制約か。■ E 問題「AtCoder Hotel」。どの制約も 5000 以下ということで、2乗の DP が許されたり TLE になったりしそう。何をキーにして何を記録する DP をしようか。結論を書くと C4B という変数名がすべて。つまり、B 人分の定員を確保するために C 円払ったということを記録する。B がキーで C が値。C を最小化する。ランクはどうなった? これは人をランク要求で、客室をランクでソートすることで暗黙的に処理できる。客室ランクは大が小を兼ねるので、最もランク要求が厳しい人を満足させられる部屋だけで DP を行ったなら、その結果は次の人に対しても通用する。ただし、前の人が収まっているのでキャパシティが1減っている。提出 #57010115 (AC / 657 ms)。収容可能な人数として考慮すべき最大が徐々に減っていくのを考慮することでループの回数をケチった。C 問題と似たことを書いてるけど、こちらは 20 分しかかけていないので、C より E の方が簡単か。■ F 問題「Divide the Cake」。求められている答えから、更新しながら順番に判定をして最初の答えを見つけるんだと思うけど、どういう形式で記録すると高速に判定と更新ができるのかわからない。


2024年08月17日 (土) [AtCoder] 今日は AtCoder Beginner Contest 367 があった。最終的には嬉しい結果だったけど、かけた時間で難易度を判定すると E<F<<<<D なのが複雑な気持ちにさせる。もっと早く D が解けても良かったのでは? 以下ふりかえり。■A 問題「Shout Everyday」。スマートに解くことができない。ループを回して %24 で現在時刻を表し、それが A 時ならたこ焼きへの愛を叫び、それが B 時ならループを終了した。■B 問題「Cut .0」。String#chomp! という便利なメソッドがあるので、無条件に5回呼び出した。■C 問題「Enumerate Sequences」。5の8乗掛ける8が数百万のレベルだったので、Array#product で全数列を列挙して選んで出力した。■D 問題「Pedometer」。問題文を読んでもいない G を除けば本日のボス問題。やり方は少し考えるとわかった。最初に累積和を用意すれば、頂点1から自身を除く他の N-1 個の頂点までの距離の一覧が得られる。この一覧を更新しながら、全頂点について、条件を満たす他の頂点を数えるのが方針。条件というのが M の倍数となっているけど、デバッグのためには %M が邪魔なので、うまいことできればいいですね! 自分は AC まで 51 分かけて、そのうち 40 分かそこらは下手なデバッグに費やしていた。■E 問題「Permute K times」。一読ダブリング。■F 問題「Rearrange Query」。Range Set Query とかそのへんの問題に見える。一致判定はソートして一致するかどうかでいいが、クエリごとにソートすることはできない。残り時間が 25 分しかなかったので(D 問題の半分!)、半ばあきらめて仰向けになって目をつぶって考えてみると(今日は朝がいつもより 30 分早かったのだ)、ローリングハッシュでずるいことができそうだと思った。数列の各値を素数で置き換えて、範囲の一致を範囲の積の一致で判定するならソートの必要もない。実装が軽かったので最初の提出を出したのが終了7分前。これは要素を素数に置き換えるためのコードを呼び出し忘れていたので WA になった。2分で修正して出した2つ目の提出は、素数1と素数2をあちらこちらで取り違えていたのが原因で WA だった。さらに2分で修正して出した3つ目の提出が AC だった。終了3分前。これが WA だったときのために3つ目の素数を利用するバージョンを WJ のあいだに用意していたが、結果的に必要なかった。■自分のすべての提出。前回が3完で、今日も D 問題がさっぱり合わなくて泣きたくなるやら腹立たしいやらだったけど、最終的に A-F の6完で大満足。D 問題がもっと早く解けたはずだとか、F 問題の2ペナの原因がしょうもなすぎるとか、欲をかけばきりがないけども、冴えないなりに健闘した。■F 問題。他の提出を見てると、自分はずるのしかたが下手だった疑いがある。素数はたくさんはいらないのかな。要素を素数にするのでなく、要素を素数の指数にして、範囲の和の一致で判定をするのが、まっとうなずるのしかた、っぽい? チェックサム? ローリングハッシュ自体がベースと mod の2つしか素数を使わないしね(※2つの素数でも十分だけど、書いてあったのは互いに素な2数だった)。自分みたいに要素をそれぞれ異なる素数に置き換えて、それらの範囲の積で判定をするのは、無駄だし要素数に応じてスケールしない下手なやり方。そもそも、ロリハ言いながらなぜ変なやり方をしているのか。たぶんローリングハッシュは位置と値に意味があるもの(位取りされた数字の列や文字列)に限られた範囲のアイデンティティを割り当てる方法であって、F 問題で必要なのは多重集合のアイデンティティだから、ローリングハッシュとして知っている方法にならなかった。各要素に散らばったユニークな値(x 番目の素数であったり、素数の x 乗であったり、Ruby であれば x.hash でも OK らしい)を割り当てたら、集合のアイデンティティとしてはその和でも積でも求めれば順序を問わない値が合成される。発想はロリハでもそれはロリハとして知っている方法ではなかった。ところで、「x 番目の素数」と「和」の組み合わせでは衝突しやすいかもしれないので(2+5=7 みたいに)、素数の積にしたのはファインプレーだったのかテストケースの穴なのか。あ、素因数分解から連想して ID を定めるか、N 進数から連想して ID を定めるかという感じでまとめられるのかも。素因数分解ならあいだに入る演算は掛け算に決まってるし、N 進数なら当然各桁重み付きの和を求める。多重集合の要素に割り当てる値の定め方に応じて、合成された全体の ID として積が選ばれるか和が選ばれるかは決まっていたのかも。■D 問題。不明なまま放置していた問題名。ペドメーターって響きがいかがわしいけど(それはお前が……)、pedestrian (歩行者) から連想すると歩数計なのかな。読み直すと、問題を解くのには全く影響しない単位が歩数だったから、たぶんそう。あたりをつけただけで確定はさせずにやっぱり放置するのはいつも通り。pedometer が何かに興味がないし気にもならない。広告があふれすぎている現代への適応。■■■ D 問題。「累積和を計算して、Mの剰余が同じ位置を集めます。そしてその位置の集まりで差がN以下の個数をカウントします。そのとき、その集まりが大きくなる可能性がありますが、尺取り法的に計算すれば速くなります。」を参考にして。提出 #56958498 (AC / 318 Byte / 371 ms)。最初の提出 #56820856 (AC / 232 Byte / 202 ms) より長くて遅くてメモリ消費量も多いけど、ややこしいデバッグは必要なかった。コーディング時間は 20 分くらいかな。30 分の節約。


2024年08月15日 (木) THERMOS の真空断熱マグを新しくした。新しいのは JON-481 STG で、古いのは JMK-500 BK。調べたら古いのは 2008 年の 10 月に購入していた。16 年前だ。理由は最近になって頻繁に漏れるようになったから。一度パッキンを新しくしているし、栓とパッキンのセットも一度新しくしているけど、もう消耗品が手に入らない。仕様の違いによりいろいろと得失がありますね。プラスチックの飲み口と、金属の飲み口。栓の大きさによる栓を介した冷めやすさと飲み口の広さ。2ピース構造の栓はパッキンが2つあって、潜在的な漏れ要因と洗浄パーツが増えるけど、傾けたときに(しっかり保温されていて熱いかもしれない)中身が飛び出してこないような仕切りを設置することができていた。新しいものは栓1パッキン1と簡略化されているが、一長一短というところだと思う。ところで、栓とパッキンが一体であることをうたうものもサーモス含む複数メーカーから販売されていた。それはやりすぎだと思う。あるメーカーのものは、どうやって洗うのかがわからなかった。今まで使っていたもので苦労していたから知っているけど、細い隙間に茶渋を含んだ液体がたまる。メンテナンスのしやすさを考慮していない道具は信用できない。サーモスの栓パッキン一体タイプは、一体といいながら一部を取り外して丸洗いできるメリットが強調されていて、洗うことを考えている点でその点が不明だった他メーカーより信用できるが、とあるレビューで自転車に取り付けるとカチャカチャうるさいと書かれており、まさしく一長一短だなと。そもそも栓パッキン一体が失敗だったのだ。パッキンだけなら 200 円程度だが、栓パッキンだと 800 円する。パッキンの抗菌防カビは実際に意味があるが、それにも時効がある。一度生えると増えるのは早い。ライフサイクルが異なるものを一体不可分にするのは設計判断としてどうか。ネジ式とワンタッチ式にもそれぞれの得失がある。形状の複雑さからくる洗いにくさと壊れやすさ、漏れへの不安から、便利さを全く評価しない自分はネジ式一択になる。必要ではないからこそ便利だという評価になっている。タダで手に入る便利さなら結構だけど、一長一短の便利さは不要。ところで、新しい方はてっぺんほどすぼまったテーパー形状で、筒も細身だ。新旧で容量が同じで長さもほとんど違わないのだから、細いのは製造技術の進歩なのかもしれないが、径の小ささとテーパー形状とフタの薄さが合わさってとても開け閉めがしにくい。力がいるし、滑りやすい。古い方は径が大きいのもあるし、頭が張り出した逆テーパー形状なのもあって、開けるのに握りやすいし、提げるのにすっぽ抜けたりしなかった。このフタの形状こそタダで手に入る便利さの例だと思うんだけど、どこにコストを見出して以前は具えていた使いやすさを捨てたというのか。ものを作る人間がおしゃれ感のために人間工学を捨てるようなことがあれば軽蔑するよ。何も捨てずにかっこいいものを作るんだ。


2024年08月12日 (月) [AtCoder] X で見かけた。「AtCoderでずっと不満な点として言及されてるの見たこと無いけど 「998244353で割った余りを…」 は、 「素数998244353で割った余りを…」 って書いて欲しい。 書いてないということは、これが素数であることを覚えゲーとする、あるいは調べろってことであり、その意図が分からない。マジでなぜなの?」 わからない主張ではない。最近は 9..... だけ見て「はいはいいつものね」と油断した対応をしているけど、初心を忘れていなかった頃は、irb を開始して require'prime' して 998244353.prime? #=> true を確認していた。この数字をまともに読んだことも入力したことも一度もない。ずっとコピペしてる。覚えゲーは成立しないのです。だから素数って書いてあると嬉しい。