/ 最近 .rdf 追記設定本棚

脳log[2022-07-22～]

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

2022年07月22日 (金) [AtCoder] 精進１。ABC260-F「Find 4-cycle」(青 diff)。２か所で「鳩の巣原理」のヒントを見てすぐに目を逸らすということをしていた。それが２、３日前。ヒントがあっても今日までかかった。■提出 #33392687 (AC / 335 Byte / 1597 ms)。一方の独立集合(V2)のサイズが意図的に小さく制限されているのはすぐに気がつく。これは要素でペアを作って１つ１つ調べても間に合うサイズ。つまり鳩の巣というのは V2 の要素のペアであり、ここに何かを詰め込んでいってあふれるのを待つ。それが何か。V1 の要素しかないんだけど、V1 の要素と V2 のペアを結びつけるものがしばらくわからなかった。目の前にきちんとお膳立てされていないとわからないんですね。辺をグループ化してグループ内で組み合わせる。■■■精進２。ABC132-E「Hopscotch Addict」(ギリギリ青 diff)。気がつけばなんてことのない問題。BFS をケン、ケン、パで３倍頑張るだけ。提出 #33383061 (AC) ■■■精進３。精進１の関連ツイート「アライグマ「F問題は鳩の巣原理なのだ！　類題は第一回最強コン決勝A問題『Equal Weight』なのだ！ https://t.co/3KBTMkCrt1」から第一回日本最強プログラマー学生選手権決勝-A「Equal Weight」。制約を見てびびる。ネタもシャリも最大 20 万種類あるから、ネタとシャリの組み合わせも、ネタとネタ、シャリとシャリの組み合わせも１つ１つ取り上げるわけにはいかない。これが 300 点問題？■提出 #33398275 (AC / 238 Byte / 498 ms)。がんばって鳩の巣を探しました。重さの散らばりが 1 から 100 万のあいだだから、組み合わせた結果(ふたつの和)は 2 から 200 万のあいだに収まる。ネタとシャリを組み合わせて重さをキーにして記録していくと、最大で 200 万回書き込むまでには重複が見つかる。■掛け算の組み合わせだと 20 万は大きすぎる上限だけど、足し算だと 100 万でも現実的な数字だというのが、見た目通りではなくて意外性があった。ヒント無しでは解けなかっただろうね。■■■精進４。ABC254-D「Together Square」(緑 diff)。自分の頭からは TLE 解しか出てこないので見ました。「AtCoder Beginner Contest 254 D - inamori’s diary」わっかりやっすーい。■提出 #33413694 (AC / 1545 ms)。prime_division を使った愚直解。遅いけど制限時間内ではある。■提出 #33414040 (AC / 190 ms)。さっきの提出は 1 から N の数について独立した処理をしていた。処理の連続性をいかして、配列をメモに使って、時間コストをケチると 8 倍速くなった。■Ruby によるすべての提出を見ると最速は 62 ms だから、まだ削れるはずなんだよね。わからんけど。しかも 62 ms のうちほとんどがインタープリタ起動にかかるオーバーヘッドだから、見かけ上の３倍差よりずっと効率が違う。

ツッコミを入れる

2022年07月21日 (木) [AtCoder] 精進。ABC260-D「Draw Your Cards」(緑 diff)。20220719に書いた。「D 問題が解けなかった３完」「まだ解けないよ」「解けずの緑になりそう」「LIS をやりながら配列の中間削除を繰り返す愚直解法しか思いつかない」ところで、コンテスト中の一番最初の提出 #33313999 (RE) の冒頭には BIT が貼り付けてある。だけど結局一度も使わずに LIS に流れていった結果どこにも辿り着けなかった。■提出 #33376903 (AC / 1129 Byte / 863 ms)。やっぱり BIT やったんですよ。むしろ配列の中間削除を繰り返すしかないような平衡二分探索木向きの問題に使える道具は、BIT か平方分割(？)くらいしか持っていないのですよ。■Ruby によるすべての提出を見ると、最速級が 300 ms 台に集まっている。読むと、Array#delete_at を繰り返しながら LIS をしているような……。解法が少なくとも２つあって、どちらの方法もよく知っていて、それなのに今日まで AC に辿り着けなかったってどうかしてるよね。■解けるはずの問題を落として一時的にレートが下がるのはまあいいんだよ、どうせ戻るから。でも上に上がる人というのは、多少の取りこぼしがあっても(なくても)難しい問題を解くことで飛躍していっている印象がある。600 点問題、700 点問題が全く解けないことの方が問題。……というように口先だけでわかったようなことを言いつつも、解けるように具体的な行動を積み重ねていったりできないのが、自分を含む一般人のあり方だと思います。たぶん、そのうち？いつの間にか解けるようになってたりするんじゃないかな？ AtCoder に関連して流れてくる「目標はあれとそれ、今日はこれをやる」みたいなのは異常者のツイートなので、真に受けて立派な人間になるんじゃあないよ。

