/ 最近 .rdf 追記 設定 本棚

脳log[2020-06-28~]



2020年06月28日 (日)

最終更新: 2020-07-05T23:55+0900

[AtCoder] AtCoder Beginner Contest 172D 問題 Sum of Divisors

コンテスト全体については順当に、冴えない結果であった。あまり書くことがないので1つだけ。

 D 問題への Ruby による提出(実行時間昇順)

他が概ね 1000 ms ほどかけているところ、1つだけおよそ半分の 515 ms で済ませている>提出 #14757268

ループでは他と同じ式を使ってるんだけど、半分に割って足しているところが鮮やか。足し算の背後にある論理がわかりません。

N/2+1 から N までの数は掛ける2をするだけで N を超えてしまうので、その数自身しか数える必要がない、というあたりかな。ループの中の計算が必要ない。

こんな手の込んだことをしていながら提出時刻も早くて、Ruby の中では5番目なんだよね。一方の自分は、C 問題で脳死の愚直手続きスクリプトを書いていた>提出 #14743690。脳死のまま清書>提出 #14788308。ステートメントを減らそうとしてやりすぎた>提出 #14788890

 脳死といえば……

D 問題にも最初は脳死状態で挑んでいた。こういうスクリプト。

  1. N 要素の配列を 0 で初期化する。
  2. 1..N のそれぞれに対してそれ自身と倍数に対応する配列の要素を +1 する。
  3. 最後にその配列を使って K×f(K) (K=1..N) を計算して合計する。

でもサンプル3が親切にも N の上限値で、このやり方では時間がかかりすぎることに気付かせてくれた。さもなくばずぼらと拙速の代償として TLE を1個拝領していたことだろう。

 [AtCoder 参加感想] 2020/06/27:ABC 172 | maspyのHP

D 問題。問題と格子点の関連がさっぱりわからなかったのだけど、ループでシミュレートしてるΣ計算に N の一般式を与えようとしたときに、Σの中に整数除算があるから、反比例のグラフと軸のあいだの格子点の数に興味があるの? その前に、k*N/k*N/k を約分したり分解したりはできない?

 ABC172D - 西尾泰和のScrapbox

ところで、この縦に足す方法では、半分から先はどうせ1つしかないのにループを回して一つずつ足してしまう。ここを斜めに足せばループは半分で済む。しかしどうせ斜めに足すなら… 左上までしっかり斜めに足す。そうするとループの回数はルートNのオーダーになる。

画像が見えない(scrapbox も CSS を切らないと読めない)。まだ「斜めに足す」がわからない。√N のオーダーになるとは他所でも読んだが、わからなかった。

k*(N/k)*(N/k) の、N/k が1になるものだけを特別扱いするのでなく、2になるもの、3になるもの、4、5……で分けると定数係数としてΣの外に出せる(それとΣの区間も変化する)とか、そういう話なんだろうか。いや、どう書いてあるかはざっと読んだんだけど、読んだだけで解れば世話がないわけで……(あとでスクリプトにして確かめよう)。

 スクリプトにして提出したら 997 ms だったものが 68 ms になった。(比較のため Python だと 32 ms)

しかし明らかにもっとすっきり書く方法がありそうなんだよな、っていうかそれはすでに Python スクリプトとして示されてるんだけど、理解できないのです。

自分がやったのはすでに書いた通り、「N/k が1になるものだけを特別扱いするのでなく、2になるもの、3になるもの、4、5……で分けると定数係数としてΣの外に出せる」ということを利用して、k=1..N のループについて前から計算すると同時にループの反対側にある N/k==k ()となるケースを計算して両端からループを進めようということ。繰り返し回数は 1,2,3,...,N/3,N/2,N の半分になるはずなんだけど、中間地点がどこにあるのか、全長がいくつになるのか、わかりません。

でもまあ、√N のオーダーになってるみたいだから、N=a*a だとして、1,2,...,a-1,a(=N/a),N/(a-1),...,N/2,N なんでしょう。

 整数への切り下げがなければ

m=N/k; n=N/(k-1) なのを利用して 68 ms のスクリプトのループの中の式を s+=N*(N+1)/2; s+=k*m*(m+1) と整理できそうなんだけど、そうするとこれまたどこかで見たような式(と定数)でさらに整理できそうな雰囲気があるんだけど、m と n の関係は通分したり約分したりできる関係ではたぶんないんだよね(答えが合わないから)。

 AtCoder Beginner Contest 172 D - Sum of Divisors - Crieit

図がわかりやすい。オーダーをちょっとずつ改善していく構成が付いて行きやすい。そして最後に見逃せないこれ>「なお、O(N^1/3)の方法もあるらしいです。

格子点のやり方がこのオーダーらしい。さっぱり想像がつかない

じゃあね、せっかくリンクを張って紹介してくれた先(「格子点の数え上げの高速化 - memo」)を読みましょうよ、って話なんだけど、高速化云々より前に格子点がどのように関わってくるのかがまず知りたいよね。

 格子点の数え上げの高速化 - memo

まずここから(わかんない)。

