/ 最近 .rdf 追記設定本棚

脳log[2022-07-11～]

最近ひとつ現在へひとつ過去へ

2022年07月11日 (月) [Ruby] ABC259-C「XX to XXX」に関して、提出 #33137008 (WA×2) のデバッグをしようとして答えが見つからないでいた。判定条件に不備が見つからない。どうやら提出したご本人も気になっていたようで、他のやりかたで AC したあとで２つの解法を近づけていって、最終的に提出 #33137524 (AC) が得られている。この２つの提出のどの部分が WA と AC を分けているのか、まじでわからない。■■■デバッグプリントしたらわかった！ chunk の戻り値は Enumerator だから size メソッドが nil を返していてサイズチェックが機能していなかった。Enumerator#size の戻り値が NaN や SQL の NULL だったらサンプルが合わなくて気がついたはずだけど、運が悪かった。Ruby の nil は nil==nil が true なのだ。問題のサンプルがどちらも S.squeeze.length==T.squeeze.length だったのもつくづく不運。S=abc/T=abcd が間違って Yes になるなら気がつけた。■これ難しいなあ。たまにちょっと古いバージョンの Ruby を使うと String#bytes の戻り値が Enumerator だったりして、.to_a って付けるのめんどうくさいなあと思うんだけど(Array も Enumerator も Enumerable だけど、Array にしかないメソッドがあるからだね)、違いに気がつかないとめんどうくさいでは済まないんだな。どういう考えで String#bytes の戻り値が Enumerator から Array に変わって、chunk の戻り値は Enumerator のままなのかわからないけど、自分はブロックを与えたらブロックはその時点で評価され配列が生成される、ブロックを省いたらあとでブロックを与えられるように Enumerator が返るというパターンに慣れ親しんでいるので、chunk{...} の戻り値は期待を裏切る。■自分の提出 #33081469 を見れば chunk の戻り値にあえて .to_a を付けている。最初のバージョンでは .to_a を書かなかったはずで、Enumerator が返ってきたのを見て .to_a を付けて、提出して、そして chunk の戻り値についてまた忘れてしまっていた。次に chunk を使うときもやっぱり期待を裏切られるんだろう(鳥頭)。

ツッコミを入れる

2022年07月09日 (土) [AtCoder] 精進。今日あった ABC259-F「Select Edges」(青 diff)。辺を選ぶ選ばないで波及する影響をどう管理するか。ある辺を選ばないと決めたら、その辺が結ぶ２つの頂点 A,B はそれぞれそれ以外の辺から上限いっぱいの本数の辺を選ぶことができるが、選ぶと決めたらそれ以外の辺からは (上限-1) 本までしか選ぶことができない。局所局所の損得勘定で辺を選んだり選ばなかったりする影響が木の末端まで波及する。それを定数時間で管理する方法。■提出 #33128461 (AC / 568 Byte / 1440 ms)。ジャッジが途中で止まってしまって再提出していいものかどうか迷っていたら、だいたい提出から５分くらいでジャッジが最初からやり直しになった。そういう仕組みがあるのね。解法は、子につながる辺を選んだ場合に得られるスコアの最大値と、選ばなかった場合に得られるスコアの最大値を木の末端から積み上げていく DP。解き方はわかるんだけど、E 問題を片付けたあとの残り 15 分で解ききるのは無理なんだよなあ。仮に１時間あっても厳しいんだよなあ。

ツッコミを入れる

