/ 最近 .rdf 追記 設定 本棚

脳log[2023-05-31~]



2023年05月31日 (水) 畳み込みの視点から見たforall(every)とexists(some): 空集合に対するforallは常にtrueになる - Lambdaカクテル」■Ruby もうまく定義されている言語のひとつ。自分の日記から「ところで空配列に関して、[].all? は true を返し、[].any? は false を返す。この違いによってメソッドの選択が制限されることがあるかなと一応警戒するんだけど、特にそういう違いは生まれないみたい。むしろそうならないようにデフォルト値が選ばれている。」■読んでたらモノイドと単位元の話になった。単位元だから true になったり false になったりするのだ(知らんかった)。それはこの前やらかしたやつ。「ST クラスの内部配列のサイズを2べきに揃えるときに埋める値がよろしくなかった。ACL などまともなライブラリのセグメント木を使ったことがあれば単位元がパラメータ(の1つ)だということがわかったはずだ。」■最後に chokudai さん出てきた。「・論理的にはtrue一択。false派は論理を勉強してほしい ・論理で判断できる項目でドキュメントを参照する手間を増やすのは良くないので、状況に拠らないで欲しい ・多くの環境では「全員が論理的に考えられる」と思わない方が良いので、ドキュメントやコメントは気を使うべき https://t.co/fovw2w1bIC」「「要件による」って言ってるたくさん人いるけど、要件は、「配列のすべての要素が条件を満たすならtrueを返す」であり、ここに「空配列はfalseにする」を入れるなら「配列の全ての要素が条件を満たし、空でないならtrueを返す」という要件にするべき。空配列がtrueはこの文章なら要件に入っている。」■これが一連の発端らしい。「「配列のすべての要素が条件を満たすならtrueを返す」関数を定義するとき、空の配列を渡したらfalseを返すかtrueを返すかが、良いプログラマかどうかの一つの境目だ」 このお題で「要件による」と言ってしまう、要件を定義する立場であってほしくない良くないプログラマがいっぱい炙り出されているのだ。とはいえ、もっともやべーのは「false に決まってる」と考えてしまう人間だし、実は「true に決まってる」という態度も現実では危うい。PHP みたいにときどき常識が通用しない言語があるわけなので。Ruby だってドキュメントを読むまでは理解できない罠があったりする>「Ruby クイズ (複合代入編)」。■chokudai さん「「全ての要素が条件を満たすならtrue」って要件の関数は場合はtrue一択だけど、実務上の要件はそれに合致しているとは限らないので、違うのであれば、 ・関数名を変えて要件が違うことを明確にする ・配列の外で判定する とかの処理は当然やるのよ。」っていう、元になったツイートのスコープ外までフォロー入れてるのにクソリプついてるぽくてかわいそう。有名税か。読めてないからこそクソなのであってどうしようもないね。あるいは読んだ上で語調から馬鹿にしてるとお感じになったのかしら。馬鹿だからどうしようもないね。読めない人に言葉を費やしても、煙に巻こうとしてるとかなんかめっちゃ焦ってるとかって「印象」を与えることしかできなさそうで、不毛だと思う。無視すれば無視したで「効いてる効いてる」なんて勘違いをされそうなので、「ここに書いてある。これを読め。わかるまで読め」が正解か。


2023年05月29日 (月)

最終更新: 2023-06-10T00:19+0900

[WR250R] 事故の顛末

 先月 28 日

横断歩道わきに人を見つけて止まったら後ろを走っていた車に追突されたよ。

 けが

車は軽自動車で、双方ゆっくりペースで走っていたみたいなので、わけがわからんまま地面を転がったけど骨折などはなし。さすがに無傷ではなく肩と腰にぶつけたような筋肉痛のような痛みがあったのと、右のすねに4点の血の穴があった。位置と配列からステップのギザギザ(※オフ車のステップにはラバーがない)にガツンとぶつけたのかなという感じ。普通に歩けはする。

肩は最も簡素なものではあってもプロテクターが初めて役に立った結果といえる。ニーシンガードは……足首の方からすきまにもぐり込まれたのかなあ。

 バイク

押し倒されて後輪に乗り上げられて冷却液をドボドボとかけ流しにされていた。

ナンバープレートやナンバーステーがぐんにょりひしゃげてるのが一番のダメージ。スイングアームの表面やアクスルナットも削られてギザギザしてた。

 場所

