脳log[20200726]

2020年07月26日 (日) [AtCoder] 昨日は ABC 級の「M-SOLUTIONS プロコンオープン 2020」があった。パフォーマンス 1683 でレートが 83 上がって Highest を更新したが、あまり喜ばしいことではない。というのも、昨日の自分が一皮むけた結果というわけでは全然なく、いつも通りの不甲斐なさを味わっていたからだ。では何が違ったか。コンテストの(自分より優れた)他の参加者が自分同様に E 問題、F 問題が解けなかった(だから提出の早さを評価する上限が高くなった)というだけのことだ(たぶん)。臨時ボーナスをもらったみたいなもので、自分は何も変わっていない。■E 問題。手を抜くと WA になり、総当たりすると TLE になる。制限時間がいつもの２秒でなく３秒であり、N の上限が 15 と相当に控えめであることから、想定解法の複雑度はかなり高いと考えられる。Ruby で工夫のない総当たりをすると N=10 と 11 のあいだに TLE の壁がある。2^20(=約100万) と 2^22(=約400万) の違い。N=15 が遠い。解説はまだ見たくない。しかしこれがヒントか。@chokudai「E、自分だったら4^Nと3^N区別したくないからめちゃゆるい制約で出すんだけど、Writerが調整めちゃ頑張ってた。」 いやでも 3^15(=約1400万) は手の抜きどころがないと Ruby では無理だけどね。■(お風呂にて) ポイントごとに縦・横・無の三択の総当たりということなのか。そうなのか。ポイントの数と同じだけの直線を選べば確実に S が 0 になることを踏まえれば、あるポイントに縦か横の直線を引いたあとは他のポイントに注意を移していいわけだ。■TLE の壁が N=12 と 13 のあいだに移動した雰囲気。3^12(=約53万) と 3^13(=約160万) の違い。■結局 C++ で書いて TLE を回避しても MLE と WA になるという。ただの総当たりなのにな。WA になるテストケースがないとデバッグが捗らないよ。■■■@chokudai「作問窓眺めてみたら、「大きいと書かれてますが同じの場合はどうなりますか？」みたいな質問が来るので、「真に」をつけてみたけど、今度は「真に大きいとはどういうことですか？」って質問が来てる、みたいな感じの流れだった twitter.com/yamasaKit_/sta…」 問題文を読んでいてちょっと引っかかった表現だった。「真に」が自分の知らない専門用語であり、わざわざ書くからには明確に画された無視できない定義があるのかと疑った。自分は「同じかより大きい」という表現をある時点から知っており、そこから「より大きい(more than)」がイコールを含まないことを覚えていった。「真に」というのが謎用語だったのなら、ある語(「より大きい」)の定義を他の語(「真に大きい」)に丸投げしているだけであり、そういうこと(循環定義)は国語辞典でときどきあるみたいだけど、説明しようという親切が伝わらないものになっていると思う。■■■@2020-07-29 E 問題。綱引きにおいて 1×2 と 2×1 と (1×1)+(1×1) の中には仲間外れがあるんだけどどれも一緒くたにしていた。最初によく考えて当然の前提としていたところにこんな見落としがあっちゃあ答えにはたどりつかねーよ。