ツッコミを入れる

2022年07月20日 (水) [AtCoder] 精進。第２回PAST-M「食堂」。周期にそって数を数える問題。しかし問題文の長さパラメータの多さからわかるように間違えずに数えるのが非常に難しい。制約が厳しいので素直で間違えにくいが遅いやり方をすることもできない。■提出 #33368195 (AC / 550 Byte / 423 ms)。４、５時間がかりの力作ですよ。初日から最初に好物が食べられる日までのあいだに好物でないものを何皿食べるかを数え、最初に好物を食べたら D 日のサイクルのあいだに何皿の好物とそうでないものを食べるかを数え、余った１サイクル未満の皿数に何皿の好物が含まれているかを数える。前半で累積和を作り、後半で数える。累積和では好物と好物のあいだに何皿の好物でないものを食べるかを記録した。■サンプルしか通らなかった提出 #13619835 (RE×1/WA×3/TLE×24) を書いた２年前より確実に前進しているね。たとえこの前の ABC が３完であり下手をすると AtCoder を始めたばかりの数年前に劣るパフォーマンスだとしてもね。■この手の問題はこれまでに少なくとも３問解いている。ABC175-D「Moving Piece」と ABC241-E「Putting Candies」と ABC258-E「Packing Potatoes」。どれも水 diff。

ツッコミを入れる

2022年07月19日 (火) [AtCoder] 精進。日曜日にあった ABC260-E「At Least One」(ギリギリ青 diff)。D 問題が解けなかった３完なので E も F も問題を一読して解法の見当がつかないことを確認しただけで終わっていた。■提出 #33354142 (AC / 410 Byte / 456 ms)。見当がつかないとは書いたけど尺取りの雰囲気は十分に漂っている。始点を決めて、N 個の条件を満たすまで範囲を伸ばす。一度条件を満たせばあとはどれだけでも伸ばすことができるけど、始点が後ろにあるほど長さの上限が低くなる。提出したスクリプトでいうと `I = Array.new(M+1){[]}` と `T = [0]*N` というデータの置き場所を用意したところが解法の８割。それぞれ、I が Ai や Bi といった 1..M の範囲の値から i を逆引きするもので、T が現在の尺取りの範囲が何種類の条件を満たしているかを数えるための 0,1,2 の３値の配列。■Ruby によるすべての提出を見ると、最初の提出 #33313831がコンテスト中唯一の AC だというのがすごいね。中身を見ると構成も記述も自分の提出とそっくりで驚く(Ruby で青色になるような人でも for ループ、while ループ、if 式をばりばりに使う手続き型のコードを書いてたりするんだ。そういうのはだらだらとまとまりがなくて読むのがつらい)。自分も時間内に書けて然るべきなんだよなあ。■D 問題「Draw Your Cards」は緑 diff だったみたいだけど、まだ解けないよ。土曜日の緑は昨日(20220718)片付いたけど、こっちの緑はこのまま解けずの緑になりそうだよ。LIS をやりながら配列の中間削除を繰り返す愚直解法しか思いつかないよ。

ツッコミを入れる

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 を解いたあとに読んだツイートによって階差数列とジグザグが結びついていたので、問題の構造がすごくはっきり見えた。今が解くのにちょうどいい時期だったのだ。

ツッコミを入れる

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

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