(N+2)/5*5 一発で二捨三入できた。切り捨て切り上げを定型で覚えているだけで考えることをしないから無駄なことをする。……というのもちょっと違う。(A+B-1)/B と (A-1)/B+1 がどうして切り上げになるのか過去に考えたことがあるから (A+2)/5 もわかる。ボーダーは動かせる。■B 問題「ABCDEFG」。もっともあほな書き方をしても 42 通りなので好きに書く。累積和を用意するときに要素数が少ないからうっかり暗算しそうになったけど、間違えるから機械にやらせた方がいい。■C 問題「Snuke the Cookie Picker」。人間はなんとなく答えが出せるけどコンピュータに出す具体的な指示は案外難しい。すべての行と列で上端下端左端右端を検出して数が多いものを採用する解答を提出してランタイムエラーを出した。最小ケースを作ってみて気が付いたんだけど、１対１で同数になるので答えが出せない。たとえば上端には最小値、下端には最大値を採用するのが正解。■D 問題「Sleep Log」。方法はいくつかあるのかな。睡眠時間の累積和に適切な座標を割り当てて二分探索ができればいいように思った。でも実装方法(座標圧縮？)が見えなかったのでもうひとつの案。累積睡眠時間を数えながら各クエリの入りと出のときに値を記録した。同時に扱う時刻が睡眠時間とクエリを合わせて３つあって、組み合わせて正しい式を得るのが難しかった。クエリの入りと出の２か所に書いて揃って間違えた。それは提出前に修正できたけどデバッグ出力の消し忘れで All WA をくらった。人間は都合良くデバッグ出力を無視してサンプルの答え合わせができるんよね……。■E 問題「Art Gallery on Graph」。これは簡単。BFS で頂点を訪問するだけ。罠があるとすれば、グラフを勝手に木だと仮定してはいけないということと、何も考えずに BFS を繰り返して値の更新が続くと O(KN) で TLE になる可能性があるということ。プライオリティキューで提出して２秒ぎりぎりで AC だったけど、BFS を(１回だけ)やりながら適時キューに警備員が立っている頂点を追加するようにするともっと余裕があった。ここでは出力形式を間違えてまた All WA をくらった。■F 問題「Dungeon Explore」。制約からもこちらに許された操作からもグラフをしらみつぶしに訪問するような探索が書ければいいとわかる。隣の頂点にしか移動できないから探索は BFS ではなく DFS。あとは E 問題と似た文面が見えることからわかるように、勝手にグラフが木だと想定しないようにだけ注意。なんでこういう注意が必要かというと、「木ではない木ではない」と唱えていないと勝手に木を想定したコードを手が書いてしまうからだ。E と F が似たようなグラフの問題でどちらも軽い問題だったから、F 問題を提出した後で F 問題を開いて解こうとして混乱したよね。■最近また落ち目だったからか解けるものを(序盤でそれなりに苦戦しながら)解いただけでレートが上がったのは微妙な気持ち。コンテスト成績証。■■■@2023-06-15 F 問題。自分の提出 #42157034 は 10 行目と 11 行目がやばく見える。10 行目は隣接頂点リスト全体を走査しているし、11 行目は隣接頂点リストがソート済みだということを無視して、頂点 N を目指しているというのに最も小さい頂点番号から順に訪れようとしている。10 行目は「DFSを非再帰に書き換えるとTLEするようになったという心霊現象」について 20221125 に書いたまずい書き換えの例と同種のミスだ。たとえば入力が頂点１を中心とするスターグラフで、頂点 N だけが頂点１から距離２の位置にあるとしよう。長さが N に近い頂点１の隣接頂点リストを N 回近くスキャンするのは O(N^2) でいかにもまずい。だけど実際には問題にならないだろうということも予想できて、当日は解答を作成しながら制約を再確認したりしていた。つまり、提出コードがどういう形で書いてあるにせよ、頂点１の隣接頂点リストを N 回近く標準入力から読み込むことは最悪の場合に避けられないのであり、それでも TLE にならないような制約が書かれていないかを確認していた。なかった。でも実際にはまずい解答でも問題が起こらないような入力だったので AC だった。まずい書き方をしたけど実際にはまずくなかったのだという話。■……でもないのかな？ 日記に「(そんな制約は)なかった」と書くに際してまた問題文を読んだけど、これまで見たことがない「
この問題のジャッジはアダプティブです。つまり、制約および以前の出力に矛盾しない範囲でグラフの形が変わる場合があります。」という注意点に気が付いたよ(今です！)。入力が頂点１を中心とする完全なスターグラフだったときに自分のまずい提出は(アダプティブに)救済されようもなく TLE していただろう(一番最初の入力で頂点 N への辺が示されているから)。あまりにも間抜けすぎるのでそんなうっかり提出を弾くためのケースを用意しようとは考えなかったのかな。あぶなかったね！
あなたにとってスマホで一番重要な機能やアプリはなんですか？ (200 字以内)」。国語のテストを思い出す懐かしい文面だけど、すれた大人としては問いが雑ではないのかなと、だから子供の頃に困ってたんじゃないかなと思う。どういうことか。紙面にはアイドルの模範解答も載っていて、それは字数をほぼ使い切って理由や背景となる自身の状況まで説明している申し分のないものだった。でもね、それを読んでもう一度問いを読み直したんですよ。そしたら「
なんですか？」「
200 字以内」と書いてある。理由の説明いりますか？ どうせ字数を大きく余らせたら減点するんでしょ？ これはすれた大人だからではなく素直な子供だからそうするんだけど、アプリや機能の名前を１つだけ挙げて答えにするんですよ、自分は。国語の授業ってテストのための暗黙のルールを学ぶ時間なのだろうか。そうではないことを知っている。学校の授業ではルールは暗黙のまま伏せられていた。塾に通い出して初めて点を取るためのテクニックのひとつとしてこうしたルールが明示された。ルールが明かされないゲームはクソゲーなんよ。こちとら暗黙のルールなんてものはこれっぽっちも認識できないの。というか、ルールであることを理由にしてルールに従わされることに抵抗があるから、明示されないルールに自ら進んで縛られに行くつもりがないんだ。だから気がつきにくいし、察しても不確定ならしらんぷり。
最終更新: 2023-06-10T00:19+0900
横断歩道わきに人を見つけて止まったら後ろを走っていた車に追突されたよ。
車は軽自動車で、双方ゆっくりペースで走っていたみたいなので、わけがわからんまま地面を転がったけど骨折などはなし。さすがに無傷ではなく肩と腰にぶつけたような筋肉痛のような痛みがあったのと、右のすねに４点の血の穴があった。位置と配列からステップのギザギザ(※オフ車のステップにはラバーがない)にガツンとぶつけたのかなという感じ。普通に歩けはする。
肩は最も簡素なものではあってもプロテクターが初めて役に立った結果といえる。ニーシンガードは……足首の方からすきまにもぐり込まれたのかなあ。
押し倒されて後輪に乗り上げられて冷却液をドボドボとかけ流しにされていた。
ナンバープレートやナンバーステーがぐんにょりひしゃげてるのが一番のダメージ。スイングアームの表面やアクスルナットも削られてギザギザしてた。
目の前が消防署であって、隊員の人が一番にかけつけてくれて怪我の確認やら事故車の退避やら道路上の液体に砂を撒いて掃き清めるやら大いにお世話になってしまった。ありがとうございます。
乗って帰るのは怖かったので購入した店まで運んでもらった。到着は営業時間をちょっとオーバーしてしまったけど、その時間ならまだ作業をしているということで対応していただきました。
使えるロードサービスが２種類あった。新車購入時に付随していてまだ更新しているものと、任意保険付帯のもの。事故で忙しいときにまどろっこしい自動音声を聞かされるのは苦痛だし、屋外で「～は何番、～は何番」みたいなのを聞き漏らさないのも難しいことなので、最初から人が応答してくれた方はポイントが高い。営業時間外やら定休日やらで販売店に運び込めなくて一時的に預かってもらう場合に、別日のレッカーが自己負担になるかどうかも対応が分かれた。つまり、任意保険付帯のレッカーはおまけなりのものだった。今月に任意保険の更新をしたときに二次レッカー費用が無料になります、という変更点が書いてあった気がするので、改善はしているらしい。
相手方の保険会社から最初の電話で 100:0 でと伝えられた。こういう(こちらに過失がない)場合に自分の保険会社は代理人になれないというのを風の噂で知っている。そういうときのために弁護士費用特約を付けている。使わなかったけど。
２回目の電話でバイクが全損扱いだということと、時価を上限にして補償するということを伝えられた。全損というのが意外なワードだったけど、要するに修理費用の見積総額(70 万円くらい)が中古車の購入費用より高くなったということなんだろう。スイングアームとリヤフレームがそれぞれ 10 万とちょっと、マフラーが 15 万円くらいするらしい。
向こうはグーバイクで走行 30000 km 以上の WR250R を検索して４件の車両価格の平均から 58 万といくらという金額を出した。自分のバイクの走行距離が 32000 km 台だから。
でも４件の平均というのはどうなのか。誰かサクラで 200 万円のバイクを出品してくれたりしないだろうか。簡単につり上げられるでしょう。また、30000 km 以上という条件もどうなのか。じゃあこちらは 40000 km 以下で平均を出しますよ。0 km の新車も 100 km の新古車も 1000 km も含めちゃいますよ。
Excel に直線を引いてもらって時価は３万円だけ上がった。
肩の部分がすり減ったプロテクター入りジャケットは購入費用２万円のおよそ１割、すねに穴の空いた靴下は購入費用２千５百円のおよそ５割が補償された。購入年月日で減価償却した結果らしいけど減価償却という概念を持っていないので何も言えることがない。
スマホはベルトに通して腰のポケットに入れていたのが完全に無傷だった。やったね。
ドライブレコーダーだとか後付けのリアキャリアだとか、車体にネジで固定しているようなものはバイクの時価の中に含めてしまって個別に補償はしないらしい。あっそ。納得はしていない。
ゴールデンウィークを含むひと月くらいバイクに乗れなくて、スイングアームにはギザギザが残って(気にしない)、リアフェンダーは純正の黒く垂れ下がったものに戻ってしまった(プラスチックだからアルミパーツに比べて軽くはある)。修理費用がパーツ代と工賃がそれぞれ 15 万円ずつくらいの計 29 万円で、およそ 30 万円が残った。
x y、y x を検索すればいいと思う。横着して単一の文字列を対象にして検索するようにしたら 10 や 20 を 1 や 2 と見間違えるバグを仕込んで頭を悩ませていた。あほ。■C 問題「Dash」。書いてある通りに実装するだけなんだけど最初の提出は WA×1 だった。問題文の最後がこうなんだけど、「高橋君が一度も倒れることなく N 回の移動を行えるか判定してください」、N 回目(最後)の移動の１ステップ目を終えた時点で体力が尽きた場合の判定がそれほど明らかではない。「
最後の移動で体力が-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」。難しくはないと思う。迷って手が止まってえらく時間がかかったけど。まず次数１の葉っぱを見つける。その相手は星の中心に決まっている。星の中心の相手は葉っぱに決まっている。すでに見た葉っぱは無視して新しい葉っぱの相手を見る。それが自分(星の中心)なら無視して、そうでないものがあるならそれは別の星の葉っぱに決まっている。という感じで次々に判定していくだけのことに 40 分ちょっとかけてしまった。最終形は、星の中心をキューに入れるようにして星のレベルを記録していくものになった。■こちらの提出 #41744985 を見ると次数だけで答えが出せるみたい。次数１は葉っぱに決まってる。次数３以上は星の中心に決まってる。次数２は星の中心でも葉っぱでもありうるけど、全体を見ると星の中心と次数２の葉っぱの数の比率は n 対 2*(n-1) に決まってるので、って感じだろうか。ヒントなしでは気がつけないよ。■面白いことを書いている人がいる。「ABC303-D この問題の正解者は実は間違っていた」。形式だけ見て気が付いたことを。「別のとらえ方」として書かれている４ステップの処理について。１ステップ目は dp[0][j] と dp[1][j] に基づいて dp[0][j+1] に一時的な値を保存している。２ステップ目は同じようにして dp[1][j+1] に一時的な値を保存している。３ステップ目は dp[0][j+1] と dp[1][j+1] に保存した一時的な値に基づいて dp[0][j+1] に本式の値を記録している。４ステップ目は dp[0][j+1] に記録した本式の値と dp[1][j+1] に保存した一時的な値に基づいて dp[1][j+1] に、おそらく誤った値を記録している。これは自分が提出 #41747349 で５行目と７行目がどれだけ長くても１行の多重代入によって値の更新をしている理由だし、ときどきは見た目を整理したい邪悪な欲求に負けて代入を複数行に分けてバグらせてしまうのと同じことである。たぶんね。
問題３ あなたは現在の富に上乗せして一〇〇〇ドルもらったうえで、次のどちらかを選ぶように言われました。五〇％の確率で一〇〇〇ドルもらう、または確実に五〇〇ドルもらう。問題４ あなたは現在の富に上乗せして二〇〇〇ドルもらったうえで、次のどちらかを選ぶように言われました。五〇％の確率で一〇〇〇ドル失う。または確実に五〇〇ドル失う。」■２つの質問への答えを決めてから読み進めると書いてあったのは、「
たぶんあなたはたいていの人と同じように、次のような反応を示すだろう。問題３では大方の人が確実な方を選ぶ。問題４では大方の人がギャンブルを選ぶ。」「
あなたは選択を決める前に、問題３では一〇〇〇ドル、問題４では二〇〇〇ドルを「もらった」はずだが、そのことに十分注意を払っただろうか。たいていの人と同じなら、そんなことは気にも留めなかったはずだ。この「プレゼント」は参照点に含まれてしまい、参照点は無視されるのがふつうだからである。」「
またあなたは、損得に対する自分の態度が、富の状態の評価に必ずしも左右されないことも知っているだろう。一〇〇ドル得をするのが好きで一〇〇ドル損をするのが嫌いなのは、富の増減の問題ではなく、単に勝つのが好きで負けるのが嫌いだからである。そしてまずまちがいなくあなたは、勝つことを好む以上に負けることを嫌う。」■自分の答え。問題３ではダブルアップチャンス(ギャンブル)を選んだ。問題４では確実な損失を選んだ。どちらも想定の反対だ。どういう心理かというと、問題３ではすでに一〇〇〇ドルというあぶく銭を手に入れていて、ギャンブルを選んでもそれを取り上げられはしないので、追加でもらえなくてもその嬉しさは減らない。一方で確実に五〇〇ドルもらうよりも倍額の一〇〇〇ドルを確率でもらうギャンブルに勝つ方が喜びは大きい。問題４では、すでに二〇〇〇ドルという十分に大きなあぶく銭を手に入れているので、それが確実に五〇〇ドル減ることに痛みは感じない。感じない痛みを取り除くために失う額を倍にするかもしれないギャンブルに参加することは、痛みや悔しさを生み出すマイナスばかりが目立つ。■どうだろう。たぶん国民性みたいな傾向もあるんじゃないかな。自分の答えは日本人の標準だと信じている。だって完全に自分の利益と感情に従っていてこれ以外の答えは考えられないんだから。■とはいえ、得するチャンスを逃したことをあとから知って、本気で損をしたように感じたり、(そこに他者が関わっていたことで)損をさせられたと感じれば腹を立てたりする、自分と異なる考え方をする人が存在することも知っている。自分の感覚ではあると知ってすらいなかったプラスのチャンスを逃したことはただのゼロであり、そこに悔しさはない。事前に知って皮算用をしていたとしても、参加費がゼロならリターンがゼロでも惜しむ対象がない。でもそうは考えないやっかいな(説明ができない)人もいる。■いやまあ、説明だけならできる。本の同じ部分(97 ページ)に書いてある。「
金銭的結果の場合には、通常の参照点は現状すなわち手持ちの財産だが、期待する結果でもありうるし、自分に権利があると感じる結果でもありうる。たとえば、同僚が受け取ったボーナスの額が参照点になることは、大いにありうるだろう。」 参照点が異なっているだけなのだ。どうして参照点をそこに置いたの？ って疑問がやっぱり理解できずに残るわけだけど。
(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 も出してしまって、そこから６分で別バージョンの解答を書き上げて AC を得た。つまり６分で解けたはずだよねってこと。コンテスト終了直後に WA 提出を眺めていてバグを見つけたので出し直して AC にしておいた。８方向の遷移先のうち１つがずれていたのが原因。'snuke' の各文字に対応したクロージャをチェインして出力に繋げる実装ってちょっとおもしろくないですか？ Array#inject メソッドがはまりすぎ(なので WA のままにしておけなかった)。■C 問題「Almost Equal」。制約がごく小さいので愚直に並べ替えて愚直に比較して答えを出した。■D 問題「Impartial Gift」。D は DP の D……ではない！ 差が一定以下で和が最大になるものだから、条件を満たす A の要素のうち最大のものと条件を満たす B の要素のうち最大のものを見つけて、いい方を答えにすれば良い。条件とは、現在見ている要素を a として、a-D から a の範囲の値が他方の数列に見つかること。■E 問題「Isolation」。UnionFind だと辺の削除はできないんだよね。注目するところは、辺の数はクエリの数を超えないということ。集合(Hash)で個々の辺を管理して許される。あとは辺の数が０と１のあいだで変化するのを掴まえて孤立頂点の数を管理する(変数名の o は orphan の o だよ。次数０の o でもあるかな)。サンプルの２が優しくて(「
2 番目の種類のクエリを行う直前の時点で、すでにその頂点と他の頂点を結ぶ辺が 1 本も存在しないこともあります」)、ペナルティを食う前にすぐ修正して提出したよね。いや、それでもペナルティは食らったんだった>WA。一度は書いた
E[a].clear がいつの間にか消えていたのが原因。■G 問題「Sort from 1 to 4」。もっと難しい類題を解いたことがある>ARC124-D「Yet Another Sorting Problem」(20211125)。あるいは UTPC2021-A「Make UTPC」(20220511)。今日の問題では、１から４の場所に納まるべき１から４の値の列が与えられる。ソートすればどの範囲が１の場所でどの範囲が２の場所か……ということがわかる。位置と値が一致しているなら交換は不要。１回のスワップでお互いの位置が正しくなるペアがあるならスワップして損はない。次は位置を交換している３つ組を見つけて２回のスワップで位置を正す。ここまで実装してあとはどうしようかと作業配列をインスペクトしながらサンプルを実行していたら、サンプルの２が神だった。残りは４つ組だけしかありえないので不一致の数を合計して÷４×３で OK。■F 問題「Merge Set」。名前からするとマージテクとかマージソートでうまくする問題かなと思うけど、うまい道筋をまだ見つけられていない。(ツイートを読んで書くんだけど) BFS も考えたけど隣接頂点リストが膨大になりそうで諦めた。ひょっとしてあなた(私です) M 個の値を頂点にしようとしていませんでしたか？■B 問題。今理解した。「5 つのマスの組 (A1,A2,A3,A4,A5)」という自己紹介がちゃんとあった。A よ、お前マスだったのか。■G 問題。「@kyopro_friends なるほど。書き方的に一般に成り立つように見えたので、例えば数が 6 種類あると上手く行きませんというのを伝えたかったです。」 うーん、わかりませんねえ。位置を正す方法(経路)に複数の選択肢があって、貪欲法では良くない経路を残してしまうのかなと思ったけど、そういうケースが作れないのと、そういうときにどういう方法がとれるのか。