2022年07月06日 (水) 去年の年末にはまだ「口語はすっかりら抜きに席巻されてしまった」という印象だったのだけど、最近本を読んでいて「見れる」とか「食べれる」と書かれているのを普通に見かけることに気がついてしまった。活字ももうダメです。これを入力するときに ATOK は《ら抜き表現》と(普段見ない)指摘をくれるので自分の勘違いでないのは確かなのだけど、もはやら抜きと指摘することに意味がないのかも。学校でどう教えてるのか気になるな。たぶん先生も普通にら抜き言葉で生活してるでしょ。ら抜きも今では表現のひとつとして教科書で容認されているのかどうか。自分が小学生(中学生？)の頃これらは典型的な誤り例として教えられた。■■■「小説家になろうの「読者が見つけた誤字脱字を修正して作者に送る機能」により『ら抜き警察が2種類もいる』ことに気づいた - Togetter」ら抜きが自然な世代がすでに存在しているという話。ら抜きしか聞こえてこないのなら当然だろう。最初に聞いた言葉の印象って強いから、正しい言葉を知っていることを前提とした言葉遊びに子供が早くから触れるのは危ういと思ってる。嘘から出たまことというか、言葉は辞書によってではなくどのように使われているかによって意味が与えられるもので、世代を経るとスタンダードが変わる。本来あるべきものを知った上でズレを楽しんでいたつもりが、下の世代ではズレたものが本当になる。さておき、いろいろなコメントを読むにまだまだまだら抜きに完敗という情勢ではないのかな(負けは確定として)。それと、他の地域を知らないのだけど、ら抜きは関西で強いらしい。全国的には聞こえてくる印象ほどら抜きがひどくない可能性がなきにしもあらず(儚い期待)。

ツッコミを入れる

2022年07月05日 (火) [AtCoder] 精進。ABC133-D「Rain Flows into Dams」(緑 diff 下位)。水になるかならないかの頃に緑はほぼ埋まっていたのだけど、埋めきれずに残っている 10 数個のうちのひとつ。どれも一度は解こうとしたことがある。■提出 #33008639 (AC)。一端を決め打つ DP かなとか、値の１つが取り得る値を二分探索かなとか予想しながら問題文を改めて読んでみたら、階差数列で初期値の増減がジグザグに波及するので両端のつじつまを合わせましょうね、という問題だった。階差数列で解くのは何度か経験があるし、とくに先月(20220612) Lucky Number を解いたあとに読んだツイートによって階差数列とジグザグが結びついていたので、問題の構造がすごくはっきり見えた。今が解くのにちょうどいい時期だったのだ。

ツッコミを入れる

2022年07月04日 (月) [AtCoder] 精進。第10回PAST-L「N mod M」。第10回は手持ちの道具では解けなさそうな N 問題「400億マス計算」以外では L 問題だけが解けずに残っていた。余りをとる M が合成数でなければ 9 の逆元が使えて解けるんだけど。■提出 #32992192 (AC)。AC につながるヒントを見ました。「Lは10^D-1を mod 9M で計算することで、直接9で割れるようにするテク」。言われたらそれだけのことで、半完成だったスクリプトをゴミ箱から拾ってきてちょちょいといじるだけで完成したのだけど、独力ではたどりつけないのだよな。これくらいのことは mod について 1 を聞いて 10 を知るどころか 2 を知る程度の理解力で把握できそうなものだけど、脳みその使い方を知らない。■Ruby によるすべての提出を見ると解法は１つでも２つでもなさそうな雰囲気。どれ１つわからなかったな。

ツッコミを入れる

2022年06月29日 (水) [AtCoder] 精進。第10回PAST-O「3-順列」。やりたいことは比較的わかりやすいと思う。グラフがあって、二部グラフとそうでないものがある。N 個の３の剰余があって、０と１、２がある。０はどんなグラフにも当てはめられるけど、特に二部グラフでないものには剰余が０になる数しか割り当てられない。なのでまず余りが１と２になる数を最大限二部グラフに割り当てる。孤立した頂点にも１と２を割り振る。１と２を使い切って残りが０だけになったら、残ったグラフに割り当てて答えは Yes。二部グラフでないものに１か２を割り振るようでは答えは No。■提出 #32841134 (AC / 1176 Byte / 301 ms)。実装が難しかった。二部グラフに１と２を割り当てる方法。使った１と２の数で二次元二値の DP をして、使った個数の和を最大化すればいい。それがわかってもいざ実装すれば３つも４つもバグり散らかしていてデバッグに大変苦労した。

ツッコミを入れる