目の前が消防署であって、隊員の人が一番にかけつけてくれて怪我の確認やら事故車の退避やら道路上の液体に砂を撒いて掃き清めるやら大いにお世話になってしまった。ありがとうございます。

 レッカー

乗って帰るのは怖かったので購入した店まで運んでもらった。到着は営業時間をちょっとオーバーしてしまったけど、その時間ならまだ作業をしているということで対応していただきました。

使えるロードサービスが2種類あった。新車購入時に付随していてまだ更新しているものと、任意保険付帯のもの。事故で忙しいときにまどろっこしい自動音声を聞かされるのは苦痛だし、屋外で「~は何番、~は何番」みたいなのを聞き漏らさないのも難しいことなので、最初から人が応答してくれた方はポイントが高い。営業時間外やら定休日やらで販売店に運び込めなくて一時的に預かってもらう場合に、別日のレッカーが自己負担になるかどうかも対応が分かれた。つまり、任意保険付帯のレッカーはおまけなりのものだった。今月に任意保険の更新をしたときに二次レッカー費用が無料になります、という変更点が書いてあった気がするので、改善はしているらしい。

 保険

相手方の保険会社から最初の電話で 100:0 でと伝えられた。こういう(こちらに過失がない)場合に自分の保険会社は代理人になれないというのを風の噂で知っている。そういうときのために弁護士費用特約を付けている。使わなかったけど。

2回目の電話でバイクが全損扱いだということと、時価を上限にして補償するということを伝えられた。全損というのが意外なワードだったけど、要するに修理費用の見積総額(70 万円くらい)が中古車の購入費用より高くなったということなんだろう。スイングアームとリヤフレームがそれぞれ 10 万とちょっと、マフラーが 15 万円くらいするらしい。

 時価

向こうはグーバイクで走行 30000 km 以上の WR250R を検索して4件の車両価格の平均から 58 万といくらという金額を出した。自分のバイクの走行距離が 32000 km 台だから。

でも4件の平均というのはどうなのか。誰かサクラで 200 万円のバイクを出品してくれたりしないだろうか。簡単につり上げられるでしょう。また、30000 km 以上という条件もどうなのか。じゃあこちらは 40000 km 以下で平均を出しますよ。0 km の新車も 100 km の新古車も 1000 km も含めちゃいますよ。

Excel に直線を引いてもらって時価は3万円だけ上がった。

 バイク以外

肩の部分がすり減ったプロテクター入りジャケットは購入費用2万円のおよそ1割、すねに穴の空いた靴下は購入費用2千5百円のおよそ5割が補償された。購入年月日で減価償却した結果らしいけど減価償却という概念を持っていないので何も言えることがない。

スマホはベルトに通して腰のポケットに入れていたのが完全に無傷だった。やったね。

ドライブレコーダーだとか後付けのリアキャリアだとか、車体にネジで固定しているようなものはバイクの時価の中に含めてしまって個別に補償はしないらしい。あっそ。納得はしていない。

 収支

ゴールデンウィークを含むひと月くらいバイクに乗れなくて、スイングアームにはギザギザが残って(気にしない)、リアフェンダーは純正の黒く垂れ下がったものに戻ってしまった(プラスチックだからアルミパーツに比べて軽くはある)。修理費用がパーツ代と工賃がそれぞれ 15 万円ずつくらいの計 29 万円で、およそ 30 万円が残った。


2023年05月28日 (日) [AtCoder] 精進。昨日あった ABC303-F「Damage over Time」(黄 diff)。昨日は DP とか二分探索とかを考えるも、問題の輪郭、要素同士の関係が十分に掴めなくて解けなかった。一晩(よく寝て)考えた方針はこう。最後のターンから考える。呪文が効果を発揮するターンは1ターン限りなので d が最大の呪文を唱えるのが最善。1ターンで倒せないなら最後から2ターン目を考える。以降3ターン4ターン……。効果ターンが決まっているのでそのターン数で最も効果を発揮する呪文は d でソートして順番に選んでいける。■提出 #41817554 (AC / 539 Byte / 616 ms)。端折った説明は、呪文の効果はターン数に比例して増加した後で一定になるということ。一定になった後の呪文はひとまとめにして最大のものだけを記憶しておけばいい。もうひとつ。ターン数を1ずつ数えることが許されない制約なので、呪文の効果が一定になるタイミングと、比例状態にある呪文の効果とすでに一定になった呪文の効果が逆転するタイミングを捕まえて、飛び飛びに判定をした。ターン数による呪文ダメージの累積と、ターン数の範囲による呪文ダメージの累積の累積をごっちゃにしそうでややこしい。


