最終更新: 2020-08-15T20:50+0900
コンテスト中に解けなかった(問題文を読むところまでいかなかった)問題に挑戦。
「連結成分」っていうのがわかんないよね、まず。出力例１の解説を読むに、頂点集合が辺で繋がれたいくつの部分に分かれるかを数えるみたい。
L<=[C,P].min && [C,P].max<=R だから、その否定。(追記：これは嘘。実装中に気がついたがこれだと頂点 C が頂点集合に含まれないケースが紛れている)スクリプト化にあたって一番考えたのって、重複組合せの求め方だった。最初 N×N にして間違っていて、仕切りを置く場所を考えるんだったような、と思い出すのに時間がかかった。そして最終的に補集合ではなく目的のものを直接数えられることがわかって無駄になった。
あと、ちょこざいなやり方だとは思うけど、C と P の大小で場合分けをしたくないなと思って符号を利用した>[(c+1)*(p-c),(p-c)*(c-N),].max。あ、カンマが余分。これは「２頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」が最後まで見抜けなかった恨みである。
こうしたら最後の計算で根(c==0)の場合を例外扱いしないで済む。
P[0] = N # 0 を根にする。N は計算のため。
p (0...N).sum{|c|
p = P[c]
[(c+1)*(p-c),(p-c)*(c-N)].max
}
ワンライナーとかわけがわかりません＞＜
あ、これ？ 「閉路が存在しないならば「連結成分の個数 = 頂点数 - 辺の数」が成り立つ。」 木のどの部分を切り取っても木だろうし、木なら頂点数と辺の数は N 対 N-1 に決まってるので、頂点数と辺の数のずれの大きさがそのまま森を構成する木(連結成分)の数というのは、まあ、言われたらそうかもね、という感じ。
言われなきゃわからないし、なんなら、連結なグラフで頂点数と辺の数の比が N 対 N-1 ならそれは木だというのも、最初からなんだか化かされてるような気がしてる。
最終更新: 2020-07-09T19:18+0900
コンテスト中に解けなかった問題に再挑戦。(C 問題まで11分で終わらせてそこで力尽きていた。そんだけ時間を余らせてなぜ解けない？)
距離を求めるのに頂点の分類が必要だったのだけど、分類して組み合わせを網羅して距離を計算することができなかった。
今回は頂点を２次元座標に配置することを思い付いて、そうすると組み合わせの網羅や距離の計算が if 文ではなくデータを中心に構成できたので、解答の提出にまで至った。
N の上限が 2000 だから N×N(=400万)のループは TLE のおそれがあり、実際に 2 秒制限ギリギリだった。提出一覧を見たところ 100 ms は切れないみたいだが 500 ms くらいは普通に切りたい感じ。
というあたりでもうちょっと。
atcoder.jp/contests/abc16… すべてのiをBFSで最短距離出すところまではすぐ思いついたけど分岐する場所の計算がわからなくて敗北した
BFS とは思いもよらなかった。たぶんグリッドでなくほぼ直線だったからだろう。そういう先入観でプランＢが見えなかった。
期待以上に速くなった！ ２桁ms！
すでに書いた通り頂点を４つにクラス分けして、始点４クラス×終点４クラスの場合に距離 k の頂点ペアがいくつになるかを計算した。計算は定数時間なので全体で k(=1..N-1) に比例した時間。
L[n][k] が主な道具。n 頂点で直線を作るときに距離 k の頂点ペアがいくつあるかを返す。
C[n][k] は n 頂点の円に対応する。頂点X,Yを除外する-4,-2 がアドホック。
k=1 の場合は例外。他と同じ式に組み込めなかった。
300 ms 台の人の十分に速くてシンプルな提出を見た>#14717011。長さ N の二重ループだった。ありうる２通りの距離のうち短い方を採用するだけだった。これをコンテスト時間中に書きたかったね。まあ、あとからでも書けなかったんだけど。
「２頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」ということが最後まで見抜けなかったからなんだけど、それでも、何らかの方法で答えにたどり着きたかった。
たぶん Python のこの提出(#11387294)が自分と似た方針で同じようなコード構成だと思う。難しくてよくわからんけど。
操作を間違えるとスマホが利用できなくなる、極めて危険性の高い機能」っていうけども、普通に考えて「操作を間違えてスマホが使用できなくなる」のは不届きな他人なのであり、何が問題なのか。もちろんどちらの問題が深刻かは利用者の判断であり、自分が何をしているか、他にどういう手段があるかが覚束ない人のために多様な判断材料とともに情報提供をすべきだったのかもしれない。完全に他人事だけど。■別に SIM が使用不可能になっても「
スマホが利用できなくなる」は言い過ぎだろうよ。ケータイネットワークは使えなくてもインターネットもスマホも使える。それこそ無効になった SIM だって代替可能なメディア(媒介物質)に過ぎない(よね？)。スマホを紛失することと比較して特に深刻な事態を引き起こすとは言えない。■「
初期設定の PIN を入力します(これから設定する PIN コードではありません)」という注意書きが完全に想像の上を行っている。そうか、そこに罠がある、それが罠になるのか。■「てくろぐ: SIMカードがロックされてしまったら (SIMへのPINコード設定)」
最終更新: 2020-07-05T23:55+0900
コンテスト全体については順当に、冴えない結果であった。あまり書くことがないので１つだけ。
他が概ね 1000 ms ほどかけているところ、１つだけおよそ半分の 515 ms で済ませている>提出 #14757268。
ループでは他と同じ式を使ってるんだけど、半分に割って足しているところが鮮やか。足し算の背後にある論理がわかりません。
N/2+1 から N までの数は掛ける２をするだけで N を超えてしまうので、その数自身しか数える必要がない、というあたりかな。ループの中の計算が必要ない。
こんな手の込んだことをしていながら提出時刻も早くて、Ruby の中では５番目なんだよね。一方の自分は、C 問題で脳死の愚直手続きスクリプトを書いていた>提出 #14743690。脳死のまま清書>提出 #14788308。ステートメントを減らそうとしてやりすぎた>提出 #14788890
D 問題にも最初は脳死状態で挑んでいた。こういうスクリプト。
でもサンプル３が親切にも N の上限値で、このやり方では時間がかかりすぎることに気付かせてくれた。さもなくばずぼらと拙速の代償として TLE を１個拝領していたことだろう。
D 問題。問題と格子点の関連がさっぱりわからなかったのだけど、ループでシミュレートしてるΣ計算に N の一般式を与えようとしたときに、Σの中に整数除算があるから、反比例のグラフと軸のあいだの格子点の数に興味があるの？ その前に、k*N/k*N/k を約分したり分解したりはできない？
ところで、この縦に足す方法では、半分から先はどうせ1つしかないのにループを回して一つずつ足してしまう。ここを斜めに足せばループは半分で済む。しかしどうせ斜めに足すなら… 左上までしっかり斜めに足す。そうするとループの回数はルートNのオーダーになる。
画像が見えない(scrapbox も CSS を切らないと読めない)。まだ「斜めに足す
」がわからない。√N のオーダーになるとは他所でも読んだが、わからなかった。
k*(N/k)*(N/k) の、N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる(それとΣの区間も変化する)とか、そういう話なんだろうか。いや、どう書いてあるかはざっと読んだんだけど、読んだだけで解れば世話がないわけで……(あとでスクリプトにして確かめよう)。
しかし明らかにもっとすっきり書く方法がありそうなんだよな、っていうかそれはすでに Python スクリプトとして示されてるんだけど、理解できないのです。
自分がやったのはすでに書いた通り、「N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる
」ということを利用して、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 の関係は通分したり約分したりできる関係ではたぶんないんだよね(答えが合わないから)。
図がわかりやすい。オーダーをちょっとずつ改善していく構成が付いて行きやすい。そして最後に見逃せないこれ>「なお、O(N^1/3)の方法もあるらしいです。
」
格子点のやり方がこのオーダーらしい。さっぱり想像がつかない
じゃあね、せっかくリンクを張って紹介してくれた先(「格子点の数え上げの高速化 - 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などを用いて計算することが多く
傾きが既約分数の場合」)
それというのも Python の方には２桁msの提出が１ページ以上もあって、オーダーは変わらないしブレもあるだろうとはいえ、28 ms と 32 ms のスクリプトのあいだには明らかに式の複雑さに差がある。
※ 実行時間昇順で並べたときだけ自分の 32 ms の提出がリストされない。降順だったり提出時刻だったりでソートすれば現れる。消えているときは代わりに他の人の 32 ms の提出が２回リストされている。
32 ms の１つは自分のだが、28 ms は例えばこれ>提出 #14788253。平均タイムからして明らかに速い。
未だ及ばずながらだいぶ迫ったのではないか。
最後に÷４するのにループの中で無駄に×４してるのが気になったので。
これを最適化というのではないか。この問題でしか意味のないループになった。少なくとも自分は式の意味を、途中からは理解していない。
実は最終版の while ループの中身は一番最初の 997 ms の提出とそっくりになっている。戻ってきた。
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 の順で発見される。１対１対応ではない。
関係ない写真を間に入れまくる、内容のないblog特有のフォーマット」「
リテラシー高めのエンジニア向け記事だとマイナスに働く効果のが大きいかなー、と思ってた」■たしかちょっと前に似たようなつぶやきが、それも AtCoder 界隈であった。動画かテキストかという話。自分はこういう派>「わからない。提出 #13147757 (WA)。解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。」 テキストでぱっぱっと要点だけ知りたいし、まだら模様の理解度に合わせて時間を配分したいし、動画はそれができないから時間の無駄だと思ってる。それが言い過ぎだとしても、効率が悪いのはたしか。■過去に何度か書いたけど、自分は画像処理が苦手でアイコンをほとんど識別しないし、現実や画面を通した映像から読み取れることがごく限られているし、テキスト処理に特化している。人間(の集団)が嫌いである種の実写がきついというのがまた別にあるけども。AtCoder の解説動画がどんなものかはまだ確かめたことがないけども。誰々がすごく丁寧な解説をするという評判だけ聞いてるけども。■Web メディアがページを無駄に(※主観です)細かく分割するのも必ずしも広告がらみの理由ではないらしいし、マスにリーチするということは、その過程が見えるということは、とりもなおさずターゲットが自分から離れていくことを意味するのだともはや承知している。逆にターゲットが自分の方に近づいてくるとき、その過程は見えない。まだ自分にリーチしてないからね。だから好き嫌い(※主観)ではあっても善し悪し(※客観)ではないんだろう。■あと「エンジニア」っていってもピンキリで、ピンはごく少数なので……。Web サービスでユーザーが増えると質の平均が下がったと嘆きが聞こえてくるのはあるあるなので。■パソコン通信は知らないインターネット老人会からでした。
最終更新: 2020-07-09T19:28+0900
WA(Wrong Answer)の記憶なんてないまま新鮮な気持ちで挑戦したら普通に解けた。過去の提出を見直してみたらまあ、解答の構成がびっくりするほど瓜二つ。
では二者の分かれ目はどこに？
WA の方はすべての人について一度だけ、その友達リストを処理している。AC した方は深さ優先探索で再帰的に処理している。なぜ再帰が必要か？
ある人 A と B が友達で、また C と D が友達であるとする。この時点で２つの友達グループがある。ここで A と C の両方と友達である E さんを処理するときに、A と C と E を繋ぐだけでは不十分で、すでに A や C とグループを作っていた B と D の所属グループまで更新しなければいけない。これをするためには配列を通り一遍に処理するだけではダメで、友達グループを記録した配列を何度もなめなめするか、再帰的に処理をする必要がある。
今ではこういう処理を Union-Find と呼ぶことを知っているし、グループの大小を管理することで書き換え処理が軽減できることも知っている。検索したらこれは序の口で、まだまだ奥が深いらしい。読んでないよ>「素集合データ構造(Union-Find)」「UnionFindTree に関する知見の諸々 - noshi91のメモ」
インタープリタ型言語は基本的に書けば書くほど実行に時間がかかるものだし、一般化して構造化すれば無駄が生じる。多く書いてそれが速いなら、アルゴリズムが優れていることに他ならない。
ところで、つい先月の新しい提出にすごいのがありますね。「Ruby(2.3)によるすべての提出(実行時間昇順)」
tamura2004 さんの提出 #13758236 (AC / 915 Byte / 291 ms / 12292 KB)
def size(a); -@data[find(a)]; end @data ひとつでグループとサイズの両方を記録している。@data[b] = a によって b グループを a グループに併合している。事前の比較により a グループの方が b グループより小さくないことが保証されている。しかし同時に行っている @data[a] += @data[b] の意味がわかりにくい。これは @data のもう一面、大きさを合計している。@data[a] < 0。負になるのはルートに対応する要素の値で、ルートにぶら下がる要素は 0 以上の値で他の要素をポイントしている。@data 変数ひとつであれもこれも済まそうなんて、なんてケチで欲張りなんだ。
コンピュータで処理するものなのだから、現実的制約は無視できない。集合演算と整数の引き算(+α)のコストの差。十分過ぎて必要のない情報にコストをかけてはいけない。
引き合いに出した ARC097 の D 問題の AC 提出は去年の10月のものだった。３月時点ではそれを糧にできていなかったのだな。
さらに言えば ARC097 の D 問題には AC 提出の前に１つ TLE になった提出があったのだけど(#8121130)、TLE の原因がグループを表現するのに集合を使っていたから。３月の提出が TLE なのと同じ理由。まるで成長していない……(それどころか WA まで)。去年の10月は TLE のままで終わらなかったのが偉くて、30分くらいかけてグループの中で一番小さいインデックスにグループを代表させることにしたらしい。それがどうして３月に生きなかったのか……。
しかし今日の日記を書く過程でさらに省メモリかつ高速なスクリプトへの手がかりを見つけられたのはもっけの幸い。わずか２日での進歩である。
tamura2004 さんの提出を参考に。同じ問題に対する#10479576ではなくて、さっき引き合いに出した#13758236の方。
出力形式も変えたけど、ジャッジがスペース区切りと改行区切りを区別しないらしいのは kotatsugame さんの何かの提出で知った。これって kotatsugame さんの記事なんだけど……「AtCoderで実行時間0msを狙う - Qiita」
「どうしても1ケースだけ1msかかってしまう……せや！テストケース特定したろ！
」「ちょっとくらい……探索サボってもバレへんか
」「進む方向を定めるのに、ベクトル(sin(r),cos(r)) (r=0,...,99)を使っています。根拠はないです。
」
「根拠はないです」やあらへんでまったく。ゴルファーでもあるこんな人がジャッジの細かい仕様を知らんはずないんだよなあ。
それに問題を読み直したら「答えを空白区切りで順に出力せよ
」と書いてあって、たしかにスペース区切りの出力例は出力形式の一例に過ぎないといえる。
最終更新: 2020-09-01T19:43+0900
コンテスト本番では問題文を読むところまでたどり着けなかったし、仮に読んでいても TLE は免れなかったろう。
しかし今や蟻本でセグメントツリーについて読んだので何の問題もない。適切なデータ構造を扱えますか、というだけの問題である。それと時間内に実装できますか、という……(BITを使おうとしてた時間を含めて３時間くらいいじくってた)。
内部データサイズが単なる 2N に見えるのが不思議。添字の扱い方はヒープに見えるけど、２の冪乗じゃないと階層が崩れて右が左に左が右になりそうなものだ。さっぱりわからん。
蟻本の著者の一人のスライドを見つけた。
実際には，この実装なら n が 2 の累乗でな くても動作する
値の更新の方はこのままではダメで，同様の 手法で再帰関数で書けば OK
- ただし，配列サイズは MAX_N * 2 - 1 では 足りない – MAX_N * 4 取れば十分
まだわかりません。それに Python による fold 関数とスライドにある query 関数は引数の数が全然違うんだよね。片方は再帰ですらないし。
一方の提出ご本人による記事である。「いわゆる非再帰実装
」「N = 2^n を仮定しない
」 これこれ。ありがたやありがたや。