/ 最近 .rdf 追記 設定 本棚

脳log[2022-07-24~]



2022年07月24日 (日) [AtCoder] 精進。第2回PAST-O「可変全域木」。最小全域木に余分な辺を1本足して代わりに不要になった辺を取り除くと重みの和がどうなるか。まず、木に辺を1本足すと木はループを1つ持って木ではなくなる。不要になる辺はループを構成する辺のうちのどれか1本。追加した辺が頂点 A と B を結ぶなら、取り除ける辺は A と B のパス上の1辺。そのうち重みが最大のものを取り除けばいい。パス上の最大コストの1辺を効率良く探す方法は? ダブリングで A と B の LCA までさかのぼるついでに見つけましょう。■提出 #33481914 (AC / 1107 Byte / 669 ms)。去年はまだ解けなかった>WA。これで第2回はコンプリート。第10回まであるなかで初のコンプリート。自分のすべての提出


2022年07月23日 (土) [AtCoder] 今日は ABC261 があった。E までの5完だったのに2連続爆死したあとのレートをさらに下げてくるとは思わなかったよ。コンテスト成績証 - AtCoder。F 問題はデータ構造でなぐるだけの問題だったので終了後に AC をとっておきました。D と E の方が難しかったんだよなあ。それなのにそれぞれ緑下位、水下位の難易度評価なんだよなあ(つまりみんな解いている)。E 問題にはスマートな解き方があるみたいで、自分のは 1410 ms かかってるけど3桁 ms で解いているのが目印>Ruby による E 問題へのすべての提出。ビットのスタートが1の場合の累積結果と0の場合の累積結果を分けて 30 ビット並列で計算しておいて、初期値& で初期値が1のビットに対応する累積結果を取り出し、~初期値& で初期値が0のビットに対応する累積結果を取り出すみたい。実際、初期値2種類、出力2種類の4通りしか考えることがない単純な問題なんだよ、本来は。自分の提出 #33472932がなんで実際のビット演算をする代わりに :nop, :zero, :one, :flip という疑似演算子を使っているかというと、初期値のビットが1の場合と0の場合の2種類のケースを分けて準備すればいいということに気がつけなかったから、0が来ても1が来ても1つのデータで両対応できるように、疑似演算子を操作して実際の演算を遅延させるしかなかった。疑似演算子だから 30 ビット並列でまとめて計算することもできなかった。不思議だね、愚か者は自分で問題を難しくするんだね。そして本当に難しい問題は自分が理解できる程度まで過度に単純化して間違えるんだよね。度し難い。


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


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


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


2022年07月19日 (火) [AtCoder] 精進。日曜日にあった ABC260-E「At Least One」(ギリギリ青 diff)。D 問題が解けなかった3完なので E も F も問題を一読して解法の見当がつかないことを確認しただけで終わっていた。■提出 #33354142 (AC / 410 Byte / 456 ms)。見当がつかないとは書いたけど尺取りの雰囲気は十分に漂っている。始点を決めて、N 個の条件を満たすまで範囲を伸ばす。一度条件を満たせばあとはどれだけでも伸ばすことができるけど、始点が後ろにあるほど長さの上限が低くなる。提出したスクリプトでいうと I = Array.new(M+1){[]}T = [0]*N というデータの置き場所を用意したところが解法の8割。それぞれ、I が Ai や Bi といった 1..M の範囲の値から i を逆引きするもので、T が現在の尺取りの範囲が何種類の条件を満たしているかを数えるための 0,1,2 の3値の配列。■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)。おとつい1時間溶かして解けなかった問題じゃん。そのときも二分探索は書いていたし、A と B で割る二種類の割り算も書いていた。でもサンプルの4が合わせられなかった。なんで今日は AC なんだろうね、不思議だね。■まじめに書くと、おとついと今日では二分探索で探ろうとしていたボーダーの意味が違う。おとついはいったん増減の幅が a,b に固定されていることを忘れて、a 対 b の比率を保ったまま定まる平均値を求めようとしていた。でもそこから答えに近づけなかった。今日はまず、答えとなる最小値を二分探索で決め打ってから、必要となる数列を増加させる回数を求め、同じ回数を減少させるときに数列が維持できる水準(どの値より上を切り捨てるか)を二分探索した。2つの二分探索による2つの水準が逆転するならそれは矛盾であり答えとして成立しない。この考え(ARC144_b_TLE.rb27)は間違いではなかったけど、二重の二分探索に線形時間のスキャンが重なるので数十秒の時間がかかって TLE が必至。AC 提出は log を1つ外そうと最適化した結果であり、最初からあの形が頭の中にあったわけではなかった。直接最適な答えが導き出せないあたり、力が及んでおらず本番で解けないのも仕方のないことかもね。


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


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


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


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


2022年07月11日 (月) [Ruby] ABC259-C「XX to XXX」に関して、提出 #33137008 (WA×2) のデバッグをしようとして答えが見つからないでいた。判定条件に不備が見つからない。どうやら提出したご本人も気になっていたようで、他のやりかたで AC したあとで2つの解法を近づけていって、最終的に提出 #33137524 (AC) が得られている。この2つの提出のどの部分が 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)。辺を選ぶ選ばないで波及する影響をどう管理するか。ある辺を選ばないと決めたら、その辺が結ぶ2つの頂点 A,B はそれぞれそれ以外の辺から上限いっぱいの本数の辺を選ぶことができるが、選ぶと決めたらそれ以外の辺からは (上限-1) 本までしか選ぶことができない。局所局所の損得勘定で辺を選んだり選ばなかったりする影響が木の末端まで波及する。それを定数時間で管理する方法。■提出 #33128461 (AC / 568 Byte / 1440 ms)。ジャッジが途中で止まってしまって再提出していいものかどうか迷っていたら、だいたい提出から5分くらいでジャッジが最初からやり直しになった。そういう仕組みがあるのね。解法は、子につながる辺を選んだ場合に得られるスコアの最大値と、選ばなかった場合に得られるスコアの最大値を木の末端から積み上げていく DP。解き方はわかるんだけど、E 問題を片付けたあとの残り 15 分で解ききるのは無理なんだよなあ。仮に1時間あっても厳しいんだよなあ。