2023年05月27日 (土) [AtCoder] 今日は日鉄ソリューションズプログラミングコンテスト2023(AtCoder Beginner Contest 303)があった。コンテスト成績証自分のすべての提出。遅めの A-E 5完で微減。以下ふりかえり。■A 問題「Similar String」。あいまい一致判定。目で見ても同一視する2つの文字がよくわからないのでコピペでスクリプトに埋め込んだ。たぶんイチと小文字のエル、ゼロと小文字のオーを同一視してるんだと思う。■B 問題「Discord」。制約が小さいので具体的に x yy x を検索すればいいと思う。横着して単一の文字列を対象にして検索するようにしたら 10 や 20 を 1 や 2 と見間違えるバグを仕込んで頭を悩ませていた。あほ。■C 問題「Dash」。書いてある通りに実装するだけなんだけど最初の提出は WA×1 だった。問題文の最後がこうなんだけど、「高橋君が一度も倒れることなく N 回の移動を行えるか判定してください」、N 回目(最後)の移動の1ステップ目を終えた時点で体力が尽きた場合の判定がそれほど明らかではない。「最後の移動で体力が-1になった場合答えはYesとなりますか?」という質問と答えが全体公開されているくらいなので。自分はコーナーケースをうまく回避したつもりで N 回目の処理を特別扱いして WA×1 になっていた。ところで、WA×4 になる提出をいくつか見かけたけど、これは「移動した点に置かれたアイテムを消費し」というのを読み落としていたものと思う。この点はちゃんと疑問を持って確かめていたので間違えなかった。■D 問題「Shift vs. CapsLock」。D は DP の D! CapsLock が ON/OFF の状態それぞれの最小タイムを記録していく。たぶんないとは思ったけど制約上は許されていたので、Shift+A と CapsLock+A+CapsLock みたいな、結果が決まってそうなケースも一応比較した。■E 問題「A Gift From the Stars」。難しくはないと思う。迷って手が止まってえらく時間がかかったけど。まず次数1の葉っぱを見つける。その相手は星の中心に決まっている。星の中心の相手は葉っぱに決まっている。すでに見た葉っぱは無視して新しい葉っぱの相手を見る。それが自分(星の中心)なら無視して、そうでないものがあるならそれは別の星の葉っぱに決まっている。という感じで次々に判定していくだけのことに 40 分ちょっとかけてしまった。最終形は、星の中心をキューに入れるようにして星のレベルを記録していくものになった。■こちらの提出 #41744985 を見ると次数だけで答えが出せるみたい。次数1は葉っぱに決まってる。次数3以上は星の中心に決まってる。次数2は星の中心でも葉っぱでもありうるけど、全体を見ると星の中心と次数2の葉っぱの数の比率は n 対 2*(n-1) に決まってるので、って感じだろうか。ヒントなしでは気がつけないよ。■面白いことを書いている人がいる。「ABC303-D この問題の正解者は実は間違っていた」。形式だけ見て気が付いたことを。「別のとらえ方」として書かれている4ステップの処理について。1ステップ目は dp[0][j] と dp[1][j] に基づいて dp[0][j+1] に一時的な値を保存している。2ステップ目は同じようにして dp[1][j+1] に一時的な値を保存している。3ステップ目は dp[0][j+1] と dp[1][j+1] に保存した一時的な値に基づいて dp[0][j+1] に本式の値を記録している。4ステップ目は dp[0][j+1] に記録した本式の値と dp[1][j+1] に保存した一時的な値に基づいて dp[1][j+1] に、おそらく誤った値を記録している。これは自分が提出 #41747349 で5行目と7行目がどれだけ長くても1行の多重代入によって値の更新をしている理由だし、ときどきは見た目を整理したい邪悪な欲求に負けて代入を複数行に分けてバグらせてしまうのと同じことである。たぶんね。