2022年06月28日 (火) [AtCoder] 精進。ABC151-F「Enclose All」(ギリギリ青 diff)。初めて見る問題。円をそれ以上小さくできなくなる状態がどういうものか想像すると、複数の点が円周上にあってそれ以上半径を縮めたり中心座標をずらしたりすると点が突き出てしまう均衡状態かな、と。そういう円は３点で決まるような気がしたけど４点になることがあるような気もした。テキトーな実装をする前に外接円について検索して「外接円 - Wikipedia」を読んで「最小包含円 - Wikipedia(en)」というものを知った。そこでアルゴリズムがいくつか紹介されていて、線形時間のアルゴリズムは難しかったので２番目に書かれていた Welzl's algorithm を実装した。■提出 #32821823 (AC / 992 Byte / 59 ms)。Wikipedia の言いなりに実装しただけなのでなんとも。最初の想定の答え合わせをすると、外接円は３点もしくは２点で決まるものを考えればいいのであって、４点を考える必要はなかったらしい。なんでかはわからない。垂直二等分線を引いて２点を満足させる円、３点を満足させる円を考えてみて、それから４点を満足させようとして偶然頼みになることを確認したりしてみればいいんじゃないでしょうか。■他の提出を見てみると最速級のものに「最小包含円 | libalgo」に書かれているのと同じ３重ループが目立つ。アルゴリズム的には自分が参考にした Welzl's algorithm と同じなんだろうか。自分が参考にして書いたのは再帰関数だったけど、再帰呼び出しの最奧の停止条件を初期値にして、再帰呼び出しからのリターンが多重ループへの飛び込みに対応するような、内外を裏返しにした相似構造が見える。

ツッコミを入れる