1 から n までの約数の個数の総和(つまり、y=n/x の第一象限内の格子点の個数)は 2 \cdot \left(\sum_{i=1}^{\lfloor{\sqrt{n}}\rfloor} \left\lfloor\frac{n}{i}\right\rfloor\right) - \lfloor{\sqrt{n}}\rfloor^2 などを用いて計算することが多く

  • y=n/x と y=x の交点が (√n,√n)
  • y=n/x は y=x を軸にして対称
  • x=1..√n の範囲で y=n/x と y=x のあいだにある格子点を数えて2倍する? (たぶん y=x 上の格子点を一度だけ数えるよう気を配るのが面倒くさい)
  • x=1..√n の範囲で y=n/x と x 軸のあいだにある格子点を数えて2倍して、重複して数えた (1,1)から(√n,√n)を対角線とする正方形領域の格子点を引く
 「考え方」
  • 曲線上にある格子点が列挙できたら
  • 隣り合う格子点間を結んで斜辺とする各台形内の格子点を計算で求めるだけでいい
  • 斜辺上にある格子点にだけ注意してね(「傾きが既約分数の場合」)
  • 最初のステップの列挙には Stern–Brocot tree が使えるよ
 「求め方」
  • わかりません。ニュートン法みたいな試行を繰り返すの? むしろユークリッドの互除法?

 ループをまたいで式を整理した。

それというのも Python の方には2桁msの提出が1ページ以上もあって、オーダーは変わらないしブレもあるだろうとはいえ、28 ms と 32 ms のスクリプトのあいだには明らかに式の複雑さに差がある。

 Python によるすべての提出(実行時間昇順)

実行時間昇順で並べたときだけ自分の 32 ms の提出がリストされない。降順だったり提出時刻だったりでソートすれば現れる。消えているときは代わりに他の人の 32 ms の提出が2回リストされている。

32 ms の1つは自分のだが、28 ms は例えばこれ>提出 #14788253。平均タイムからして明らかに速い。

未だ及ばずながらだいぶ迫ったのではないか。

 これで最後。

最後に÷4するのにループの中で無駄に×4してるのが気になったので。

これを最適化というのではないか。この問題でしか意味のないループになった。少なくとも自分は式の意味を、途中からは理解していない。

実は最終版の while ループの中身は一番最初の 997 ms の提出とそっくりになっている。戻ってきた。

 Python のこの提出 #14841471

Ruby で書くとこんな感じ。

N = gets.to_i
p (1..Math.sqrt(N)).sum{|k|
	n = N/k
	k*n*(n+1)-k*k*k
}

違いを見比べると -k^3 がループの中にあるか外にあるかの差なんだろう。Wikipedia による と \sum_{i=1}^nk^3 = \left(\frac{n(n+1)}{2}\right)^2 らしい。

k*[n*(n+1)-k*k] からは、何か、意味が読み取れそうな気がするね。数学力があれば見えるんだろうか。数学力があれば意味を保ったまま易々とたどり着けるんだろうか。

 結局これでいい。

ループ後のつじつま合わせの正体が -\sum{k^3} だとわかったので……

N = gets.to_i
s,k,n = 0,1,N
while k<=n
	s += k*n*(n+1)
	k += 1
	n = N/k
end
s -= (k*(k-1)/2)**2
p s

 両辺の k は異なる。右辺の k が 1,2,3,... の順で繰り返される k として、それに対応して左辺を満たす k が N,N-1,N-2 の順で発見される。1対1対応ではない。


2020年06月27日 (土) 大阪大学、ブチギレやん」■マーク・ピーターセンさんの英語について書かれた本で、「○○ University」と「University of ○○」の違いについて触れられていた。いわく、University of Kyoto はアリだが、University of Meiji(?) はナシだという。府立大学と市立大学を統合した大学が University of Osaka を名乗るのは正当性があるように思える(※)。わかりにくいけど。そして OSAKA UNIVERSITY (阪大) の立場とは? もともとわかりにくかったものがわかりにくいというだけの話なんだよなあ。■■■続。「「University of Osaka」が大阪大学の英語名称として使用されている実態 — 大阪大学」 阪大が University of Osaka を名乗っておくべきだったという傍証(茶化しています)。とはいえ、あんまり区別されない実態があるなら名前をかすめ取るような行為を非難するのもむべなるかな。■あとから考えるとタイミングがアウトかもしれない。たぶん University of 地名 は固有名詞としてよりその地の大学の代名詞的意味合いを持ってると思う。あとからやってきてその呼称(呼称です)を固有名詞として使用するのはどうなんでしょうね。商標登録とか紛らわしいインターネットドメインを押さえておくとか、そういう奪い奪われは商売の世界だけにしてほしいな。■よく知らないけど、新しい方はシティカレッジ的な雰囲気がある気がする。大学の実際も「シティカレッジ」という用語の実際も知らないけど。■阪大が1位で、新しい大学は3位のマンモス大学になるらしい。たぶんカレッジではないし、頭数ではどっちも存在感があるな。


