最終更新: 2020-10-29T15:09+0900
解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。(追記) 13日の現在はPDFもあるみたい。
これを読んでも間違っているとされている定義のどこに問題があるのかわからんのだよね。果たしてそれで解けるものか。>「競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話 - notブログ」
正規表現の ? を * に変えたことで、AC は増えたけどまだ WA がある。
こういう生成スクリプトでテストした結果、最初の提出で使用した正規表現パターンに問題が見つかった。
def puts s
re = /(?<p>\(\g<p>?\))/ # バグあり。提出 #13147757 より。
re = /(?<p>\(\g<p>*\))/ # 意図通り。提出 #13156522 より。
t = s.gsub(re,'')
print "#{t.empty?}:\t#{s}\t#{t}\n"
end
L,R = '('*5,')'*5
10.times{
puts L+((L+R).chars.shuffle.join(''))+R
}
LR = '()'
10.times{
puts 10.times.inject(''){|s,| s.insert(rand(s.size+1),LR) }
}
そうするともう、提出したスクリプトは完全に自分の意図通りに動作しているはずなんだけど、WA がある。書き間違いではなく、考え違いがある。
)( 型の s を連結する順番によって結果が変わる。)))( と )((( の２つの s があるとき、連結のしかたによって )))((( が残る場合と )( が残る場合に分かれる。)( を残した方が 'Yes' と答えられる確率が高くなる。
)( 型の文字列が１つだけのときに必ず No と答えてしまいそう。今現在 Ruby で一番速い提出は 498 ms だ。>すべての提出 - AtCoder Beginner Contest 167
再帰ありの正規表現(※矛盾した表現)を使ってる時点で勝ち目はない。左括弧の数が負になれないのに気をつけながら、左括弧と右括弧を対消滅させながら、左括弧と右括弧がいくつ残るかを数えればいいんだろうけども。
しかたない、省メモリを売りにしていこう。>すべての提出 - AtCoder Beginner Contest 167
ソートを必要としてないあたりで(※)ちょっとは有利を得てもよさそうなもんなんだけど、トップの提出はソート対象を )( 型に限るなどしてる。※ループ内で２要素のソートもあかんか？
( 型の文字列を最優先に、)( 型のうち ( 優位のものを優先的に、最後に ) 型を、という感じで連結していくのがストレートな解答らしい。
３つの型の文字列を統一的にソートすることもできるし、)( 型だけソートしてもいい。
自分はどれもソートしてないんだけど、)( 型の中から１番目と２番目に条件のいい文字列をピックアップするための比較演算()( 型の文字列１つにつき１～２回)が重くてソートした方が速い。
(ゴルフ勢を除けば)わりと短くてそこそこ省メモリで今のところ Ruby で一番速い。すべては正規表現エンジンとそれを使う gsub のちから。
やってる内容は最初の AC と変わらない。入力をがばっとひとまとめに処理するようにしたのと、最小２要素を取り出すのに一度全体を配列に蓄えてから min メソッドを使うようにしただけ。
この記事を書かれた方（ギフテッドの人）には、もしかして、自分の話を相手に理解してもらえなかった経験はあっても、相手の話が自分には理解できなかった経験が無かったりするんだろうか？」■quora に書いた人はたしかに「
でも実際に起きていることは、上のような「なんで何回も説明しないとだめなの」「なんで伝わってくれないの」というようなコミュニケーション不全による高IQ側の孤独さです。なぜ伝わらないのか、何がいけないのかと頭を抱えて涙している、そういうシーンです。」と、わかっている立場から書いているけど、同時に「
そもそも自分の日本語が間違っているかもしれない、自分のアイディアが頓珍漢なものかもしれないという恐怖感」が訪れるとも書いているし、また、「
馬鹿なことを言っているのは自分じゃないのか、人と満足に交われないのは自分の性格が悪いのではないか、と悩み苦しみ」と、弱い立場からも書いている。孤独な人間は自分の正しさを確かめるために他者を利用できない。自分で自分が信じられなくなったら狂人へまっさかさまだ。「一般人」に囲まれたときそういう恐怖の内にある。だから「相手の話が自分には理解できなかった経験が無かったりする」というのは想定される像から外れると思うのだ。quora の方で「
高慢ちきな高IQが「お前たち低能とは話が合わない」と吐き捨てるように告げるシーン」は実像に合わないと否定されているのだが、そのイメージに近づきすぎていやしないかと思うのだ。■『心を読みすぎる 心の理論を支えるワーキングメモリの心理学』(前原 由喜夫) という本を読んだ。「心を読みすぎる」というワードでは伝わらないと思うんだけど、この言葉に込められた意味は、他人の考えが自分にはよくわかっている、と考えているときこそ他人が見えていない、見えていないから(自己を投影しているだけだから)そう思えてしまう、というようなことだ。「ワーキングメモリ」というワードが quora の記事と共通している。quora の記事を書いた人は明らかに単純バカではないから、他人のことを理解しているなどと安直に思い込んで安心することはできないのではないか。だから確かめたいし歩み寄る努力をするんだけど、「一般人」の側があまりにも簡単に、「気持ち悪い」という言葉や「何言ってるの……？」という不審な目でもって、「意味不明な話をしている気味の悪いやつを排斥」してしまうのではないか。■伝える努力をしたくても、理解しよう受け止めようという姿勢を「一般人」の側が持てなければコミュニケーションは成立しない。「
「やばい、相手の言ってることがまるで自分には理解できない。どんなに説明されてもチンプンカンプンだ」という感覚」。やばいと感じているうちは大丈夫。「
「相手の言ってる事がまるで分からない」時、僕は、すごく惨めな気分になるし、相手に対する申し訳なさや負い目を感じます。」 この気持ちがあるなら大丈夫。でも一方が諦めて排斥して開き直ったら、どうしようもない。そういうことを quora の記事は書いているのではないか。■だから quora の記事がきっかけにすぎなかったとしても、十分に踏まえられていない感じが気になった。
最終更新: 2020-05-29T19:43+0900
数弱さんには厳しい回だった。E 問題は読む時間さえなかったので今日の日記は D 問題。次の整数式を考察するだけ。
x*A/B - x/B*A
A を掛けてから B で整数除算するか、B で整数除算してから A を掛けるかという違いで生じる値の差について。その最大。
違います。B を周期として第一項と第二項が一致します。A がその周期に与える影響はよくわかりません。
ちなみに B の上限は 10^{12} のため周期全体をテストすることはできません。>提出 #12633357
たぶんその通り。だけど説明を端折った N との関係がわかんなかったのと、A と B の因数によって第一項と第二項で周期 B の位相がずれていくんじゃないかという気がしたので探索した。>提出 #12640433。でも錯覚。位相がずれるなら「B を周期として第一項と第二項が一致します」が嘘じゃんねえ。
Ruby で提出している他の人は、提出の早さも実行速度も優秀だった。>すべての提出 - AtCoder Beginner Contest 165
実は B 問題で15分近く詰まっていた。瞬殺できないとあせる。最初は(もはやうろ覚えの) log を使って計算していた。
X = gets.to_i p ((Math.log(X) - Math.log(100)) / (Math.log(101) - Math.log(100))).ceil
でも大まかにしか数字が一致しない。同じかちょっと小さい数字になる。俺が log を忘れているか浮動小数点数の誤差か(近い数字の引き算とか良くないのでは？)これの影響じゃないかと>「(複利、小数点以下切り捨て)
」。複利の計算をするごとに切り捨てなければいけないのでは？
B 問題なので手続き的に解いても TLE にならないのはわかっていた>提出 #12601266
実は C 問題でも30分近く詰まっていた。A 数列の総当たりでいこうと決めるまでに制約条件を総当たりしようとしていて、他の制約にまったく制約されない孤立した制約条件の扱いをうだうだ考えていた。
再帰をループにするとかの効率を考えずにちゃっちゃと書いただけなので、提出へのリンクはなし。
上手い人のゲームプレイ動画と AtCoder の解説 PDF のあいだの共通点。多様性のなさ。へたくその動画の方がバラエティに富んでいて見ていて面白くさえある。間違え方というのは本当に千差万別で、ありとあらゆる機会を逃さずに、そう来るかと予想もできない脱線をする。たったひとつのゴールに向かう限られたルートに収斂していくということがない。
当人にとっては面白くもなんともないので、B 問題、C 問題に詰まらないような世界線に乗っていきたい。
chokudai(高橋 直大)🌸🍆 Verified Account @chokudai
とはいえ、高度な問題を解く時に、「floorが出てきたら整数部と小数部に分離して式変形！」って結構大切な考え方なので、Dみたいなのを出さないと、後半問題で突然そういう数学力が応用状態で問われることになるので、そのあたりの塩梅がむずかしいよね。
x が固定小数点数で小数部が５桁なら、x - x/100000*100000 が小数部分になる。……という話ではない？ D 問題を解くときの話？
以前にもはっとさせられたことがあった。
kを使った場合のコストは、k-1以下のすべてを使ったコストより高い
これって要は 100000 > 11111 (２進数) と同じことなんだけど、自分のような人間は「この一連の操作のコストは（書き換えた要素の数によらず）2^k である」という問題文を読んだだけではたどり着けなくて、上のように事実として示されて２進数で考えてみて初めて了解できることだったりする。
「一を聞いて十を知る(20200508)」ってこういうことだと思う。賢い人は「いやそれって同じことだから一の内に入るのでは？」と思うかもしれないけど、全然違うのである。
そして自分が AGC022C 700点問題 にまるで歯が立たない理由には、列挙された要素の数とそれらを煮詰める段階の深さに関係があると思ってる。「理解が及ぶ広さ、深さ、早さに優れ(20200508)」という風に書いたけども、そうでない自分は頭の中で抱えきれないし、整理して外に出して部分ごとに解決することもできない。
アストロノーカやテラリアですでに知ってるんだけど、ツリー状にねずみ算式に倍々に増えていく要求リソースの全体を把握すること、並列に進行する精製過程をストールさせないように需給を絶えず調整すること、このサプライチェーンの階層がある程度以上になると(たぶん３くらい)完全にお手上げになってしまう。そういう能力がない。
「たぶん３くらい
」 深さが３、二分木なら葉の数８までしか脳内で扱えないんです。
ちょっと検索したら「銀の格言」としてこんなのが列挙されてる。
つまりはこういうことなんでしょう？
chokudai(高橋 直大)🌸🍆 Verified Account @chokudai
「この問題だったらこうするだろ」って感じに無意識にやってることってめちゃめちゃ多くて、その「無意識」を言語化して列挙するだけでもめちゃめちゃ有効だと思うのよねえ。
chokudai(高橋 直大)🌸🍆 Verified Account @chokudai
「chokudaiのアルゴリズム格言1000」とか作って、こういうのをひたすら列挙しまくると、格言の組み合わせだけで良い感じに解ける問題がたくさんできそうだな、と思っていて、アルゴリズム名とは別レイヤーで浸透させたいな、ってちょっと思ってる。
「解説なんかだと、正しいルート以外はすっ飛ばされちゃう」というのがまさしく今日書いたことで(20200502p01.04)、解説PDFよりも「競技プログラミングの強みと「典型力」について - chokudaiのブログ」という思考の跡が見えるブログ記事の方が自分には有用となる理由。アルゴリズム格言に期待する理由。
最終更新: 2020-06-15T20:02+0900
日付のあたりに書いた通り解説PDFを読んで実装した。だけどあれ全然答えじゃないね。Chokudai さんのブログで以前読んだような、ちょっとひねってあるのをいかにして典型問題に落とし込むかというタイプの問題だったらしい。ある意味そこまで含めて典型では。でも一度も実装したことのないパターンだから「(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。
」とだけ書かれても、～を状態とするってどういうことですか？
Wikipedia の「ダイクストラ法」を読みながら雰囲気でPDFに書いてあった方針で実装しようとした。一応答えは出たがサンプル入力ですら一瞬の間を感じさせる激遅スクリプト。
N 個の頂点と銀貨の枚数を組み合わせて状態にするといっても、訪れなければいけない地点は依然として N 個のままなわけで、そのあたりの状態を集約する手つきが具体化できなかった。最終的に提出したスクリプトで「すべての地点を一度でも訪れた時点で完了」としたところとか、「銭なしの再訪に用なし」とコメントしたあたりがそうだと思うんだけど。
苦しんで何度か書き直すうちに原型を失いつつもすっきり書けて、プロファイルをとりながらの実行もすっきりだったから「どうだ！」と提出したら、AC の中１つだけが TLE で脱力。これ以上は無理ですよ。
この段階で他の人の提出を見た>「すべての提出 - AtCoder Beginner Contest 164」。
Ruby での全提出は１ページに収まるほどで、AC していたのは２人だけ。TLE 仲間の提出を覗いてみれば、自分が TLE になった入力(とサンプル)だけ AC していたりして、line_2.txt が何と癖の強い入力であることか。
ダイクストラ法に立ち返らないといけないかと思っていたが、diff をとらないと判らないレベルのチューニングでなんとかなった。不思議。
M.times.map の .map がいらない。すっごく読みやすいんだよなあ。何をやっているのか手に取るようにわかる(笑)。配列総なめが嫌だからって冗長なカウンター変数を用意するところまで。
自分に欠けていた工夫が２つあって、
特に２番目は効果が大きいんじゃないかなあ。キューへの出し入れがボトルネックだから、エンキューをひとつ節約するごとにそこから波及する複数のエンキューが節約されるのは大きい。
それはそれとして、Python は AC だけに限っても５ページの提出があるのがうらやましい。傾向として判で押したように似たような提出が多くはあるが。理由のひとつはヒープ(データ構造)とかダイクストラ法とか、名前のついたアルゴリズムが簡単に利用できるところにある。
読めない記述がある。この行
(v = V[n]&.&SM) ? (next if v>=s || v>2500) : R << [n,t]
演算子(に見えるがメソッド)をドット記法で呼び出せる(それが結合規則を変えるのでゴルフに使える)というのは読んだことがあって、たとえば 1&3 と 1.&(3) は同じ意味になる。でも &.& をどう解釈すればよいか。SM はただの数値変数だからブロック引数化の & ではないと思う。
他にもアロー記法だとか、暗黙のブロック変数(_1, _2 とか)だとか、Ruby 2.7 を読むには知識が足りない。ローカルにインストールしている Ruby 2.5 ではまだ使えない記法だったりする。まだ gem コマンドを一度も使ったことがないから、デフォルト添付ライブラリ(prime とか)の gem 化は歓迎できない？。
ブロック変数には悩ましいところがあって、.map(&f) とか .map(&:to_i) とか書けるときには積極的に書いていきたいんだけど、.to_i ではなく .to_i(2) を適用したくなると途端に .map{|_|_.to_i(2)} と書かなければいけなくなる。.to_i に 2 (と self)を予め束縛した関数がサッと(記述コストと実行コストなしに)利用できるといいんだけど、なかなかそうもいかないらしく、とりあえず .map{_1.to_i(2)} と書けますよ、ということ。たぶん。まだ試したことない。
- 引数の評価が行なわれない
- メソッド呼び出しが行われない
- nil を返す
&.& が何だったかと言えば、nil テストを含んだ & 演算だったと。Swift とか C# にあるやつじゃない？ どっちも使わんしよう知らんけど。
51 ms 縮まったけど本質的な改善ではないと思う(配列４とか比較が雑で適応が限られるし、ない方がいいかも)。シンプルさも失われていいことない。しかも Python (140 ms) に負けてる！ Ruby のバージョンが 2.3 から 2.7 になって、実行前のオーバーヘッドが 40 ms ほど大きくなったと思うんだよなあ(それでも勝ちたい。ユーザー数で負けても質で勝ちたい)。
嬉しい！ 自分で解釈して手を動かして理解してる！ 立派！ 自分で好き勝手書くより他人の考えをトレースする方が難しいものよ。
タイムが縮んでるのはホットスポットである PQ#up_heap (PriorityQueue#update_heap_to_up) で配列アクセスを減らしてるからなんだろうか。キューが長くなるほど効果があると思う。
あと自分は意味まとまりのある変数群を一行で定義するために多重代入を多用するんだけど、実は字数が減るわけではないし、多重代入式に対応する配列値が作り捨てられているとしたら、もったいないことをしてる。
地味に変数の定義位置をずらして無駄な計算を減らしたりもしてる。自分は変数の定義をひとつにしたいがために効果のない値([0,0] とか)を使用して効果のない加算を実行してたりするんだけど、贅沢ではある。関連>20181029。
(自分の提出だよ)
z, y = ２[v]+a, ３[v]+a # z < y if z < s c, d = s < y ? X[v][s-a,３[v]] : [0,0]
X[v] が返す関数が受け取る引数２つ(s-a と ３[v])はその差だけに意味があるから、両方に a を足して、X[v][s,y] とすると引き算１つと配列アクセス１つが省略できる。そもそもが引数が２つある冗長性から生じた無駄であるな。
こういう楽しみがあるのはスクリプトならではなんだよなあ。C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。そこに性能を犠牲にせずに読みやすい表記を追求する余地があるとも見られるんだけど。
もう一度asmコードをよく読むと不要なはずの配列の初期化が走ってる模様. デフォルトcstrは空のはずなんだけどと自分のコードを見直すと、FpDblクラスだけ配列の初期化が入っていた.
うっかりいれちゃっていた模様. 削除するとgcc-7.5で13%高速化. おおこいつのせいだったのか. それでもclang-8より4%ほど遅いけど気がすっきりした. でも配列の初期化で1割変わるというのは(clangは速いだけに)何か変なことしてるのかな.
プログラマに指示されたらコンパイラは無視できない(こともある？ clang の場合をどう解釈する？)。結果に影響しない表面上はささいに見える違いが思わぬペナルティを生むことも。
プライオリティキューの実装が違うだけで、メインループは共通して richvote さんのオリジナル。
richvote さんの提出は、自分が最初唯一の TLE を食らった line_2.txt という入力が際立って他のケースより速いため、明らかに異なる部分に着目して探索の優先順位を決めている。
それはさておいて、俺の目には２つのプライオリティキュー実装に違いがあるとは見えないんだけど、俺の書き方の方が遅いという傾向が間違いなくあるようだ。
loop{} と書くより while 0; end と書く方が速いというように、気をつけておくと得する書き方がまだあるみたい。だけどわからん。
require 'benchmark'
N = 10_000_000
Benchmark.bm{|x|
x.report('多重'){ N.times{ a,b,c = 1,2,3 } }
x.report('代入'){ N.times{ a=1;b=2;c=3 } }
}
これを Ruby 2.5 で実行してみた。
> ruby25 a.rb
user system total real
多重 1.591000 0.000000 1.591000 ( 1.585992)
代入 0.967000 0.000000 0.967000 ( 0.969697)
多重代入遅いなあ。(bm メソッドを bmbm に変更してリハーサルを行っても同じ結果)
あと最近驚いて、確かめてみたら Ruby 1.8 の昔から一貫して同じ挙動だったんだけど、多重代入の評価順って、単純に右辺から左辺とか、カンマで区切られた左から右ではないみたい。次のスクリプトの実行結果に驚いた。
i, a = 0, [0,1,2] # 準備
i, a[i] = 2, i # どうなる？
puts "i=#{i}; a=#{a.inspect}" #=> i=2; a=[0, 1, 0]
最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな？ 右辺の一時記憶が必要？
多重代入は遅くて時々評価順が難しい、というのが現在の評価。
？ 2.6 でデフォルト gem 化というのを読んだんだけど、普通に require 'prime' できる。gem 化されなかったのか、gem 化について勘違いしているのか。