2023年05月26日 (金) キッチンシンクを皿用スポンジで洗うのが汚いという感情の成立と国鉄型特急の不便な手洗い場の関係について」■全然知らんかった! でもたしかに洗面台にはゴム栓があるし、風呂桶は洗面器って呼ぶ。熱すぎるお湯も手を離すとすぐ止まる水も、直面すると困ってしまう様子がありありと想像できる。水をためる発想はまったくなかったけど、言われてみればそうとしか思えない。中性洗剤の用途に野菜って書いてあるのを知ったときと同じくらいの驚き。一昔前のことでも全然知らないね。


2023年05月25日 (木) 検索結果のRPMは高いのだと、Twitterのキーワードターゲティング(の発表)が証明している | LIFT合同会社」■全然知らない分野で興味深く読んだんだけど、じゃあ Twitter はなんで最近になって検索結果の表示をログインユーザーだけに限っているのか、広告主への売り物をログインユーザーだけに限ろうとしているのかと疑問に思う。ユーザーが生み出すコンテンツを自家消費するだけではもったいないでしょうに、どうして露出を減らすのか。検索がしんどいの? クローズドサークルなのは Facebook が以前からそうで、Twitter も普通の SNS を目指してるんだなーというのがイーロン・マスク以来の感想なので、全然不思議はないのかもしれないけど。


2023年05月24日 (水) 2023030920230414 で読んでいた『ひとはどこまで合理的か?』(スティーブン ピンカー)に続けて『ファスト&スロー』(ダニエル カーネマン)を読んでいる。現在は下巻のプロスペクト理論の章で、ベルヌーイの富の効用理論の限界を明らかにするための問いかけへの自分の答えが見事に想定から外れていたので、そういうのが大好きなので、紹介したい。■下巻 94 ページから。「問題3 あなたは現在の富に上乗せして一〇〇〇ドルもらったうえで、次のどちらかを選ぶように言われました。五〇%の確率で一〇〇〇ドルもらう、または確実に五〇〇ドルもらう。問題4 あなたは現在の富に上乗せして二〇〇〇ドルもらったうえで、次のどちらかを選ぶように言われました。五〇%の確率で一〇〇〇ドル失う。または確実に五〇〇ドル失う。」■2つの質問への答えを決めてから読み進めると書いてあったのは、「たぶんあなたはたいていの人と同じように、次のような反応を示すだろう。問題3では大方の人が確実な方を選ぶ。問題4では大方の人がギャンブルを選ぶ。」「あなたは選択を決める前に、問題3では一〇〇〇ドル、問題4では二〇〇〇ドルを「もらった」はずだが、そのことに十分注意を払っただろうか。たいていの人と同じなら、そんなことは気にも留めなかったはずだ。この「プレゼント」は参照点に含まれてしまい、参照点は無視されるのがふつうだからである。」「またあなたは、損得に対する自分の態度が、富の状態の評価に必ずしも左右されないことも知っているだろう。一〇〇ドル得をするのが好きで一〇〇ドル損をするのが嫌いなのは、富の増減の問題ではなく、単に勝つのが好きで負けるのが嫌いだからである。そしてまずまちがいなくあなたは、勝つことを好む以上に負けることを嫌う。」■自分の答え。問題3ではダブルアップチャンス(ギャンブル)を選んだ。問題4では確実な損失を選んだ。どちらも想定の反対だ。どういう心理かというと、問題3ではすでに一〇〇〇ドルというあぶく銭を手に入れていて、ギャンブルを選んでもそれを取り上げられはしないので、追加でもらえなくてもその嬉しさは減らない。一方で確実に五〇〇ドルもらうよりも倍額の一〇〇〇ドルを確率でもらうギャンブルに勝つ方が喜びは大きい。問題4では、すでに二〇〇〇ドルという十分に大きなあぶく銭を手に入れているので、それが確実に五〇〇ドル減ることに痛みは感じない。感じない痛みを取り除くために失う額を倍にするかもしれないギャンブルに参加することは、痛みや悔しさを生み出すマイナスばかりが目立つ。■どうだろう。たぶん国民性みたいな傾向もあるんじゃないかな。自分の答えは日本人の標準だと信じている。だって完全に自分の利益と感情に従っていてこれ以外の答えは考えられないんだから。■とはいえ、得するチャンスを逃したことをあとから知って、本気で損をしたように感じたり、(そこに他者が関わっていたことで)損をさせられたと感じれば腹を立てたりする、自分と異なる考え方をする人が存在することも知っている。自分の感覚ではあると知ってすらいなかったプラスのチャンスを逃したことはただのゼロであり、そこに悔しさはない。事前に知って皮算用をしていたとしても、参加費がゼロならリターンがゼロでも惜しむ対象がない。でもそうは考えないやっかいな(説明ができない)人もいる。■いやまあ、説明だけならできる。本の同じ部分(97 ページ)に書いてある。「金銭的結果の場合には、通常の参照点は現状すなわち手持ちの財産だが、期待する結果でもありうるし、自分に権利があると感じる結果でもありうる。たとえば、同僚が受け取ったボーナスの額が参照点になることは、大いにありうるだろう。」 参照点が異なっているだけなのだ。どうして参照点をそこに置いたの? って疑問がやっぱり理解できずに残るわけだけど。


