/ 最近 .rdf 追記 設定 本棚

脳log[2021-10-14~]



2021年10月14日 (木) [AtCoder] 精進。ABC160-F「Distributing Integers」(ギリギリ黄 diff)。最近よく見る全方位木 DP。20210928p01.0120211010p01.06。ノード間の式は ABC217-F「Make Pair」に提出したものと同じ(#25683515)。各ノードが自身を含めて A 個の子孫ノードを塗る方法(順番列)を B 通り持っているとき、2つの子ノード以下を塗る方法は B1×B2×(A1+A2 個から A1 個を選ぶ組み合わせ)で求まる。提出 #26559753 (AC / 1028 Byte / 1548 ms)。これで黄 diff の AC は9個目。かなり貴重。■■■全方位木 DP と言えば第八回 PAST の H 問題「最短経路」。制約が N≦3000 だから全ペア 900 万通りの全探索が想定解法かなーと想像したんだけど、Ruby にはやや厳しく見える数字。最近覚えた全方位木 DP で>提出 #26574539 (AC / 72 ms)。子ノードのマージ部分が全方位木 DP 問題唯一のアイデンティティ。各ノードに子孫ノードへの距離一覧をハッシュ表で持たせた。あとは全要素更新を避けるためのオフセット値を表とは別に持たせたりマージテクなどの時間節約術。ところで、提出した解法を全方位~と呼んでいいのかはよくわからない。全ノードを起点にした距離を調べてはいるんだけど、距離って指向性がないので頂点ペアを片方向しか調べなくていいわけなので、ただの木 DP と同じように根への1パスで処理が終わっている。■BFS で全点間距離を調べる方法はやっぱり厳しかった。ゴルフしながら1秒前後で通してる提出が多数あるからそうでもないのかなって思ってたけど、実際厳しかった。あの短いスクリプトのどこにどんなアルゴリズムがあるというのか。ともあれ最終的には BFS でも通った>提出 #26823765 (AC / 814 ms)。どういう時短術を使ったか。X を超える距離はすべて X 以上という扱いにしてそれより遠くの頂点は調べなかった。その場合でも最内ループでチェックをすると TLE がひどいので(#26823520 の 13 行目)、その1つ外でチェックをした(AC コードの 11 行目) (よく考えると TLE がひどいのは距離表の更新がスキップされてるからで、X を超えていてスキップするのはキューへの追加だけにすべきだった)。最も効いたのは、すでに距離一覧を調べてある隣接ノードの結果を流用したこと。そうすると、開始点から出る辺のうちの1本から先にあるノードは距離を調べずに済ませられる。そのために距離表はオフセット値とセットにして初めて実際の距離を表す。この点は全方位木 DP でのやり方と一緒。くらべて不利な点は、距離一覧ではなく具体的な頂点とのあいだの距離を一覧して持っていて等距離にある2点を同一視できていないので扱う数字が多いことと、結果の流用が辺の1本に対してしかできていないこと。これらの差で全方位木 DP に負ける。辺に重みがあるんだから BFS ではなくダイクストラ法を使うべきだというのはあるかも。実装も定数倍も重くて気が進まないわけなんだけど。■同じアイディアでちょっと前の ABC で制約が厳しくて想定解法のワーシャルフロイド法が通らなかった問題が通せないかな。


2021年10月13日 (水) [AtCoder] 精進。ARC089-D「Checker」(青 diff)。大きさが 2K×2K で黒白2マスずつの最小市松模様に 2N 個の点をプロットしておいて、K×K の枠内に最大でいくつの点が含まれるかを二次元累積和で求めるのだと思った。概ね正しかったのだけど、二次元累積和のサイズは 2K×2K ではなくて 4K×4K が必要らしかった。わからないが言われたように修正してみる。提出 #26544471 (TLE×8)。定数倍がたいへん厳しい。提出 #26544665 (AC / 956 ms)。元データが 2K×2K なのだから愚直にデータを展開せずとも計算で仮想的に 4K×4K を存在させられる。ところでこの人の提出>#2789430。すごく短いのと、累積和のサイズが 2K×2K だ。c と N-c を同時に答えの候補にしている部分がよくわからない。わからなくはないか。黒く塗るか白く塗るかだ。そうすると 4K×4K が必要というのも、K×K の枠内が■□■□になる場合と□■□■になる場合を網羅するためだったか。じゃあ 3K×3K でも? そもそもさっきの仮想累積和の提出(#26544665)が、3K×3K の累積和上を K×K の枠が移動する 2K×2K 通りの探索になってたっぽい。わかってやってるんじゃあないんだよなあ。


2021年10月12日 (火) [AtCoder] 精進。ARC088-D「Wide Flip」(ギリギリ青 diff)。まずは問題を理解する。「操作には2つの端点がある」「端点は 0 と 1 の境界に揃えたい(←この表現)。そうすれば操作のたびに端点にあった境界が消える。さもなければ新たな境界が生まれるが、それは嬉しくない(←この表現)」「一方の端点を文字列の先頭または末尾に固定して手近な境界から貪欲に消していけばゴールに至る」「文字列の真ん中より手前側にある境界は相方に任せて良い」。提出 #26527889。■一番最初に思いついたゴールに至る確実な答えは、最も短い 111...列(000...列)の長さを操作の最小幅にすることだった。これをどこまで伸ばすことができるか。文字列の端っこまで伸ばしたとき答えが見える。


2021年10月11日 (月) ベテランの「適当でいいよ」は真に受けちゃいけない→ベテランと新人の『適当』にはこれくらいの違いがある - Togetter」■適当に正反対の意味があるのって、判断の基準が主観にあることで結果がピンキリになり、ピンの結果とキリの結果がどちらも適当にやった結果扱いされるせいで起こる現象だと思ってる。なかなかに味わい深い言葉。適当でいいという指示こそがテキトーであり適当ではなかったのであり、言葉からしっぺ返しを食らっている、的な。本当にテキトーでいいなら指示が必要な場面ではなかったはずだし、期待する結果も期待外れの結果も存在し得ないのが道理。「適当でいいよ」ではなくて「もうそれくらいでいいよ」なら許されたのかな。


2021年10月10日 (日)

最終更新: 2021-11-15T21:43+0900

[AtCoder] エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222)