2020年06月25日 (木) 韓国の高校で出された日本語の問題です。 問題の下線部分と発音が同じものを選んで下さい。 日本人の皆さん、なめてかかると間違えますよ~」■難しい(笑)。日本語の「ん」は1種類や2種類ではないという話を聞いたことがあるけど、解ったためしがない。「っ」についてはちょっと違いがわかった。「まっすぐ」の「っ」は歯のあいだから息が漏れていた(初めて知った!)。「あさって」と「きって」の「っ」は舌で歯のあいだを埋めて「て」の発声に備えていた(初めて知った!)。「きっぷ」の「っ」は唇を閉じて「ぷ」の発声に備えていた(初めて知った!)。「がっこう」の「っ」は舌の根で口の中の微妙に奥まったところを塞いで「こ」の発声に備えていた(初めて知った!)。でも音としては「まっすぐ」を除いてどれも同じ無だと思うんだけど、そういうもんではないのか。■「っ」の場合をヒントにして、音ではなく口の形で区別することを意識したら3問とも正解だった! 耳は使わない! ていうかその違いに気がつけないのが日本語ネイティブの耳なのか?


2020年06月24日 (水) 読まれるブログフォーマットと読者のリテラシーと好き嫌いの話。https://mobile.twitter.com/chokudai/status/1275308912896405507■個人的にはとってもわかる。「関係ない写真を間に入れまくる、内容のないblog特有のフォーマット」「リテラシー高めのエンジニア向け記事だとマイナスに働く効果のが大きいかなー、と思ってた」■たしかちょっと前に似たようなつぶやきが、それも AtCoder 界隈であった。動画かテキストかという話。自分はこういう派>「わからない。提出 #13147757 (WA)。解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。」 テキストでぱっぱっと要点だけ知りたいし、まだら模様の理解度に合わせて時間を配分したいし、動画はそれができないから時間の無駄だと思ってる。それが言い過ぎだとしても、効率が悪いのはたしか。■過去に何度か書いたけど、自分は画像処理が苦手でアイコンをほとんど識別しないし、現実や画面を通した映像から読み取れることがごく限られているし、テキスト処理に特化している。人間(の集団)が嫌いである種の実写がきついというのがまた別にあるけども。AtCoder の解説動画がどんなものかはまだ確かめたことがないけども。誰々がすごく丁寧な解説をするという評判だけ聞いてるけども。■Web メディアがページを無駄に(※主観です)細かく分割するのも必ずしも広告がらみの理由ではないらしいし、マスにリーチするということは、その過程が見えるということは、とりもなおさずターゲットが自分から離れていくことを意味するのだともはや承知している。逆にターゲットが自分の方に近づいてくるとき、その過程は見えない。まだ自分にリーチしてないからね。だから好き嫌い(※主観)ではあっても善し悪し(※客観)ではないんだろう。■あと「エンジニア」っていってもピンキリで、ピンはごく少数なので……。Web サービスでユーザーが増えると質の平均が下がったと嘆きが聞こえてくるのはあるあるなので。■パソコン通信は知らないインターネット老人会からでした。


2020年06月23日 (火) 免許を更新した。更新手続きの休止期間が長引かなくて余計な面倒がなかったのは幸い。今日に備えて10年来の眼鏡を新しくしていた。ボーダーについてはなぜか 0.6 だと勘違いしていたのだけど、0.5 から 0.8 までいろいろ基準があっても 0.6 はないみたい。眼鏡屋さんが 0.7 だと言うのはしかたがない。自分の事情は自分で知っておく必要がある。いつまでも慣れない深視力は 10.0 mm、5.9 mm、0.9 mm で余裕(20mm3回より悪くなければいい)。■通知ハガキの記述と異なっていたのだけど、まず、4桁の番号は1つだけしか入力しなかった。ハガキには2組と書いてあったけど、1つは免許センターの機械が勝手に決めた。もう1点はハンコがいらなかったこと。用意するものに含まれていたから持っていったけど、そういえば使わなかったなと。

最終更新: 2020-07-09T19:28+0900

[AtCoder] AtCoder Beginner Contest 157D 問題 Friend Suggestions

 成長の記録

WA(Wrong Answer)の記憶なんてないまま新鮮な気持ちで挑戦したら普通に解けた。過去の提出を見直してみたらまあ、解答の構成がびっくりするほど瓜二つ。

では二者の分かれ目はどこに?

 友達の友達ネットワークの把握 (WA の理由)

WA の方はすべての人について一度だけ、その友達リストを処理している。AC した方は深さ優先探索で再帰的に処理している。なぜ再帰が必要か?

ある人 A と B が友達で、また C と D が友達であるとする。この時点で2つの友達グループがある。ここで A と C の両方と友達である E さんを処理するときに、A と C と E を繋ぐだけでは不十分で、すでに A や C とグループを作っていた B と D の所属グループまで更新しなければいけない。これをするためには配列を通り一遍に処理するだけではダメで、友達グループを記録した配列を何度もなめなめするか、再帰的に処理をする必要がある。

今ではこういう処理を Union-Find と呼ぶことを知っているし、グループの大小を管理することで書き換え処理が軽減できることも知っている。検索したらこれは序の口で、まだまだ奥が深いらしい。読んでないよ>「素集合データ構造(Union-Find)」「UnionFindTree に関する知見の諸々 - noshi91のメモ

 例えば ARC097 の D 問題 Equals
自分の提出 #8121358 (AC / 310 Byte / 340 ms / 16252 KB)
何も考えず小さいインデックスにグループを代表させている。
betrue12 さんの提出 #2497462 (AC / 1004 Byte / 315 ms / 15116 KB)
rank(木の高さ)の小さい方を大きい方に接続している。