2023年05月21日 (日) [AtCoder] 精進。昨日の ABC302-F「Merge Set」(水 diff)。ネタバレを読みました。「アライグマ「F問題は超頂点を使う最短経路問題なのだ! ABC184Eが類題なのだ」 https://t.co/vn6YsG0fOO」。集合と集合の要素の両方を頂点にして二部グラフを構成するといいらしい。昨日書いたように自分の頭ではそれがわからない。「BFS も考えたけど隣接頂点リストが膨大になりそうで諦めた」。■提出 #41606573 (AC / 455 Byte / 508 ms)。実装はなんの問題もなくできる。操作回数を数える位置だけちょっと悩んだ。


2023年05月20日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302) があった。コンテスト成績証自分のすべての提出。所要時間が A=1分、B=31分(+5分)、C=3分、D=8分、E=12分(+5分)、G=33分。B 問題で沼ったのとケアレスミス2つが反省点。以下ふりかえり。■A 問題「Attack」。繰り上げ整数除算。A が1以上の制約であることを確認してから (A-1)/B+1 と書いたけど、だったら (A+B-1)/B と素直に書けばいいと思う。負数の整数除算は 0 に近づく言語と負の無限大に近づく言語があって、Ruby の場合はたとえば (-1)/2 が -1 になる。わざわざ括弧を付けたのは、たとえば 0-1/2 が 0 になるからで、負号がリテラルの一部(もしくは単項マイナス)であることを明確にするため。めんどくさ。■B 問題「Find snuke」。いまもって分からないこの条件文「A1​,A2​,A3​,A4​,A5​ の中心はこの順に一直線上に等間隔で並んでいる」。中心ってどこ? さておき、単にグリッドを全探索する問題なのだけどどこではまったのか。次の文字を探索するときに方向を固定するのを忘れていてジグザグに探索してしまっていた。それで答えがいくつも出てきて困っていた。さらには WA も出してしまって、そこから6分で別バージョンの解答を書き上げて AC を得た。つまり6分で解けたはずだよねってこと。コンテスト終了直後に WA 提出を眺めていてバグを見つけたので出し直して AC にしておいた。8方向の遷移先のうち1つがずれていたのが原因。'snuke' の各文字に対応したクロージャをチェインして出力に繋げる実装ってちょっとおもしろくないですか? Array#inject メソッドがはまりすぎ(なので WA のままにしておけなかった)。■C 問題「Almost Equal」。制約がごく小さいので愚直に並べ替えて愚直に比較して答えを出した。■D 問題「Impartial Gift」。D は DP の D……ではない! 差が一定以下で和が最大になるものだから、条件を満たす A の要素のうち最大のものと条件を満たす B の要素のうち最大のものを見つけて、いい方を答えにすれば良い。条件とは、現在見ている要素を a として、a-D から a の範囲の値が他方の数列に見つかること。■E 問題「Isolation」。UnionFind だと辺の削除はできないんだよね。注目するところは、辺の数はクエリの数を超えないということ。集合(Hash)で個々の辺を管理して許される。あとは辺の数が0と1のあいだで変化するのを掴まえて孤立頂点の数を管理する(変数名の o は orphan の o だよ。次数0の o でもあるかな)。サンプルの2が優しくて(「2 番目の種類のクエリを行う直前の時点で、すでにその頂点と他の頂点を結ぶ辺が 1 本も存在しないこともあります」)、ペナルティを食う前にすぐ修正して提出したよね。いや、それでもペナルティは食らったんだった>WA。一度は書いた E[a].clear がいつの間にか消えていたのが原因。■G 問題「Sort from 1 to 4」。もっと難しい類題を解いたことがある>ARC124-D「Yet Another Sorting Problem」(20211125)。あるいは UTPC2021-A「Make UTPC」(20220511)。今日の問題では、1から4の場所に納まるべき1から4の値の列が与えられる。ソートすればどの範囲が1の場所でどの範囲が2の場所か……ということがわかる。位置と値が一致しているなら交換は不要。1回のスワップでお互いの位置が正しくなるペアがあるならスワップして損はない。次は位置を交換している3つ組を見つけて2回のスワップで位置を正す。ここまで実装してあとはどうしようかと作業配列をインスペクトしながらサンプルを実行していたら、サンプルの2が神だった。残りは4つ組だけしかありえないので不一致の数を合計して÷4×3で OK。■F 問題「Merge Set」。名前からするとマージテクとかマージソートでうまくする問題かなと思うけど、うまい道筋をまだ見つけられていない。(ツイートを読んで書くんだけど) BFS も考えたけど隣接頂点リストが膨大になりそうで諦めた。ひょっとしてあなた(私です) M 個の値を頂点にしようとしていませんでしたか?■B 問題。今理解した。「5 つのマスの組 (A1​,A2​,A3​,A4​,A5​)」という自己紹介がちゃんとあった。A よ、お前マスだったのか。■G 問題。「@kyopro_friends なるほど。書き方的に一般に成り立つように見えたので、例えば数が 6 種類あると上手く行きませんというのを伝えたかったです。」 うーん、わかりませんねえ。位置を正す方法(経路)に複数の選択肢があって、貪欲法では良くない経路を残してしまうのかなと思ったけど、そういうケースが作れないのと、そういうときにどういう方法がとれるのか。