大反省回。未だに ABC で ABC の3完敗退を繰り返していることに驚きを隠せない。今回がそうだしついこの前の ABC219 もそうだった>20210918。ついでに言うと3年以上前の第2回参加回もそうだった。まるで成長していない……。戒めとして普段はとばす A 問題から振り返る。

 A - Four Digits

20 年前の自分だったら N の常用対数から N の桁数を求めてくっつける 0 の数を決定していた。

だけどとある WSH 関連の掲示板で、十分な数の 0 をくっつけてから必要な文字数だけ切り出す方法を知った。

 提出 #26434564 (AC / 25 Byte)

他の人の提出を見ると printf かそれに類するメソッドを使うものが多かった。Ruby で最初に提出した人は rjust を使っていた。目的にぴったりのメソッド(rjust)がある以上、それを使うのが最善だった。

 常用対数から桁数

こういうこと。

L = lambda{|n| Math.log10 n } # 正整数 n の常用対数
D = lambda{|n| L[n].floor+1 } # 正整数 n の桁数(10進表記)

p [D[99],L[99]]   #=> [2, 1.99563519459755]
p [D[100],L[100]] #=> [3, 2.0]
p [D[101],L[101]] #=> [3, 2.0043213737826426]

学校で対数を習っても理解が伴わないと計算問題はできてもこういう風に実用できなかったりする。Project Euler の 62 問目を二重ループで解いたりもする>20110308p01.02

実はまだよく分かっていないのは自然対数の底 e。なんだかこれを底にすることで累乗が掛け算になったり曲線が直線になったりして性質を変えずに扱いやすくなったりするらしいんだけど、そういうのは(文系学部に分類されるらしいことを少し前に知って驚愕した)経済学部の人に任せておきたい。

 B - Failing Grade

コメントのしようがない。スクリプトを読んで。

 提出 #26437560 (AC / 63 Byte)

 C - Swiss-System Tournament