インタープリタ型言語は基本的に書けば書くほど実行に時間がかかるものだし、一般化して構造化すれば無駄が生じる。多く書いてそれが速いなら、アルゴリズムが優れていることに他ならない。

ところで、つい先月の新しい提出にすごいのがありますね。「Ruby(2.3)によるすべての提出(実行時間昇順)

  • tamura2004 さんの提出 #13758236 (AC / 915 Byte / 291 ms / 12292 KB)

    1. UnionFind クラス唯一のインスタンス変数 @data 配列の初期値は -1 であり、これはすべての要素がサイズ1のグループを作っていることを意味している。def size(a); -@data[find(a)]; end @data ひとつでグループとサイズの両方を記録している。
    2. unite メソッドでは @data[b] = a によって b グループを a グループに併合している。事前の比較により a グループの方が b グループより小さくないことが保証されている。しかし同時に行っている @data[a] += @data[b] の意味がわかりにくい。これは @data のもう一面、大きさを合計している。
    3. find メソッドの再帰停止条件は @data[a] < 0。負になるのはルートに対応する要素の値で、ルートにぶら下がる要素は 0 以上の値で他の要素をポイントしている。

    @data 変数ひとつであれもこれも済まそうなんて、なんてケチで欲張りなんだ。

 必要なのは中身ではなくサイズ (TLE の原因)

コンピュータで処理するものなのだから、現実的制約は無視できない。集合演算と整数の引き算(+α)のコストの差。十分過ぎて必要のない情報にコストをかけてはいけない。

 「成長の記録」とか見出しをつけたけど……

引き合いに出した ARC097 の D 問題の AC 提出は去年の10月のものだった。3月時点ではそれを糧にできていなかったのだな。

