/ 最近 .rdf 追記設定本棚

脳log[2022-07-16～]

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

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

ツッコミを入れる

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 が一番簡単なのになー。

ツッコミを入れる

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

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