2023年05月16日 (火) [AtCoder] 精進。AGC047-A「Integer Product」(水 diff)。以前に解こうとして解けなかった問題。小数部分を9桁に固定した固定小数点数として扱って、2の因数と5の因数を数えて 10 が 18 個以上作れる組み合わせを数えるというところまでは以前も考えた。いったい何がわからなかったのか。たぶん A 数列の組み合わせを考えようとして O(N^2) をどうにかする方法がわからなかったのだろう。でも考えてほしい。2 の因数も 5 の因数も 18 個までしか数える必要がない。A 数列の各要素は 18×18 の平面にプロットできる。そうすると組み合わせは 19^4 ≒ 13 万通りしかない。■提出 #41467175 (AC / 511 ms)。同じ要素を組み合わせないようにだけ注意。そこはひっかからなかったけど入力を固定小数点数化するところでバグらせて、0の数がときどき1多かったりした。こういう添字と数の変換って指を使ってよくよく数えるんだけど間違えるんだなあ。


2023年05月15日 (月) 長らくのご利用ありがとうございました。 : モトアサイン」■なんの関係もないけど読んでたブログ。最近更新が滞り気味だと思っていたら……。過去の記事全部消しちゃったの? それは何かを否定するような行為に見えて賛同はできないかな。当人の意思とすればよく理解はできるけども。所詮は赤の他人の言うことだけど。読者だったから惜しいと思う。


