/ 最近 .rdf 追記 編集 設定 本棚

脳log[20230304]



2023年03月04日 (土) [AtCoder] 今日あった ABC292のふりかえり。コンテスト成績証自分のすべての提出。■A 問題「CAPS LOCK」。入力の小文字を大文字にする。Ruby のこの手のメソッド名がこれまで一度で当てられたためしがない。JavaScript なら toUpperCase()。Ruby では? capitalize, toupper, uppercase, upcase さてどれでしょう。答えに行き当たらないこともままある。■B 問題「Yellow and Red Card」。0=カードなし、1=イエロー、2=レッドで管理すれば良い。イエローの 1 とレッドの 2 が入力(c)として与えられているからと分岐をひとつサボったけど、まあどうでもよろし。■C 問題「Four Variables」。N×N の組み合わせは許されないけど掛けて N 以下になる組み合わせは列挙できる。それよりも、問題文の「AB+CD=N」が4、5回読んでも理解できなかった。サンプルにヒントを求めても解答例が理解できなかった。つまり、A=12、B=34 だとして、AB=1234 だと読んでしまってそこから抜け出せなかった。A×B+C×D=N の意味ではないかとようやく推測できて、その解釈でサンプルが理解できることを確かめても、まだ半信半疑で問題に本腰を入れられなかった。問題文が難解。■D 問題「Unicyclic Components」。UnionFind をするついでに辺の本数を数えた。グラフの性質を踏まえたかっこいい解法で解きたいなと思ったけど、最近あほなので愚直にやった。■E 問題「Transitivity」。最初はダメ解法に捕まってしまった。こういうの。ある頂点を見て、入ってくる頂点と出て行く頂点の組み合わせを考える。すでに両者に辺が通っているなら操作はいらない。そうでなければ直通辺を足す。このやり方でやるとサンプルの3の答えが 17 と過大になってしまった。自分としては珍しいことだけど、そこで一旦リセットしてイチから別の解法を考えてみた(出口のない泥沼の数合わせに終始するのが見えてしまって瞬時にうんざりしてしまったのだ)。ある頂点から到達できる頂点というのは、必ず直通辺が通っていなければいけない頂点なのであって、距離2以上の頂点が操作の対象。有向辺なので問題は始点に選んだ頂点ごとに独立。足がかりに使う距離1の隣接頂点も無関係。N の2乗が通る制約なので全頂点を始点にして BFS をした。■F 問題「Regular Triangle Inside a Rectangle」。辺の長さが1の正三角形をちょっとずつ回転させて外接する矩形の大きさを調べた。そこから矩形の拡大倍率を求めたんだけど WA×10 が解消できなかった。二分探索をするのだと見かけてテキトーにでっちあげてみれば WA×43 と悪化していて AC が遠い。水 diff ですってよ。