2022年06月27日 (月) [AtCoder] 精進。前回の ABC-E に関連して「既視感がある問題。それも WA がいつまでも取れなかったことで記憶に残っている」と書いていた問題。ABC118-D「Match Matching」(ギリギリ青 diff)。16 個の WA/RE 提出の末に 4 WA(#13237877) まではいっていたのだけど行き詰まっていた。それから２年を経て改めて問題を読めば、DP だろうなあと嗅覚が働く。３年前も２年前も謎の貪欲法(バックトラック付き。つまり打ち切りありの再帰)でやっていたみたいだけど。■提出 #32816278 (AC / 361 Byte / 71 ms)。マッチの本数に対して桁数の最大値を記録する DP をやって、なんとなーく経路の復元をして答えとした。DP の復元という比較的最近仕入れた概念は『典型90問』の成果。限られたパラメータを広範囲に展開して書き込むよりもっと上手い方法があるんじゃないかと思いつつ、ループの中で DP 配列を右へ左へ全長に渡ってなめなめ更新しても許されているのでまあいいか。■他の提出を見ると Ruby なら桁数でなく作った数そのものの最大値を記録するのでも良かったらしい。だけどこの問題を連想させた問題で Bignum に起因して TLE になっているので、そういう選択はできなかったな。最大で 5000 桁になるのを確認して避けたもんな。■Ruby で最速の提出はいずれも答えの数字を３つの部分に分けて考えているようだった。２年前の自分が 4 WA を解消できなかったのはこの構造が見抜けていなかったせいだろう。貪欲さが足りなかった。

ツッコミを入れる

2022年06月25日 (土) [AtCoder] 今日は日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）があった。自分のすべての提出。13 分余分にあれば６完だった！(空しい反実仮想)■特に書くことはないかな。(F 問題までの)傾向としては易化、典型寄りだったと思う。F 問題でも PAST の真ん中あたり(J とか K)に出そうな雰囲気。そういうときに点が取れないでどうするの？■C 問題で質問したよ。S の i 文字目を右から数えるのか左から数えるのか、問題文はわかるように書かれていないし(S=S1S2S3...Sn から成る。Si=1 のとき……とか。「Shortest Good Path」がそんな感じ)、サンプルの S がどれも左右対称だったから手掛かりがなかった。ビットなら LSB から数えるだろ常考、で納得するけども、文字列の常識は知らない。■解けたから簡単だというのは嘘だな。考えたことと罠を書いていこう。■C 問題「Robot Takahashi」。X が実数って書いてあるけど、与えられた数値(W)と、与えられた数値よりも(ちょっとだけ)大きな値だけを試せばいいよね。尺取りをすれば N の制約上限 20 万もクリアできる。与えられた数値よりちょっとだけ大きい値を試す必要があるのは、X 未満の子どもという条件で max(W) を勘定に入れるためには max(W)<X である必要があるから。■D 問題「Jumping Takahashi 2」。問題文を誤読したまま考えていた。つまり、あるジャンプ台からスタートしてジャンプを繰り返しながら全部のジャンプ台を巡らなければいけないのだと思っていた。サンプルを読めば間違いがわかるのだけど、頭の中でひと通り試行錯誤して実装してからサンプルを試す段階で初めて気がついた。ワーシャルフロイド法で解ける。■E 問題「Addition and Multiplication 2」。既視感がある問題。それも WA がいつまでも取れなかったことで記憶に残っている。調べたら初めて参加した ABC の D 問題「Match Matching」のことだった。しかもまだ AC してなかった>自分のすべての提出。ちょうどを要求されていない点で今日の E 問題の方が簡単だったのでは？その E 問題。問題文を読めばどの i を選ぶかよりも操作回数を最大化することが大事だとわかる。まずは最小コストの数字を使用して桁数を最大化する。次に桁数を減らさない範囲で最大限 i を 9 に置き換える。それから 8,7,... と順番に残された条件の範囲で桁数を減らさない限りにおいて i を i より大きい数字に置き換えていく。罠は答えの出力方法。サンプルに「答えが 64 bit整数型に収まらないこともあることに注意してください」と書いてあるのだけど、これをよくある 32 bit整数型に収まらない場合の警告だと思って、でも上限がどこかに定めてあるんでしょうと問題文をさらったけど見つからなくて、Ruby だからと深く取り合わずに提出したら TLE になった。答えを文字列で持つのが正解。■F 問題「Teleporter Setting」。これも最初は問題文が読めていなかった。求めるのは 1 から N までの最短距離。それに不定なテレポーターがどう寄与するか。不定なテレポーターが寄与しないなら普通に町 1 から BFS した距離表(D1)でもって D1[N] が答えだし、寄与するときに考えるパターンは２通りしかない。つまり、1 から i を目指すより 1 から 0 を目指した方が近いパターンと、N から i を目指すより N から 0 を目指した方が近いパターン。それだけではない気がしたとしても、それだけ。■コンテスト時間中に 4 WA と自分より先を行っていた提出 #32743897 をデバッグしようとして 30 分以上考えている。予想だけど、町 1 と町 N が不定なテレポーター(0)を介して連結な場合が抜けていると思う。たとえば 1-2-0-9-N というグラフ構造のとき、i の値によらず `min_a+min_b+2` が答えの候補としてある。

ツッコミを入れる

2022年06月24日 (金) [AtCoder] 精進。AGC056-A「Three Cells per Row and Column」(水 diff)。N が 3 の倍数のときは簡単だけど 3 で割り切れないと難しい。1 余る場合と 2 余る場合を手で構築してうまく敷き詰められないかと思ったけどうまくできなかった。■提出 #32694973 (AC / 582 Byte / 68 ms)。Array#sample と Array#shuffle! の使用がすべてを物語っている。テキトーにコンピュータに構築させたらええねん。■「テキトー」の解説。1 から N の順列を 1 つテキトーに選んで、i 番目の値が j のとき、j 列の i-1 から i+1 行目を # にする。順列の中で隣接 3 要素の少なくとも 2 つの値が連続しているときは上下に伸ばした # が連結してしまって不都合なので、そういう順列は不採用にする。1 行目から上に伸ばした # と N 行目から下に伸ばした # の扱いが特殊だけど、それぞれ N 行目、1 行目の同列に配置すれば行の条件と列の条件は満たす。そのうえでそれが N-1 行目、2 行目から上下に伸ばした 3 マスと連結になるなら連結成分の条件も満たす(このとき 2 マスの連結成分が 2 つと 4 マスの連結成分が 2 つできている。他は 3 マス)。■自動生成するまで気がつかなかったけど、N が大きいほど構築はテキトーにやって失敗しない。むしろ条件設定を失敗して N=6 の場合に構築できない(どの順列も条件を満たさない)ケースが目立った。人間は N=6 が一番簡単なのになー。

ツッコミを入れる

2022年06月23日 (木) ５年ぶり２度目にスタートした Salt and Sanctuary を今回はクリアした。先月発売された Salt and Sacrifice の前作。全然覚えてなかったけど５年前も今回も全く同じ大槌を振り回していて、同じ頭をくっつけた人間って同じ道を辿るのだなって。つるっぱげの女の子キャラでプレイしたけど、とってもかわいいし着せ替えも楽しい。手と足は重装で胴は軽装もしくは下着。頭は好みで。

ツッコミを入れる

2022年06月22日 (水) [AtCoder] 精進。ABC169-E「Count Median」(水 diff)。コンテスト当日に 23 分で D まで解いていながら残り 77 分で解けなかった問題。当日と後日を合わせて 6 WA している。■提出 #32668994 (AC / 210 Byte / 316 ms)。秒で考察が終了して実装量もご覧の通り。むしろどこでどう迷っていたのかがわからない。コンテストで安定した成績を残したいなあ。■考えたこと。中央値を最大化したいとき、数列の半分を上限(B 数列)に張り付かせればいい。反対に中央値を最小化したいとき、数列の半分を下限(A 数列)に張り付かせればいい。N が奇数のときは単純に N/2+1 番目の上限と下限のあいだが中央値として可能な範囲。N が偶数の時は、N/2 番目の上限下限と N/2+1 番目の上限下限を同じように求めて、その和(下限+下限と上限+上限)が取り得る範囲を定める。■どこで迷っていたのか思い出した。各要素が取り得る範囲が Ai 以上 Bi 以下という形で制約されているので作れる中央値の範囲(上限と下限のあいだ)に抜けがあるのではないかと考えたのだった。その不安はわかる。わかるけど、問題設定の理解が足りないせいで書かれていない制約を自分で作り出していませんか、と今となっては思う。望みの中央値を作るに際してどういう操作が可能か限界がどこにあるかよくよく具体的に考えてみれば。

ツッコミを入れる

2022年06月21日 (火) [AtCoder] 精進。ABC187-E「Through Path」(水 diff)。コンテスト当日に 25 分で D まで解いていながら残り 75 分で解けなかった問題。翌日のふりかえり>20210103p01。「全然ループの軸が見えなかった」と書いてあるが、以前も今日(の最初)も問題の形式に引っぱられて辺を中心としたループしか考えられていなかった。考えるのは頂点について。■仮に定めた木の根によって決まる親子関係とクエリの種類(t)によって、クエリは、a か b を根とする部分木に x を加算するか、部分木以外に x を加算すると理解される。部分木に加算するのはオイラーツアーと累積和の組み合わせでいけるし、部分木以外に加算するには全体に x を加算してから部分木を対象に -x を足せばいい。■提出 #32649747 (AC / 577 Byte / 832 ms)。以前の日記に「筆塗りを思い出した」とも書いてあるから当時からオイラーツアーは知っていた。硬直した視点が解けなかった唯一の理由。■解説を読めばオイラーツアーはいらなかった。それはクエリを処理しながら質問にも答えたいときに BIT を使って累積和の構築を高速化する方法。解説の最後に「また、各クエリで辺 e 以外では cai−cbi の値が変わらないことに注目し、c1 と cai−cbi の値を管理しても同様に解くことができます」とも書いてあるけど、えっと、よくわかりません。■■■木の全体を変化量(差分)の連鎖として見る。頂点の値は変化量の累積。変化量の累積は相対値なので木全体の値を一意に定めるアンカー(初項)として c1 に代表させる。根っこの値を代表値にすると都合がいいのは、親子関係で辺の向きが判別できるから。■提出 #32651136 (AC / 408 Byte / 958 ms)。時間もメモリ使用量もさっきの提出に劣ってるのが納得いかない。いやまあ、判断と計算を先送りしたせいでややこしくて、判断と計算の材料を蓄えるために余計なメモリを使ったんだろうなあとはわかる。報いがない。でも先送りせんと辺に注目してるのか頂点に注目してるのかわからんようになるのでしかたなかった。解説の最後の１行ってこういうことだと思ったんだけど違うかな。

ツッコミを入れる

最近ひとつ現在へひとつ過去へ

ここをクリックしてカテゴリ一覧を表示