制約が小さいので愚直にシミュレーションをすれば良い。

解答を作成するのに 20 分かけたのが良くなかった。出力フォーマットを勘違いしていて、求められているのが順位で並べた人番号だったのに、人番号順に順位を表示しようとして余計な手間をかけ、余計な手間を実装するのにもやけに手間取ってしまった。

 提出 #26449288 (AC)

 D - Between Two Arrays

解けなかった。シンプルな DP。直前の項がとった値ごとに場合の数が記録してあれば、現在の項において取り得る値と場合の数が数えられる。それがわかっていて解けなかった。

  1. 提出 #26458829 (WA×15)
  2. 提出 #26459583 (WA×15)
  3. 提出 #26461168 (WA×15)
  4. 提出 #26493159 (WA×15) 一夜明けて今日も WA

もうね、「なんでなん?」という感想しかない。これが違うなら正解が正解ではないと言い張ることしかできない。

 提出 #26493304 (AC) Range を等価な Range で置き換えました。

制約の下限が 0 なのは知っていた。知っていたしそのせいで Range の終端が -1 になることがあるのもわかっていたが、終端が始端よりも前にある「空の Range」で切り出した部分配列が、「空の配列」ではないことがあるだなんて想像だにしなかった。これは Ruby の罠である。こういうことだ。

range1 = 0..-1 # これで WA
range2 = 0...0 # これで AC
p range1.size #=> 0
p range2.size #=> 0

array = *0..9
p array[range1].size #=> 10
p array[range2].size #=> 0

配列の切り出しにおいて Range は単なる添字のペア [0,-1] として扱われている。Range としてのアイデンティティを奪われている。この仕様を知らなかったわけではない。ただ、認めがたい仕様なので自分では絶対に使わない仕様なのであり、意識の外だった。

 E - Red and Blue Tree

D 問題を諦めたのに E 問題もコンテスト中の提出は叶わなかった。

やることははっきりしている。できるかどうかは別としてやるだけの問題。

木において辺とは頂点集合を左右に分けるもの」だと前回の ABC に関連して書いたばかり。ある辺について注目したとき、A_i と A_{i+1} が異なる集合に属していれば A_i から A_{i+1} への移動に際してこの辺を通るのでカウント +1。

A_1 から A_2,..., A_m へと移動するとき辺ごとに何回通るかが数えられたら、今度は R−B=K を満たすような塗り方(辺の選び方)を数える。一度も通らない辺は青でも赤でもどっちでもいいので除外してあとで掛け合わせる。

 提出 #26470241 (WA×4 / TLE×3 / AC×37) 昨晩の提出

原因は想像だけど、頂点集合の管理に 1000 ビットのビットフラグ×1000 を使って TLE。後半で謎の DP をして WA。

 提出 #26494106 (AC / 1050 Byte / 183 ms)

頂点集合の管理に UnionFind を使うことを思い出した。後半の DP はシンプルになって、辺を赤く塗った場合と塗らなかった場合を一緒くたにハッシュ表に詰め込むだけ。

1050 Byte は書き過ぎかなと思ったけど、他の Ruby での提出も軒並み 1001 Byte, 2162 Byte, 1019 Byte, 1776 Byte だったから別に突出してはいなかった。

 F - Expensive Expense

前々回の ABC で見たのでこれを全方位木 DP と呼ぶことを知っている。そのときの経験でとりあえず根をとっかかりにすればいいことも知っている>20210928p01.01。根っこの特殊性は親がないことで、(子から親へ処理を積み上げているにも関わらず)親を参照しなければ求められない答えも、根に限れば求まる。そうすれば根を親に持つ子の答えも求まる。以下同様。

木 DP は処理の流れさえできあがれば、葉という一番単純で考えやすいところから差分で処理を積み上げていくと答えになるのでやりやすい。差分の部分の式が難しいことがあるし(20210909)、子のマージが難しいこともあるけど。

 提出 #26495540 (RE×5)