2023年05月14日 (日) [AtCoder] 今日は ARC160。配点 400-500-500-(あとは知らん) はゼロ完あるで。参加賞は茶パフォかな。■A 問題「Reverse and Count」。数列を前から見ていく。その値が a であるとする。a より小さい要素が右側に sub 個あるとして、K<sub であるなら、右側にある小さい方から K 番目の要素と a を範囲とする操作が答え。さもなければ、a を含む a より左側の数列の並びをそのまま温存するような操作がいくつあるかを考える。a の左に l 個、右に r 個の要素があるとすると(l+1+r=N)、evn = l+1+r*(r+1)/2 回の操作が a までの数列を固定する。これが K-sub を超えるなら次の要素に処理をまわす。今は a の位置に a より大きい要素を持ってくる操作を考える。a より右にあって a より大きい要素のうち K-sub-evn 番目の要素と a を範囲とする操作が答え。説明しててもわからん。難しいね。提出 #41421021 (AC)。1時間半ちかくかけて 2WA のち AC。■C 問題「Power Up」。これは精進。最初は素朴に A の要素を小さい方から処理するのだと思った。個数を数えて何回の操作が可能か数える。そして次の要素の個数を操作回数分だけ加算する。それではだめなのだな。たとえば現在の要素が a であるとして、最初 n 個あったとする。最大限の操作を駆使して n+c 個まで増やすことができるとする。n+c 個を操作対象にするとき a 以下の要素から成る集合の多様性が最低になる一方、もともとあった n 個の範囲内で操作をしたりしなかったりする場合は、a 未満の要素を対象にした操作にはなんの制限もかからず集合の多様性が最大になる。というのをどうやって管理して数えるのか。提出 #41424512 (AC)。A 問題の AC から1時間後でコンテスト終了からは 30 分後の AC。かかった時間を考えると A 問題の配点は低かったと思う。■B 問題は苦手な苦手な ABC-D の臭いがしたし、ARC の問題ならさらに難しいに決まってるので一瞥だけして飛ばした。正しい判断だったと思う。■■■@2023-05-17 精進。B 問題「Triple Pair」(ぎりぎり水 diff)。動画を見た後でいまさらだけど、x≦y≦z を仮定して並べ替え(6通り3通り3通り1通り)を考えるところまではすぐに考えた。2数の積が N 以下なんだから入力の平方根の範囲で全探索できることもわかる。でもコンテスト終了後にちょっと考えたときは z に関してループを回していた。それは難しくない?■提出 #41484353 (AC / 180 byte / 350 ms)。動画で見た通りに y についてループを回した。普通に ABC-D だったと思う。ただし苦手な苦手な ABC-D ではある。


2023年05月13日 (土) [AtCoder] 精進。今日あったパナソニックグループプログラミングコンテスト2023(AtCoder Beginner Contest 301)-E「Pac-Takahashi」(青 diff)。最初はメモ化再帰だと思った。「順列総当たりが許されない制約(N≦16)だけど、A<B、A>B を区別せずに2回目以降の数え上げがサボれるなら許される」制約だったから。でも実装を始めるとパラメータが多くてうまくメモできなかった。そのうちに TSP とかワーシャルフロイド法が見えてきた。■最初の提出 #41382752 (WA×19)。無効値が -1 と T+1 の2種類あって、-1 がうまく扱えていなかった。■2番目の提出 #41386679 (WA×5)。パックマンの餌が1個もない場合に答えが nil になってしまっていた。■3番目の提出 #41392115 (AC / 3117 ms)。無効値を T+1 に統一したり多重ループの一番深い部分を効率化するなど清書しているうちに WA×5 の原因がひらめいて、制約を確かめたら間違いなさそうだった。終了から5分3秒後の AC。一番悔しいやつ。■コンテスト成績証。上がるんだ……。喜べないかな。■■■ABCD のふりかえり。A 問題「Overall Winner」。Array#tally で集計して出現数を比較する。同数なら最後の文字を見れば答えられる。Array#tally を使うとき出現数が 0 のときに nil が返るのが予想外で実行時エラーを起こしがち。■B 問題「Fill the Gaps」。隣接2項を見てあいだを補完する。Gateway Timeout のせいで最初の提出は虚空に消えた。その後も E 問題で提出が消えたり、消えたと思わせてちゃんと WA になっていたりした。だから再提出前には提出一覧を確認したんだよ、ペナルティを重ねないために。■C 問題「AtCoder Cards」。これも Array#tally で集計した。'atcoder' の各文字に対してはオールマイティ(@)が使えるが、それ以外の文字は出現数が正確に一致していなければいけない。数の一致とオールマイティの数が足りているかを確かめた。■D 問題「Bitmask」。すべての ? が 0 だったとして可能な最小値を求めて N と比較する。あとは最上位の ? から順番に 1 に変えてみて、N を超えない限りはさっきの最小値に加えていく。こういう数の扱いは BIT#lb メソッドの実装でなじみがある>#38427641。典型力について書かれた「chokudaiのブログ」にも言及があるよ(「この一連の操作のコストは(書き換えた要素の数によらず)2^k である。」「kを使った場合のコストは、k-1以下のすべてを使ったコストより高い」)。自分は「わかる」のではなく「知っている」だけなのだ。最小値を求めるときに String#to_i を無引数で呼び出してしまって1ペナ。