さらに言えば ARC097 の D 問題には AC 提出の前に1つ TLE になった提出があったのだけど(#8121130)、TLE の原因がグループを表現するのに集合を使っていたから。3月の提出が TLE なのと同じ理由。まるで成長していない……(それどころか WA まで)。去年の10月は TLE のままで終わらなかったのが偉くて、30分くらいかけてグループの中で一番小さいインデックスにグループを代表させることにしたらしい。それがどうして3月に生きなかったのか……。

しかし今日の日記を書く過程でさらに省メモリかつ高速なスクリプトへの手がかりを見つけられたのはもっけの幸い。わずか2日での進歩である。

tamura2004 さんの提出を参考に。同じ問題に対する#10479576ではなくて、さっき引き合いに出した#13758236の方。

出力形式も変えたけど、ジャッジがスペース区切りと改行区切りを区別しないらしいのは kotatsugame さんの何かの提出で知った。これって kotatsugame さんの記事なんだけど……「AtCoderで実行時間0msを狙う - Qiita

どうしても1ケースだけ1msかかってしまう……せや!テストケース特定したろ!」「ちょっとくらい……探索サボってもバレへんか」「進む方向を定めるのに、ベクトル(sin(r),cos(r)) (r=0,...,99)を使っています。根拠はないです。

「根拠はないです」やあらへんでまったく。ゴルファーでもあるこんな人がジャッジの細かい仕様を知らんはずないんだよなあ。

それに問題を読み直したら「答えを空白区切りで順に出力せよ」と書いてあって、たしかにスペース区切りの出力例は出力形式の一例に過ぎないといえる。

最終更新: 2020-09-01T19:43+0900

[AtCoder] AtCoder Beginner Contest 157E 問題 Simple String Queries

 成長の記録(2回目)

コンテスト本番では問題文を読むところまでたどり着けなかったし、仮に読んでいても TLE は免れなかったろう。

しかし今や蟻本でセグメントツリーについて読んだので何の問題もない。適切なデータ構造を扱えますか、というだけの問題である。それと時間内に実装できますか、という……(BITを使おうとしてた時間を含めて3時間くらいいじくってた)。

提出 #14702134 (AC / 835 Byte / 449 ms / 39004 KB)
セグメントツリーを初めて実装したのがこのとき>20200610p01。今回は更新があったのと、ツリーを根からたどったのと、2の冪乗になるように詰め物をしなかったのが初めてのこと。
提出 #14702414 (AC / 774 Byte / 350 ms / 38728 KB)
最初の提出では本を見ながらそれにならって値を根からたどって取得したけど、そうしなければいけない理由はなかったのだった。以前の雰囲気実装と同じく葉から始めて値を取得するバージョンがこれ。速いよね。fn メソッドをインライン化したらもうちょっと稼げると思う。
提出 #14702882 (AC / 708 Byte / 333 ms / 38948 KB)
fn メソッドをなくしたけどあんまり変わらない。ループの中で多重代入というのが影響することも知ってるけど(20200428p01.08.01)、表記の簡潔さはゆずれない。
ST#[]= メソッドのために1個だけ詰め物をしたけど効果がなかったので(#14702766 RE)、詰め物の意味はない。消し忘れ。
スクリプト言語での popcount は二進文字列化して "1" を数えるものが多いみたいだった。高々26ビットだということがわかっているので log2(32) セット(=5組)のビット演算で済ませる魔法があるらしいし、そういう提出もあった。その他にも色々と『ハッカーのたのしみ』で紹介されている。ループを回してるのは芸がないね。

 Python によるこれらの提出。提出 #14610743提出 #10774518

内部データサイズが単なる 2N に見えるのが不思議。添字の扱い方はヒープに見えるけど、2の冪乗じゃないと階層が崩れて右が左に左が右になりそうなものだ。さっぱりわからん。

蟻本の著者の一人のスライドを見つけた。

  • 実際には,この実装なら n が 2 の累乗でな くても動作する

    値の更新の方はこのままではダメで,同様の 手法で再帰関数で書けば OK

  • ただし,配列サイズは MAX_N * 2 - 1 では 足りない – MAX_N * 4 取れば十分

まだわかりません。それに Python による fold 関数とスライドにある query 関数は引数の数が全然違うんだよね。片方は再帰ですらないし。

 追記@2020-09-01 「Segment Tree のお勉強(1) | maspyのHP

一方の提出ご本人による記事である。「いわゆる非再帰実装」「N = 2^n を仮定しない」 これこれ。ありがたやありがたや。


2020年06月22日 (月) [AtCoder] かなりの期間その存在を知らなかったし、今でも全くアクセスすることのないページが「順位表」。ABC 全完が当たり前でタイムアタックにしか意味がない人にとっては関心が向く唯一の対象かもしれないけど、E 問題も F 問題も、下手したら D 問題も解けない人間には興味も関係もないこと。……ということをわざわざ書くのは、Twitter を見ていて「そうではない人もいるのだなあ」と気付かされるから。コンテスト中に確認したいらしい。


2020年06月20日 (土) 進化論にかこつけて憲法改正をあおる自民党の広報マンガが誤っていると突っ込まれている。「唯一生き残ることが出来るのは変化できる者である。」(だから憲法を変えよう)とか言ってるけども、こちらが進化論になぞらえて読み取るメッセージは「勝てば官軍」であるので、なんだ何も間違っていないな(とっとと負けやがれ)。■「二階氏「ダーウィンも喜んでいる」 進化論の誤用問われ:朝日新聞デジタル」 マンガが子供にも失礼な子供だましなのよりも、この聞く耳のなさ、反省のなさが問題だと思うんよな。多様な意見への寛容さをアピールしたそうに見えるけど、そういう話ではない。それがわからないなら愚か者だし、わかってまぜっかえしてるなら不誠実だ。あ、それが平常運転でしたね。■日本心理学会@jpa_psych「日本人間行動進化学会「「ダーウィンの進化論」に関して流布する⾔説についての声明」 hbesj.org hbesj.org/wp/wp-content/… 6:14 - 2020年6月27日


2020年06月15日 (月) [AtCoder] 「【競技プログラミング】青コーダーが灰~茶コーダを緑diffの問題をACに導く Part1【考察過程】 - YouTube」■すごく、すっごくもどかしい。でも自分がもどかしい側に立っていることを知っている。実際、教えている青色の人が一瞬で問題を掴んで解法の見当をつけたところでは問題の理解が完了していなかった。教わっている人がサンプルの答えとなる数列を列挙している時間と図を使って、見ているこちらでも具体的な解法がわかった。実のところ題意を満たす満たさないを問わない部分列の全列挙がそう簡単なタスクではない。開始位置と終了位置の組み合わせで特徴付けられると気がつくまで、本当に網羅できているか不安があった。問題の輪郭と扱っている対象がはっきりしてくるまでに、手の運動と、目への刺激と、時間が必要なのだ。■「累積和」という単語で2つめの解法を新たに知った! 最初に N 要素を順に足してメモして、それは増加列だから二分探索で題意を満たす最小の範囲が確定できる。題意を満たしているかは引き算で。■■■高校3年生ですって。人生2周目でも追いつけないよ!「超高速!多倍長整数の計算手法【前編:大きな数の四則計算を圧倒的な速度で!】 - Qiita」■■■@2020-06-19 今日は蟻本で BIT(Binary Indexed Tree) という構造について読んだ。とりあえず累積和を記録するのに使えることがわかったけど、普通に配列にそれまでの総和を記録していくのと比較した強みがなんなのかがはっきりしなかった。たぶん更新がないなら普通に総和を記録していくのでいいと思う。定数時間で値の取得ができるし(BIT なら対数時間)。BIT を使いたいのは値の更新があるときだろう。普通に配列にある要素までの総和を記録していた場合は、値を更新するのにある要素より後ろのすべての要素が関わってきて線形の時間がかかる。BIT なら値の更新も対数時間で済む。


2020年06月12日 (金) GAFAコーディング面接こんな感じでした - yambe2002’s diary」■「ちなみに「ぼく」はIQ+30くらいの設定です。」というのがよく解らないけど、自分は対面だと IQ にマイナス100補正がかかります(元が100以上あるかは知らない。小学校でそれっぽいのを受けたけど結果は教えてくれなかったよね)。考えながら話せない。会話に脳のリソースを100%持っていかれる(つまり能力が足りていないということだからあわあわする)。なんなら見られているだけで何も考えられなくなる。隣に人が立つだけで小便が引っ込むような。■(ダミー問題だけど)履歴の管理。いきなりだと面食らうだろうなあ。まず問題のコンテキストがわからない。そのあたりはブログ筆者も同じとみえて質疑が参考になる。とりあえず配列で持って、現在位置を示すポインタを増減するかな、ということを自分で考えてから記事を読み直したらさっきより内容がよく掴めた。■計算量の話題。配列だとメモリの再確保で履歴の追加が最悪 O(N) とか、そんなことまで気にするの? 「「まあ、一般的な使い方なら大丈夫だろうけどね。これを解決するにはどうする?」」 えー、聞くの? ブラウザの進む・戻るボタンの履歴なんてタブとともに捨てられるんだから気にする必要なくない? 適当に上限を100にしてリングバッファにしても普通の利用者は上限の存在に気がつかないだろうから、それで。■「ところで、仕様追加をしたいんだけど。古い履歴は自動で捨てるようにしたい」 あっ、これって進む・戻るボタンに留まらない履歴管理の話だった(読み返したから思い出せた)。そうすると複数のウィンドウと複数のタブから報告される訪れたサイトと時刻のペアをどんどん追記していく感じになる。タイムゾーンとか文字コードはいい感じに。進む・戻るボタンの履歴はタブのセッション記録に別途保存しておくだけでいいでしょう。■「報告される」(※自分で書いた)ってなんだ? そんなサーバープロセスは存在しない、こともないか。Firefox は1タブ1プロセスなんてことはない。仮に履歴ファイルの排他が Web ブラウズのレスポンスを低下させるなら、プロセスごとに仮の履歴ファイルを作るようにして、プロセス終了に合わせて統一履歴ファイル(places.sqliteみたいな)にマージするようにするかな。それだとウィンドウごと、タブごとに見られる履歴の内容が最新でなく異なるって? じゃあプロセスの終了を待たずに随時バックグラウンドでマージすればいいじゃない。クラッシュ耐性も上がるよ。■「仮に履歴ファイルの排他が Web ブラウズのレスポンスを低下させるなら」(※自分で書いた)←こんな状況は考えられない。ブラウザの使用者は1人だよね。人間ミューテックス。


2020年06月10日 (水)

最終更新: 2020-06-15T23:25+0900

[AtCoder] 第二回 アルゴリズム実技検定 過去問

 自分のすべての提出

第三回まで過去問をやったけど(20200607p0120200607p02)、やはり順当に解けるのは K 問題まで。L 問題が自分にとってのチャレンジ。そこまでの問題が漏れなく時間内に解ければ上級認定。今回時間をかけてでもこれが解けたのは、今日たまたま読んでいた蟻本で紹介されていたデータ構造を雰囲気で実装してみたことによる。(この日記は今日書いた>20200602p02.03)

 L 問題。清書しようとしたらバグに苦しめられた。

  • 最初の AC 提出 #14164516 (AC / 1293 ms / 93824 KB)
  • 清書した AC 提出 #14183943 (AC / 870 ms / 61964 KB)

ヒープ構造を使って冗長な情報を削ったら同時に保険がなくなって、雰囲気実装のふんわりした理解の穴が露呈してバグに苦しんだ。AC と AC のあいだに 3WA。

二分木におけるLCA

木の構造が定まっているので、bit演算で計算できる。

こんな感じでうまいことできないかずっと考えていたのだけど、バグが取れてみれば、1つか2つのノードを見るだけでは済まないみたいなのでもとから無理だったっぽい。

 せっかく清書したけど

他の人(Ruby では2人いる)の提出を見ていたら不備に気がついた。

B,BL = A.map.with_index.to_a,1<<A.size.bit_length
H = [nil]*(BL-1) + B + [B[-1]]*(BL-B.size)

こんな感じで配列 A のビット長をもとにしてヒープのサイズを決めてるけど、例えば A のサイズが2のべき乗でヒープの最下段にきっちり収まるとき、なぜか倍のサイズを確保してしまってる。

例えば A.size == 8 のとき、ヒープサイズは 8+4+2+1 の 15 で十分だけど、上の BL の定義ではヒープ H のサイズが 31 になる。無駄のない定義は BL=1<<(A.size-1).bit_length。-1 がキモ。

 値の取得を最下段から遡ってやってるけど

これはうまくないみたい。今回は値の更新がなかったけど、更新を遅延させて値の取得に合わせて伝播させるためには、上から下っていかないといけない。

更新を遅延させるとか、考えてもみなかった。

それに最下段の要素に直接アクセスできたのは今回の問題に限った特殊条件ではある。範囲が配列の添字、0から連続する離散値だっていう。

必要になるまで考えないでいいことは考えない方針で。

 図を見てたらまだ理解が不十分で無駄なところがあった。

上に上るにしろ下に下るにしろ、自分が左右どちらの枝にいるかは考える必要がなくて、右ないし左に移動してから隣の階層に移動するだけで次の判断がつく。

右(左)に移動するとは、兄弟もしくは従兄弟ノードに移動するということ。最初に右の枝にいたか左の枝にいたか、そして右に移動したか左に移動したかで関係が違ってくるが、気にする必要がない。そのうえで上の階層に移動するとは、元のノードから見て親か伯叔父ノードに移動するということ。いとこの親ならおじさんである。

具体的なコードは次で。

 まとめ
提出コード長タイムメモリ
とりあえず AC660 Byte1293 ms93824 KB
ちょっときれいに AC740 Byte 870 ms61964 KB
十分に詰めて AC707 Byte 700 ms51032 KB

単純にタイムを縮めるだけなら他に優れた解法がある。これは次にこのデータ構造を使う準備みたいなもの。

 L 問題。Python で速い人の提出 #12961808 (279 ms / 61868 KB)

すっごく読みやすいね。実は答えを保持するスタックに push/pop するだけで答えになるらしい。しかも速い。

自分の最初の提出(TLE)がこれで、#14163100、素朴なやり方では無理なんだと思っていたのだけど、どういう違いが AC(速い) と TLE を分けたのか。

もっともらしいことを想像で書こうとしたのだけどよく解らなくなった。バグで無限ループしてるという方が納得できる。だって K の大小や D の大小に応じて、最小値を求める区間や回数はしっかり反比例してる。たしかに重たいケースで TLE になってるみたいだけど、他のケースの10倍20倍も時間がかかるというのは解せない。


D が小さくて A 数列がほぼ昇順に並んでるときに、N の上限の20万要素ちかい範囲から何度も最小値を選ばされる地獄を見ることがあるのか。いやあ、そんな意地悪な入力を与える人はいないと信じるよ。


2020年06月09日 (火) 今日「高襟(ハイカラ / high collar)」という言葉と当て字を仕入れた。はいからさんってそういう……(知らなかった)。


2020年06月07日 (日) PAST とエロゲは同じ値段。AtCoder 緑色は初級と中級に分かれるらしいが()、第一回なら中級の目があった>自分の提出。わざわざ初級認定をもらいたくはないが、中級なら。無料だった第三回は昨日終わっている。第一報があったときに確認したサンプル問題は明らかに難しくて、「取るべき問題をすべて取って、さらに2、3問のまぐれ当たりを上乗せしてやっと中級」という感触だったんだ。それで見逃した。

最終更新: 2020-06-09T19:05+0900

[AtCoder] 第一回 アルゴリズム実技検定 過去問K 問題 巨大企業

答えを出すだけなら簡単。社長を頂点とするピラミッドを遡るあいだに上司として出くわすかどうか確認するだけ。こういう問題は好き。逆にいつまでも数が合わない数え上げ問題は嫌い>禁止された数字への自分の提出。そもそもサンプルへの答えがいつまでも一致しないから、提出に至らないスクリプトが山ほど隠れている。

簡単ならどこが問題か。

 最初の提出 #14088806 (RE と TLE)

N の上限が15万だから、そして組織が非効率の極み直列15万階層だったなら、1つのクエリに答えるために15万マイナス1回階層を上らなければいけない。クエリは最大10万個ある。

そこは一応読めていたので、社員ごとに社長から何階層下にいるかという情報をメモしておいて、社員間の階層の隔たりと同じ回数だけ上司をたどれば答えが出せるようにしていた。でも TLE と RE。最悪の場合はやっぱり15万マイナス1回たどらなければいけないのだから、TLE はまあ当然。

 2番目の提出 #14089327 (RE)

社長から始めて決まったやり方で社員を一列に並べていったら、ある社員とその部下と部下の部下以下末端までを一定の連続する範囲で表せるのではないかと考えた。なんのことはないそれって深さ優先探索と同じ順番だったのだけど。

それで TLE はすべてなくなった。1度だけ15万マイナス1階層をたどってしまえば、あとはすべてのクエリに定数時間で答えられる。

しかし TLE はどれも RE に変わっていた。最初の提出からかなりの数存在しているこの RE は何だ? RE ってだいたいはヌルポだからよくある配列の範囲外アクセスが原因だろうと、考えるのを後回しにしていた。しかし目を皿のようにして調べてもその可能性はなかった。

 3番目の提出 #14090337 (AC / 394 ms / 22832 KB)

再帰呼び出しをやめてスタック変数を……というと意味が違う。スタック構造を持つ変数をスタックの代わりに使うようにしたら通ったので、呼び出し階層が深すぎたのが RE の原因だった。最悪で15万マイナス1階層は深すぎるだろうなあ(最初から読んでおけ)。

 4番目の提出 #14102282 (AC / 394 ms / 21500 KB)

  • N 回繰り返す前処理のループで if を取り除いた。
  • if を取り除いたことでスタックを社長で初期化するときに検索がいらなくなった。一石二鳥。
  • 変数 T,L,R は一列に並べた組織構造(T)と、そこに張った社員ごとのインデックス(L,R)という役割だったのだけど、実は T は配列である必要がなくカウンタ変数で十分だった。(RDB でもインデックスに情報がすべて載っていて表がいらないケースがあるよね)

しかし実行時間は変わらず。「Ruby によるすべての提出(実行時間昇順)」を参考にすると、

  • 回答の出力を一行ずつではなくまとめた方が速い。(システムコールを減らす、の類だと思う)
  • スタック(変数)に一度に要素を詰め込まない方がたぶん速い。
  • p メソッドが puts メソッドより遅いかもしれない。

ということが言えると思う。他に差がつく要素があるだろうか。

最終更新: 2020-06-26T13:37+0900

[AtCoder] 第三回 アルゴリズム実技検定 過去問

 自分のすべての提出

やはり解けたのは K 問題までだった。ただし第一回と違って途中で1問落としたりはしていない。もうひと踏ん張りで80点を超えて上級だけど、残された問題の予想される難しさと裏腹に考える時間が残ってないんだよなあ(本番じゃないので途中でお風呂に入って本を読んだりしていたけども)。

第一回、第三回に共通する問題の傾向として、数学的応用的な要素が抑えられていて、愚直に効率的なコードが書ければ解けるものが選ばれている印象。よく知らないけど、一般的なお仕事コーディングに寄せていこうとしてるのかな。基礎的な知識とその初歩的な運用に漏れ抜けがないことを確認しようとしてるのかな。(緑色以下のコーダーには保証できることがない、というツイートを見かけたので。このへんとか>https://mobile.twitter.com/chokudai/status/1274756588624965632)

 L 問題 スーパーマーケット

Python で解けることは運営元で確認してるらしいので()、Ruby でも方法はあるはずなんだよなあ。

タイムだけちらっと見た>Ruby でのすべての提出。提出数は4つで、ユニークユーザーは2人。2689 ms < 2726 ms < 2747 ms < 3735 ms。やっぱり方法はある。

TLE のケースはメモリの食い方が特異的に大きい。ざっと 1.5 倍。他のケースを見ると、必ずしもタイムとメモリ消費量のあいだに比例関係があるわけではない。メモリの割に時間がかかるのは M が大きいんだろう。TLE ケースは M も大きいんだろうけど、特に N と K が大きそう。K が大きくても配列の shift はポインタのインクリメントで済むようなので(Ruby-1.9の array.c で確認)、あまり影響がない。delete_at(1) を [1]=[0] and shift に置き換えたら一部速くなったから、やっぱり shift は問題ない(提出 #14129916提出 #14130610)。N が大きいと……、M 回のループで4回ずつ行う二分探索の時間に影響する。N は棚の数だから商品数(メモリ)と商品の検索(時間)の両方に響く。問題が「手前から ai 番目までにある商品を見た後、見た商品のうち最も消費期限の値が大きいものを選んで棚から取って購入します」だから、棚を選ぶ検索は避けられない。方法があるとしたら、予めうまいことソートしてしまってループの中では検索しないか、4回を2回に減らすか……。

 M 問題 行商計画問題

 提出 #14141040 (Ruby / TLE)

半分以上がTLE。ACも17個あるからやり方は間違ってないと思う。しかし PAST の問題が考察よりも実装重視の傾向を持っている以上、TLEに甘んじるわけにはいかない。でも無理ぽ。

 提出 #14144878 (C++ / WA)

TLE がすべて WA か AC になりました。C++ のちから。TLE の陰に WA が隠れていたということで、やり方が間違っていた。

 提出 #14145227 (C++ / AC / 1695 ms / 74616 KB)

Visited フラグを立てるタイミングを誤っていたのと、訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた。

この問題を Ruby で、試験時間内に解けるなんてことがある? ちなみに現在 Ruby で AC 提出はない>Ruby によるすべての提出

ところで、1695 ms は C++ 最遅だった。C++ を使うなら2桁msで解けるらしい。

 問題名で検索した。

さっき「訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた」と書いた。その対策として、関心のない街を迂回するルートを2街間の最短経路として採用するようにした(たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは2本以上の2街間最短ルートの組み合わせとして現れてくるので。

でもこのステップで求めるものを、2街間の移動コストに加えてその際に通過する街と定義したなら、もっと速くゴールにたどり着けていたかもしれない。

解答は2パートに分かれているが、どうやら後半は幅優先探索ではなく DP でやるものらしい。もちろんその方が最遅より速くなるだろう。

でもまだ……。一度通過した街に戻るのにも移動コストがかかるから、状態や遷移には現在位置が関わってくる。それをベルトコンベヤ式に取り扱って答えにたどり着けるイメージが湧かない。二次元の遷移が解らない。

 色と認定の関係

https://mobile.twitter.com/atcoder/status/1273915562989502465

 現在 M 問題で唯一 AC を獲得している Ruby による提出 #14152776

気がついたこと

  • (たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは2本以上の2街間最短ルートの組み合わせとして現れてくるので。」と書いたが、あれは嘘だった。
  • 注目している K 地点間の移動コストは K*(K-1)/2 通りを調べるのではなく、K 通りを調べるのが良さそう。

    終点を K 地点に限って試行回数を増やすより、終点を N 地点から限らず試行回数を K 回に留めるということ。

  • 後半はワーシャル-フロイド法に見える3重ループ。

    ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト。


2020年06月06日 (土) どこへともなく。GitHub を使ってるなら blame の画面で行番号のすぐ左にアイコンがあって、そのラベルが「View blame prior to this change」。cosmetic なコミットを無視して blame を遡りたいのは、残念ながらあるあるなので……。■blame はいかにもコストがかかりそうな操作だから()、一度開いた画面はあまり閉じたくないかな。blame からコミットを確認するときは新タブで開く。インクルードガードやコピーライトコメントみたいに初版から不変の行が一行でもあると、ログを完全にたどらないといけない雰囲気。