順調にジャッジが進んで行っていたのに最後の最後で次の一群のテストケースに阻まれた(06_n_eq_2_00.txt, 06_n_eq_2_01.txt, 06_n_eq_2_02.txt, 06_n_eq_2_03.txt, 06_n_eq_2_04.txt)。AC は近い。あそこが nil になりそうだなーと疑っている部分はある。

 提出 #26495783 (AC / 602 Byte / 1310 ms)

ABC が 12 時間のコンテストなら ABCDEF の6完も不可能ではない!(慰めはいらねーよ)


ゴルファー以外では Ruby で唯一の AC だった tinsep19 さんの提出 #26477920 を読んだ。

どうやら参照すべき日記を間違えていた。先月の 28 日(20210928p01.01)ではなくて、今月の 4 日(20211004p01)を参照すべきだった。全方位木 DP ではなく木の直径を解法とすべきだった。そっちの方が簡潔になるから。

関連問題である ARC022-C「ロミオとジュリエット」のスライドに2通りの解法が書いてあったらしいのをある参加者のブログで読んでいたが、わざわざややこしそうな全方位木 DP で木の直径を求める方法を知りたいとは思わなかったのだった。

知らずに実装していたし、知っていたのに(理解が浅くて)簡潔な手法を選べなかった。

振り返れば E,F がやるだけの問題だったこと、全方位木 DP、木の直径、どれも前回と前々回の ABC を彷彿させるものだった。どちらも復習はばっちりだった。その結果が3完とは泣かせる。


 提出 #26528881 (AC / 587 Byte / 1032 ms)

DFS 2回で直径を求めるバージョン。全方位木 DP バージョンと比べて、思ったより短くはならなかったけど速くはある。何より各ステップが単純でバグらせにくいと思う。

この単純さは、旅費が最大になる目的地の候補を予め2つに絞っているところから来ている。すなわち、直径(の1つ)の両端に位置する2つの街。

仮に木の中心がある辺にあるとしよう。すべての街が辺のあちら側かこちら側かに二分される。どの街をスタート地点に選んだ場合でも、中心を経由して、中心から最も遠く半径分だけ離れた街を目指すのが最も高くつく。中心を経由しないパスについては、中心に寄り道をするパスを想定して比較材料にすると、最も高くつくケースより安くなることがわかる。


2021年10月09日 (土) 「暑いのに動いてない」なくすエアコン、シャープが発売 設定温度に達した後の湿度上昇防ぐ - ITmedia NEWS」■これは、冷やし終わっても止まらず電気を食い熱を生み続けるエアコン。「冷風を送り出すファンの回転数を抑えることで、室温を下げずに平均湿度を従来機に比べ約12%下げる。」 冷やすことが目的ではないけど除湿のために冷房運転をするからこういう制御になるんだけど、結果は室内の温度ムラを生む。除湿運転によりホットスポットができる。そうするとマッチポンプなんだよ。室温がコントロールできていると思うならあとは除湿ではなく送風を頑張るのがいいと思う。実はコントロールできていませんでした(だから暑い)ということが明らかになったりもするだろう。都合のいいことに消費者の多くは室内機のファンの音をエアコンが仕事をしている音だと思っていると思う。■すべての不満は部屋に対してキャパシティに余裕のあるエアコンを選ぶことで解消するのかな、と考えないではない。


