/ 最近 .rdf 追記設定本棚

脳log[2022-07-18～]

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

2022年07月18日 (月) [AtCoder] 精進。ARC144-B「Gift Tax」(緑 diff)。AtCoder Problems に Easy 問題を推薦してもらったら出てきたんです。まだ解いていない緑 diff はどれも解こうとしたけど解けなかった問題として名前を覚えてるんだけど、これは見覚えがなかった。■提出 #33348708 (AC / 177 Byte / 1181 ms)。おとつい１時間溶かして解けなかった問題じゃん。そのときも二分探索は書いていたし、A と B で割る二種類の割り算も書いていた。でもサンプルの４が合わせられなかった。なんで今日は AC なんだろうね、不思議だね。■まじめに書くと、おとついと今日では二分探索で探ろうとしていたボーダーの意味が違う。おとついはいったん増減の幅が a,b に固定されていることを忘れて、a 対 b の比率を保ったまま定まる平均値を求めようとしていた。でもそこから答えに近づけなかった。今日はまず、答えとなる最小値を二分探索で決め打ってから、必要となる数列を増加させる回数を求め、同じ回数を減少させるときに数列が維持できる水準(どの値より上を切り捨てるか)を二分探索した。２つの二分探索による２つの水準が逆転するならそれは矛盾であり答えとして成立しない。この考え(ARC144_b_TLE.rb27)は間違いではなかったけど、二重の二分探索に線形時間のスキャンが重なるので数十秒の時間がかかって TLE が必至。AC 提出は log を１つ外そうと最適化した結果であり、最初からあの形が頭の中にあったわけではなかった。直接最適な答えが導き出せないあたり、力が及んでおらず本番で解けないのも仕方のないことかもね。

ツッコミを入れる

2022年07月17日 (日) 「「夜の運転は注意しないといけない」を×とし、「昼も注意しないといけない」、つまり、問題文から「昼の運転は注意しなくてもよい」を読み取れないと免許は取れない。 - REV のブックマーク / はてなブックマーク」■これって免許試験に関する定番の不条理ネタなんだけど、つまり自分はネタだと認識してるんだけど、あまりによく見かけるのであえて否定したい。■たぶん元ネタにあたるものはあって、それは教習所で自習に使える模擬テストなんじゃないかと思ってるけど、自分はほぼ利用しなかったので判然としない。■本番では問われないだろうと考える理由は、「夜の運転は注意しないといけない」は、たしかに日常会話ではそれ以外の状況では注意を必要としないことを含意することが多いし、それを読み取れた方が会話がスムーズだけど、免許試験が問うのは法律で定められている事柄であって、書かれていないことを読み取る能力は求められていないし、むしろ勝手に読み取ってはいけない。そのような理解を問う試験において、出題側が解答に書かれていないことを勝手に読み取り、屁理屈で減点をすることはなかろうと思う。■このネタが広く受け入れられる理由は、書かれていることを書かれている通りに読み取れない人間が感じる(故なき)不条理に慰めを与えるからだろうと思う。免許試験の問題にひっかけはないよ。正しく過不足なく文章を理解する能力が求められているだけ。もう昔のことなので今改めて試験を受けて同じ感想が出るかどうかはわからないけど。■たとえばこれが「注意しないといけないのは夜の運転だ」だとまた話が違ってくるかな。「普通自動車は高速道路を走れる」と「高速道路を走れるのは普通自動車だ」が違うのと同じ。同値関係なら入れ替えても意味は同じだけど、「A は B」がまず意味するのは A が B に含まれるという包含関係なので、同値であることを確認せずに入れ替えたら意味が違う。違うのに一緒くたにするから不条理が生じてネタになる。

ツッコミを入れる

2022年07月16日 (土) [AtCoder] 今日は ARC144 があった。B 問題「Gift Tax」で早々に行き詰まってしまって１時間を溶かしてから、離脱する前に C 問題「K Derangement」をひと目だけでもと読んでみたら、まあまあとっつきの悪い問題ではない。実際、終了直前の提出 #33273999 こそ WA だったけど、見つけていたダメケースにきちんと対処すれば AC になった>提出 #33274921。手も足も出ない方が悔しくないんだよなあ。

ツッコミを入れる

2022年07月14日 (木) [AtCoder] 精進１。ABC034-D「食塩水」(水 diff)。これまで何度も解こうとして解けていなかった問題。諦めて解説を読もうとしたこともあるけど、SlideShare がポップアップでスライドを隠し、自分は無粋なポップアップを閉じるためにクリックをする手間はかけられないので(20170403)、読めないし解けないのだった。■提出 #33224471 (WA×1)。以前は DP で解こうとして解けなかったりもした。今日の嘘解法は、いったん全部の水溶液を混ぜたあとで、取り除くと最も濃度が上がるものを１つずつ選んで取り除いていく方法。結構好成績だったんだけど嘘は嘘だったらしい。■提出 #33224936 (AC)。他の提出を見た。実は二分探索を使うらしいという噂は聞いていて考えてみたことがあるけど、肝心の判定部分(７行目)が自分で導き出せないでいた。最終的な濃度を決め打てば各溶液ごとに溶質の過不足が具体的な重さでわかるので……ということでした。■■■精進２。第１回PAST-M「おまかせ」。実は最初に選んだ今日の１問はこちらだった。「浮気予防を解くために浮気予防の解説を読むのは癪だけど、Builder Takahashi を解くために浮気予防の解説を読むのは許されるような風潮が、あるとは思いませんか」と同じ理屈で、「おまかせ」を解くために「食塩水」を解いたのだった。■提出 #33225721 (AC / 448 ms)。ただの亜種なのでなんの問題もなく。ただ、Ruby によるすべての提出を見ると 448 ms は桁違いに遅いので、もっとうまいやりようがあるみたい。

ツッコミを入れる

2022年07月13日 (水) 「超わかりにくくね!?　オジさんはなぜナビをノースアップにするのか問題 - 自動車情報誌「ベストカー」」■おじさんなのでノースアップです。メリットデメリットは本文中に書いてあるし、一方的にノースアップがなしという記事ではない。自分が地図をノースアップにする理由は、脳内地図を作りたいから。ヘディングアップにしてぐるぐるぐるぐる地図が回転してしまうと何も頭に残らない。いつまでたっても脳内地図が完成しないし方向感覚が身につかないし自分がどこにいるのか見当がつかないしで、いっときも地図から目が離せないままになる。慣れればノースアップの地図を好きな方向から眺めて仮想的にヘディングアップにできるけど、逆はできない。ヘディングアップの地図は１枚の地図ではないので。■RPG のミニマップもどっちに何があるか地理が把握しやすいように向きを固定するんだけど(武器屋は町の右上にあるとか覚えたいじゃない)、なんとなくヘディングアップがスタンダードな雰囲気を感じるなあ。クエストターゲットを画面中央に据えたお使いオープンワールドゲームとか。

ツッコミを入れる

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 を解消できなかったのはこの構造が見抜けていなかったせいだろう。貪欲さが足りなかった。

ツッコミを入れる

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

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