2021年10月05日 (火) 自分のおばあちゃんくらいの世代の人が「行かれる」とか「歩かれへん」という言葉を使っていたイメージがある。行かれるは可能以外の用法も考えられるが、歩かれへんは歩けない以外の意味は考えられない。自分世代なら歩けへんと言う。最近こういう記事を見かけたが(「「ら抜き言葉」で抜かれているのは「ら」ではなかった?「目から鱗」「言われてみれば確かに」 - Togetter」)、ら抜きが行き過ぎた可能動詞化だとすれば、これらは可能動詞以前の形態だと考えられる。『ちいさい言語学者の冒険――子どもに学ぶことばの秘密』という本がある(未読だけど)。子供にとって(たぶん日本語学習者にとっても)歩ける、走れるからの推測で食べれると言ってしまうのはある種の必然なのだろう。自分が小学生の頃は食べれるは食べられるの間違いだと目くじらを立てるくらいにはら抜きが使われていたし、だけどら抜きで何が悪いと開き直れるほどには広がっていなかった。普通一度訂正されたら一生守るよね。二度目は死ぞ。自分は本で読んだ言葉、教科書に書かれていた文法を重んじているが、自然言語はプログラミング言語などと違い文法は後付けの解釈だ。言葉も教科書も移り変わり正解はひとつではない。ATOK では送り仮名を必ず本則に設定するのだが、それ以外が間違いというわけではない。ら抜きは拙く聞こえるしダサいので絶対使わへんけどな! たとえ風俗を写し取るためだったとしても、本の中で使われていたら読み進めるのは苦痛だ。だけど自分から見て上の世代の人がら抜き言葉を話すのもまた、テレビで垣間見える世間で当たり前の光景なんだよね。口語はすっかりら抜きに席巻されてしまった。自分を中心に置いて上と下を見ると時代の流れがわからなくなる。聴覚優位で下の世代の人間はら抜きしか聞こえてこないのでら抜きが当然。では上の世代の人間は? 自ら変化していった? 変化に取り残される人間もいる。省略と拙速は「お嬢様」には似つかわしくありませんことよ。でもさ入れは嫌かも。


2021年10月04日 (月)

最終更新: 2021-11-04T10:11+0900

[AtCoder] AtCoder Beginner Contest 221/F 問題 Diameter set

精進ですよ。おとといあった ABC の F 問題。

コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの2のような円形の木で制限時間内に答えを数えきるためには、木の中心を中心とした組み合わせを考えるしかなかった。

木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を2度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。

木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので1本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。

たとえば直径が偶数の時、直径の中心には頂点が1つある。問題は直径を与える頂点ペアが複数あるときに中心が複数あるかどうか。中心が仮に2つあるなら、2つの中心の中点が本来の中心であるべきであり、直径だと思っていたもの、2つの中心だと思っていたものは直径でも中心でもなかったことになる。だから中心は1つ。

たとえば直径が奇数の時。直径の中心には1本の辺がある。この辺は中心に位置する唯一の辺だろうか。仮に直径の中心に位置する辺が2つあるなら、2つの辺の中点が本来の……(略)。だから中心は1つ。

色の塗り方だけど、中心から最も遠く半径と同じだけ離れている点の集合を、中心から直接出るどの頂点の先にあるかで分類する(中心が辺なら辺が結ぶ2つの頂点を考える)。同じ頂点の先にぶら下がっている2点を同時に塗ってしまうと、そのあいだの距離は必ず直径よりも短くなる。直径より長くなることはありえないし、仮に直径と等しくなることがあるなら、真の中心はどこだ?という話になる。そんなものはない。

ここまでを今朝のうちに納得してから実装したのに、直径が偶数のケースで中心の求め方を間違えたり(提出 #26352819)、線形時間の集計を繰り返して TLE になったり(提出 #26353052)、無駄に長さ N の配列確保を繰り返して TLE になったり(提出 #26353383)、いっぱい間違えた。

配列アクセスとハッシュ表アクセスだと配列の方が断然速いのだけど、初期化が1度で済まないなら、ハッシュ表の初期化コストの低さが効いてくるみたい。

 提出 #26353562 (AC / 750 Byte / 725 ms)

8問目の黄 diff AC。これより上は橙が1問だけだから、かなりのレア度なんだ。

ちなみに 水 diff だった E 問題 LEQ は、まだ TLE を回避する計算方法がわかっていない。

 木の直径

さっき書いた。

木の直径については知っている。(中略)。証明は知らない。

木の中心を念頭に置いて考えると直径を求めるアルゴリズムはこういうことだ。中心は、頂点の場合も辺の場合もあるけど、頂点集合を左右のどちらか(もしくは中心から直接出る辺のどれか)に振り分ける。任意の1点を始点に選んで最も遠い頂点を求める1回目の探索は、中心を挟んで異なる側にある、中心から最も遠い点を求めている。2回目の探索も同じ。同じ側に属する点が最遠点として選ばれることがないのは、中心に寄り道するパスを想定して比較材料にするとわかる。2回の探索で見つかったどちらの頂点も中心からは半径分だけ離れているから、そしてお互いに異なる側にあるから、合わせて直径になる。

 ある問題

さっき書いた。

木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を2度呼び出して答えとしたことがあった。

エディタのログから「.max_by」を GREP したら該当するファイルが(たったの) 15 見つかったので、順番に調べてみた。「ある問題」とは ARC022-C「ロミオとジュリエット」だった。これが青 diff なんだからチョロい!(嘘です。調子乗りました)


2021年10月01日 (金) [AtCoder] 精進。ABC104-C「All Green」(水 diff)。配点の高い問題から解いていきたいけど完答ボーナスがちょっとした番狂わせを演出するのにどう対処するか。貪欲がダメなら DP すればいいじゃない。だから DFS で解いた>提出 #26249595。問題群を ボーナス込みの得点合計÷問題数 でソートして効率のいい方から総当たり(打ち切りあり。残りスコアの合計からと得点効率から計算する最小値更新の見込みから)。問題の解き方は問題群単位で全部解くか1問も解かないかスコアを満たせるだけ解くかの3パターンしかない。制約がたいへん控えめなので解法もバラエティに富んでいる印象>Ruby によるすべての提出。と思ったらほとんどがビット全探索で DFS が少々、といった感じ。DP はダメだったか。たしかに、全部解くか残スコア分だけ解くかの2択に対して p 回繰り返すループは、それが無理な制約ではないにしても無駄が多い。


2021年09月30日 (木) 娘の「なぜ1+1=2なのか」に対して「りんご1つとりんご1つを合わせると2つになるって説明は」と聞くと「それは『例え』」と返された話 - Togetter」■おもしろそうな話。バイリンガルの小学1年生だって。どこに疑問を持ってるのかわからないところがある。たとえば自分なら1と2という文字とその関係について考えている。1+1が3や「あ」ではなく2である理由。だから答えは、順番さえ最初にエイヤで決めてしまってそれに従うのなら(たとえばイロハニホヘト……)、1+1=2がイ+イ=ロでもいい、という話になる。これより難しいことは考えられないし疑問に思うこともありません。ところで、見慣れない表記をしたせいでわからなくなったのだけど、イ+イ=ロからの類推でロ+ロ=ハとしてしまう間違いの原因はどこにあったのか。コメントからのリンクで「ペアノの公理」というページをチラ見したのだけど、「順序」(相対的)ではなくて「0からの隔たり」(絶対的)と考えた方が良かったのですか?


2021年09月29日 (水) ひえーFacebook、Aタグの上でマウス押下した瞬間にhref書き換えてんのか!で次の瞬間マウスクリックするとその書き変わったURLを踏む / Twitter」■なにそれすげー(すごく邪悪)。マウスボタンダウンとマウスクリックの間隙をついた操作。こういうのは大体 Tab/Enter/Appキー/Shift+F10 には対応していない中途半端なゴミになるのが関の山なので、邪悪な目的に使う分にはどうでもいいけど(どうせスクリプトは無効だし、Facebook は非ログインユーザーを門前払いしている)、乱用するとナビゲーションに困難を来す結果になりますよ。■関連で <a> タグの ping 属性を知った。「<a>: The Anchor element | MDN」 いらない機能ですね。「A space-separated list of URLs. When the link is followed, the browser will send POST requests with the body PING to the URLs. Typically for tracking.」 もちろん User-Agent たる Firefox はユーザーが望まない動作を行わないオプションを用意してくれるものと信じている。■まじであった。「Firefox 3 で対応が追加、但し既定では有効化されていない (browser.send_pings の設定で隠蔽)。」 けっこう古くからあったみたい。古すぎて、今でもこの設定が参照されているかは要確認だけど。


2021年09月28日 (火)

最終更新: 2021-12-21T16:21+0900

[AtCoder] AtCoder Beginner Contest 220/F,E

昨日あった ABC。今回は全体に易化傾向で、D 問題がやるだけの茶 diff。F 問題でも水 diff。実は F 問題より E 問題の方が解かれていないけど、そちらも水 diff の範囲。ABC は5完6完を狙いたいところなんだけど、ABCD を 17 分4完(+うっかり余りをとり忘れて 1 WA)でレートは微減。あなたは残りの 83 分間何をしていたのですか?

 F 問題 Distance Sums 2

こちらが先に解けた。やり方はすぐにわかる。1か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どういう処理をどういう順番で並べると答えが次々生み出されてくるのか、とっかかりが掴めなかった。結局、根を1つ決めると木に深さという概念が生まれて、根の深さを0にしておくと全頂点の深さの和が根にとっての答えになった。これがとっかかりになって最後まで書けた。

 提出 #26188321 (AC / 572 Byte / 573 ms)

木の問題は深さと距離と子孫がそれぞれ Depth, Distance, Descendant なもんだから、いつも D が識別子として不足して困る。それに直径(Diameter)も追加で(ちなみにアクセントは i でも e でもなくて a らしいですよ)。

 E 問題 Distance on Large Perfect Binary Tree

83 分間合わないサンプル2を合わそうとしていました。明らかに同じような計算がノードごとに繰り返されるので、累積和の累積和を表引きして TLE を避けるのだと思っていた。ところが実際は一番内部の式が定数になったので(たとえば 2^a × 2^{N-a} が a の値によらないようなこと)、愚直解だと思っていたものがそのまま答えだった。

しかしその愚直解を合わせるのにも一生分の時間がかかるように思われた。死ぬ前に解けて良かった。3つくらい勘違いポイントがあった。組み合わせを半分(それとも2倍?)扱いしなければいけないのはどういうケースか(同じ深さの2頂点を組み合わせて距離 D を作る場合ではない)、それは頂点何個分か(N,D に足し引きして求まる数ではないし冪(数)でもない)。

 提出 #26199345 (AC / 203 Byte / 167 ms)

余りをとる数え上げ問題は正答までの距離が計れなくて途方に暮れがち。

愚直解っていうのは、深さごとに、頂点がいくつあるか、頂点1つが相対的深さ D の頂点をいくつ持っているか、相対的深さ 1 の頂点と D-1 の頂点をいくつ持っているか、相対的深さ 2 と D-2 ならいくつか……を数えて掛け合わせて足し合わせること。

E 問題も F 問題も青 diff でいいじゃないかというくらい苦労したけど、振り返ればどちらも考察は要求されていない(「すぐにわかる」「愚直解」)。ある意味やるだけの問題だった。やるだけ(できるとは言っていない)。


2021年09月25日 (土)

最終更新: 2021-09-30T13:08+0900

[AtCoder] AtCoder Regular Contest 127/A,B

 A 問題 Leading 1s

制約上の上限が 16 桁だっていうから、f の値の上限も 16。たとえば f(x) = 5 のとき、x は 11111 であるかプリフィックスが 111110 であるかのどちらか。f の値ごとに N 以下の範囲にそういう x が何個あるかを数える。桁数を固定すれば数えやすい。提出 #26096008

競プロ典型90問「025 - Digit Product Equation(★7)」の簡単バージョン。

 B 問題 Ternary Strings

頭の中がぐちゃぐちゃで解けなかった。終了直前の提出がこれ>提出 #26101512 (1 WA)。

とってもくやしいことに、1文字書き換えたら通りましたとさ>提出 #26105189 (AC)。2行目の N==1L==1 にしただけ。なんだよもー。もーもーもー。

一応考えたことを。最小化したい最大値の先頭の桁は2で決まっている。その後ろに0から N-1 までの N 個の数を3進数で表記したものをくっつける。これが2から始まる N 個の数。0から始まる N 個の数と1から始まる N 個の数は、桁ごとの制約を満たすようにテキトーに決める。これだけ。なんで書けへんの? 他の人の提出を見ると tr で 0,1,2 をローテーションするのが簡単そうだった。簡単にできることをすごく難しく考えていた。

驚いたことに、このふがいない有様でレートは上昇しているのである()。どれだけ低いレートに甘んじているかわかろうというもの。