/ 最近 .rdf 追記 設定 本棚

脳log[2021-07-05~]



2021年07月05日 (月) [AtCoder] 昨日は ABC 208。E 問題は見た瞬間に競プロ典型 90 問の「025 - Digit Product Equation(★7)」が思い浮かんだ。実際それは外れてなかったっぽい。「ABC208 五分で見ました C:典型 033(小数点以下切り上げ) D:あああああ なんで今出たの E:典型 025 ほぼそのまま(0 がある場合を場合分けすると速そう) F:??? / Twitter」 しかし残る 10 分 15 分で書き上げることはできない。自分は D 問題を通すのだ。■最初の提出 #23975406 (TLE×12 / 21時36分)。k と s を固定してプライオリティキューを使ったダイクストラ法の繰り返し。TLE が出てからが本番です。■2番目の提出 #23980117 (TLE×11 / 21時54分) k から k+1 への遷移にダイクストラ法が必要ないことに気がついた。便宜上 k=0 の場合を想定し、すべての s について1回だけダイクストラ法を実行することに。TLE は1つだけ減った。■3番目の提出 #23981771 (TLE×10 / 22時01分) あれ、k=0 の場合にダイクストラ法っていらなくね?と気がついた。プライオリティキューを削除してダイクストラ法はなし。TLE がまた1つ減った。■4番目の提出 #23983424 (TLE×5 / 22時10分) 余分なものがなくなって遷移ループの最適化に専念。例外値をさっさと検出してループをスキップするのが効くのは TSP 問題の経験が教えている。TLE は 5 つまで減った。そして最後まで 5 つから減らなかった>提出 #23993655 (TLE×5)。■perfect_*.txt と名付けられた全 5 ケースが壁になっていたと後で知った。何が perfect なのかを想像すれば、k が増えるたびにガッツリ最短経路の更新が起こる(ループのスキップができない)のではないかと思う。というより、N×(N-1) の辺がある完全相互通行が可能な網の目ネットワークか。どうやって手を抜けばいいんだ?■コンテスト後にワーシャルフロイド法という名前や、これまでは N≦300 の制約で出題されることが多かった(今回は N≦400)という話が聞こえてきた。アルゴリズムの名前が出てきたからって問題が解けるってことはないよね(負け惜しみ)。■「Ruby によるすべての提出」。コンテスト中の AC はゼロだったけど、最初に tompng さんによる 2893 ms の提出が、次に kojix2 さんによる 1083 ms の提出が AC を取っている。不可能ではないなら自分も通せて然るべきなのだ。ネタバレするのはあきらめたとき。■■■@2021-08-19「ARC035-C アットコーダー王国の交通事情」 これもワーシャルフロイド法っぽくて、しかも N≦400。Ruby での AC は現在に至るまでゼロ! Ruby のバージョンは 1.9 から 2.7 までと幅があるけど、2015 年と同じことが繰り返されているだけだった。


2021年07月04日 (日) プレイ中。アルノサージュの世界はわかりやすい。巨乳は敵! 巨乳は敵! しかしイオンちゃんはそれなりに……。イオンちゃんは敵?(わかりやすくバカなのはお前だ)■アルノサージュは実質的にアルトネリコ4だと評するコメントがあった。アルトネリコの3は発売前から悪ノリが目に余って回避したが、1と2はプレイした。アルトネリコの1と2と4はおすすめできる。再発売される Legend of Mana の横に並べてもいい。特に1がおすすめです。あんなにプレイヤーをやきもきさせる心配なヒロインは初めてでした。■■■「「聖剣伝説 レジェンド オブ マナ」のHDリマスターを遊んだら軽く感情が暴走したので全力でお勧めする:今日書きたいことはこれくらい(1/2 ページ) - ねとらぼ」■■■「『聖剣伝説 レジェンド オブ マナ』HDリマスター版発売を機に、石井浩一氏&高井浩氏にインタビュー。オリジナル版開発秘話を訊く - ファミ通.com

最終更新: 2021-07-14T01:38+0900

[AtCoder] 競プロ典型 90 問/083 - Colorful Graph(★6)

たいへん厳しい。解説1解説2解説3解説4

解説を読めば半分全列挙と同じように、汎用的な手法であるが故に問題から解法を見出そうとしても出てこないタイプの問題と解法だったと言えるのではないか。

以下は解説を読む前の提出。

 提出 #23928493 (TLE×9 / 同じ内容) ※TLE×4 に改善できる

クエリを先読みして頂点ごとに関連するクエリ番号をためておき、メインループは辺について繰り返すことにした。メインループの中ですることは辺が結ぶ2頂点が持つクエリ番号列のマージ。色の伝播を担うのが辺だということと、現在の色を決めるのは直近のクエリだということに着目した解法。

解説1にも書かれているように、これは特定の頂点に辺とクエリが集中したときに処理時間をオーバーする。とはいえこの提出のマージ部分は不必要に時間をかけている。2つのクエリ番号列の長さの和に比例した時間ではなく、二分探索を繰り返してもう少し(<コレ)ましな時間にできる。その場合の TLE は(おそらく)4つ(random_challenge のうち2つと random_clique 2つ)>typical90_83_TLE4?.rb27

 提出 #23932276 (TLE×8 / 同じ内容)

この問題の悩みの種は、クエリに応じた色の変化を隣接ノードに「通知する」ことも、逆に隣接ノードに現在の色を「問い合わせる」ことも、制約から許されていないということ。

ここで、親にだけ通知してみるのはどうだろうと考えた。隣接ノードの数は N のオーダーになりかねないとしても、親であれば1つに決めていい。問題は親の決め方で、この問題のグラフは木ではない。

この提出ではノード番号が小さいものを親の側にあるとした。いきなり「親は1つ」ではなくなっているがしかたがない。だからこその TLE×8 なのだ。

 提出 #23933074 (TLE×5 / 同じ内容)

所与のノード番号を利用するアイディアはお手軽に過ぎたので、今度はちょっと手間をかけて深さ優先探索で親子関係を決め、閉路が見つかったときに限り余分な親を追加することにした。残る TLE は5つ。

テストケースをダウンロードしたら、TLE になっているのは random_clique と名付けられた全2ケースと random_kill と名付けられた全3ケースの合計5ケースだった。自分の解法に弱点があり、そこを見事に狙い撃ちされたといったところか。定数倍の改善では全然間に合わない。

 提出 #23996165 (TLE×2 / 同じ内容)

閉路が見つかったときにどちらをどちらの親にするかは好きに決めていい。親の数を比べて親の数が少ない方に他方を親として追加することにしたら、random_kill と名付けられた3ケースの TLE が解消した。

残るは random_clique が2ケース。random_kill が特定の1、2ノードに辺が集中していたのに対して、この2つのケースはまんべんなく多くの辺が伸びている。クエリに応答する負荷が全体的に底上げされていて逃げ場がない。

 提出 #24004617 (TLE×2 / 同じ内容)

クエリの先読みをしたらメインループの前準備で探索のためのスタックがいらなくなった。クエリに関与しない頂点は無視していいし、入力された辺も片方向だけ記憶しておくのでいい。どちらをどちらの親にするかを決める

# P[v].size は親の数。Qn[v] はクエリで参照される回数
if P[a].size*Qn[a] < P[b].size*Qn[b]

という判定はメインループの負荷をよく反映していて気が利いてると思う。すべてクエリ先読みの効果。でもダメ(TLE)です。さっきの TLE×2 からはローカルで 12 秒が 7 秒になったけど、ならジャッジサーバーでは良くて 5 秒だろう。制限は 3 秒。


2021年07月03日 (土) ゲーム「AとBの効果は重複する。」ワイ「はぇ~じゃあ同時に使うのやめとこ」 : 暇人\(^o^)/速報 - ライブドアブログ」■なんかすごい。新たな日本語の発見だ。これ一部の勘違い人間がスレを立てたのかと思ったら、82 で貼られているスクリーンショットの文章が「ゲーム用語としての『重複』」は意味合いが特殊だから注意しましょうね、というスタンスで書かれていて頭を抱えている。つまり、自分は効果が重複するというのを、片方の効果がキャンセルされたりしない、2つともが効果を発揮している、効果が重複している、というように理解していたのだけど、その(特殊なスタンスの)スクリーンショットに言わせれば「従来の日本語で「重複」と言うと「1つ以外は無駄」というニュアンスで使われることも多かったため知らないと混乱することがあるが(実際ゲーム関連サイトや攻略本などで逆の意味で使われることもあるようだ)、既にかなり定着しているのでそういうものと割り切るしかないだろう。誤解を招きたくない場合は「重複する」を「重ね掛けできる」等と言い替えることも出来る。」 つまり、「効果が重複する」とは「効果が1つ以外は無駄になる」という意味なんだけどゲーム用語では逆の意味になることも多いから「重ね掛けできる」と言い替えた方がいいかもね、と言っている。■ひとつ疑問があります。自分に言わせればトンデモな内容のスクリーンショット(文章)のソースが、検索では見つけられなかった。見つけたら是非、「重ね掛けできる」という用語をゲーム以外のどの界隈で使用するつもりなのか知りたかった。だってゲーム用語としての重複は(そして自分に言わせれば伝統的な日本語としての重複は)もう「既にかなり定着しているのでそういうものと割り切るしかない」と書かれているのだ。誤解のおそれはない。なら誤解を避けるために「重ね掛けできる」と言い替えた方がいいのは、どの界隈の話なのか。俺はゲーム業界の中のさらに狭いジャンルの中で広まりつつある誤用だと思ってる。課金のように。■たぶんまとめ方が恣意的だっただけで、コメント欄が“そこそこ”まともなことに救いを感じてる。■あ、重複(チョウフク)する、ね。あなたがどう読んでいようと、辞書にリダイレクトが設定してあろうとも。■@2021-11-18 ついでに書いとこ。こだわるべきは不自由な日本語ではなくて、重複するはするでもどのように重複するのか、だ。1回なら5割増しが +50% でも ×1.5 でも同じだけど、2回だとそれが +100% なのか ×2.25 なのかという違いが出る。それが攻撃補助なら係数が何にかかっているのかという理解も必要。攻撃力にかかる場合とダメージにかかる場合があるので。


2021年07月02日 (金) なぜUserクラスは負債化しやすいのか “風刺動画”から理解する情報システム開発とモデリング - ログミーTech」■タイトルだけ読んで反応するんだけど、コーディング対象として「User」の名前しか発見できなかったのが敗因では? たぶんそういう状況への反省からこの辺のアイディアが出てきてるんだと思う。「PHP Mentors — 「Lean Architecture / DCI Evening」参加レポート」 ざっくり言うと、コンテキストに応じてロールをアタッチしたりデタッチしたりすること。一人一人の User は存在する。しかし負債化する User と異なりこの User は場(コンテキスト)に応じていくつかの役割を受け持つことができる。それらを全部一緒くたにしてひとつの User クラスにまとめたのが間違いで、個々の側面を Role に分離してモデル化すべきだった、という話だったのではないかと想像しました(読みなさいよ)。■役者(User)と振る舞い(ロール)だけではない。演じる場が第三のコーディング対象。ユースケースという表現もされている。「ユースケースのコードをオブジェクトよりも上のレイヤーに取り出す、ということをやってみましょう。今、ユースケースのコードは、オブジェクトのクラスの中にあります。このユースケースの部分を、クラスの外側に出すのです。そうすると、オブジェクトの方は基本的なクラスのインスタンスのままなので、とても単純です。しかし、これらは実際のところユースケースの一部にはなりません。では、ユースケースの部品は何でしょうか? ロールですね。ユースケースの部品は、ロールの中にあります。開発者は、このようなロールの中からいくつかを選んでまとめます。このまとまりを、コンテキストと呼びます。 つまり、コンテキストがユースケースに相当します。」■ゲームの造りにこれと似た構造があるという話。世界があってプレイヤーキャラクターがいて、プレイヤーははしごを登ったり椅子に座ったり運転席に乗り込んだりする。ゲームの造りとしての話だけど、プレイヤーが世界中のあらゆるオブジェクトに対してどう振る舞えばいいのか何が起こるのかを知っているのではなく、逆にインタラクティブオブジェクトの方がプレイヤーキャラクターの動きをプログラムして操っているのだとか。なんか似てない?


2021年07月01日 (木) [AtCoder] これ面白い。「「ABC-D 虐殺三銃士を連れて来たよ。」 『ABC-D 虐殺三銃士?』 ABC155 Pairs (1845)「億マス計算を負も考慮でやらせちゃうぞ~」 ABC191 Circle Lattice Points (1953)「座標小数にしたけど余裕だよな?」 ABC207 Congruence Points (2074)「幾何幾何幾何平行移動回転移動オラオラオラオラ」」 / Twitter」■Pairs を含む回の ABC は参加していなかったけど、Pairs は最近解いた>20210401p01。なお、取りかかってから AC までひと月半かかった模様。他の2問はコンテスト中に通している。結局のところ、(ABC の) D 問題にしては、という枕詞ありきの評価なのだ。頭を(あまり)使わずすぐに実装に取りかかれる問題が好き。書き上がるまで一時間かそれ以上かかってるし、複素数の取り扱いを間違えて必死で高校生時分の記憶を掘り起こしたりした結果なのであって(定積分だって忘れていた>20210618)、得手にしているわけではないけども。■■■@2021-08-19「億マス計算」って元ネタがある用語だったのか。「ARC037-C 億マス計算」 百マス計算から直接派生して使ってるのだと思ってた。


2021年06月28日 (月) 今日とりあげる競プロ典型 90 問は「030 - K Factors(★5)」。★5つでまずまずの難易度だけど、Ruby で想定解法を通すのは不可能ではないかと思う。500 万回までのループならありでも、5000 万回のループを Ruby で2秒はなしだと思う。かといって組み合わせでどうにかできるのかもわからない。定数倍改善の努力の跡>TLE×13TLE×12TLE×7TLE×3。サンプルの5が強すぎるので、これが通れば AC への道が開けそう。しかしもう万策尽きている。(N, K) に対応した答えを埋め込む?(やらない) ところで、Crystal だと素直に書いて 271 ms らしいですよ。


2021年06月27日 (日) 昨日の競プロ典型 90 問「077 - Planes on a 2D Plane(★7)」■実にタイムリーだった。過去に蟻本に2度取り組んで2度投げ出しているのだけど(20200602p02.03)、しおり代わりのスリップが次はここからだとネットワークフローのページに挟んであるのですね。ちょうど前日にお風呂でページをぱらぱらめくっていたので、すぐにこれが「二部マッチング」の問題だとわかったというわけ。その言葉と概念を仕入れていた。あとは蟻本の C++ コードを Ruby に翻訳する簡単なおしごと。最初の一歩はこういうのでいいでしょう(「慣れてから理解が追いついてくるのを待ってもよいのではないか」)。■提出 #23754353 (TLE×7 / 部分点1+1+2 / 同じ内容) さてどうしよう。見よう見まねなのであってなんの策もない。実行時間制限が 1.5 秒のところ C++ で 400 とか 700 ms かかるらしいんだよなあ(Ruby に手があるのか?)。■■■「二部マッチングでTLEに苦しんだ話 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ


2021年06月26日 (土) 「「ワクチンを接種した後も感染対策は引き続き必要なのであればQoLは変わらないのでワクチンは打つべきでは無い」という意見を見かけて、直後素で『頭が悪いなら考えなければ良いのに・・・』という感想が浮かんでしまった。」 / Twitter」■この間違い探しけっこう難しくないですか? ワクチンを接種した場合もしなかった場合も「感染しない」ことを比較の前提にしてしまっていることが間違いかなと思ったけど、そんな気がするだけ。


2021年06月25日 (金) 今日の競プロ典型 90 問。取りこぼしていた「051 - Typical Shop(★5)」を通した。「キーワード:半分全列挙をしよう」と書いてあるのは知っているのだけど、解説を読む前の提出がなまじ TLE×1 だったせいで捨てるに捨てられなくて、今日まで無得点だった。しかし意地でとうとう通した>#23736923 (1593 ms / 同じ内容)。if k==2 が最後の TLE 対策。それも含めて思いつきを全部試してみましたみたいな頭悪そうな雰囲気が気に入っている。■if k==2 の中身は Pairs と Handshake の解答のオーダーを改善する過程で出てきた形>20210401p01


2021年06月24日 (木) 今日も競プロ典型 90 問。■「073 - We Need Both a and b(★5)」 すごく難しいです。解説を読んでも難しいです。青 diff 後半だった「ARC112-C DFS Game」は(時間をかけて)解けても、これはまだ。解説を読めばプログラムの型はできていたことがわかる。大きなミスは、あるノードを根とする部分木について考えるとき、「単色になる場合」と「二色になる場合」を数えるにあたって、切り捨てる場合があることに気がつかなくて(解説のこの部分「辺(pos,bi)を削除するとき頂点 bi を含む連結成分が 'a', 'b' 両方含む必要がある一方、削除しないとき 'a' しか含まないから」)、必ず単色・二色のどちらかに振り分けようとしていたこと。一応 AC>#23696813 (同じ内容。あ、concat と << でスタックに二重に積んでる)■「074 - ABC String 2(★6)」 前日より★が多いけど、これは★3つくらいのあっさりさで解けた。「この桁の変化は(逆向きだけど)すごく見覚えがあるぞ」「だけど繰り下がりに伴う変化だけちょっと違うぞ」というあたりから。.tr.to_i+.tr.to_i (@2021-06-28 .to_i 一発(相当)で計算できるこんな言語もあるらしい。「2001を2進数で解釈するというのは通常だと意味が通らないが、dcにおいては構わず2×2^3が使われる」)■今日はこの他に取りこぼしていた「045 - Simple Grouping(★6)」を Ruby で通しておいた。組み合わせの総当たりが bitDP でできるというのは初めて知った。Avoid War がまだ通せないとは 20210622 で書いたけど、そのときに覚えた部分集合の列挙をビット演算で行う方法(蟻本に載っていた。144 ページ)がさっそく使えた。1つのケースだけ 20 秒くらいかかって TLE になるので、その場合だけ別の方法で答えを出すなど>#23710778 (1087 ms / 同じ内容)。□わずかな時間を削るためにいろいろと猪口才なことをしている。配列の配列を作るときに長さ14で2^{15}個のインスタンスがいいか長さ2^{15}で14個のインスタンスがいいかとか。2点間距離をメモした D 配列がそのまま DP 配列(E)の初期値であるとか(だから本当は3ビット以上立っている数に限って列挙したい)、DP 配列のその他の初期値が最大値ではなく 0 でいいとか、それによって中間ループを K 回回さないで済んでるとか。ループの中で最初から最後まで使われている d 変数の初期化が実は1回だけですよとか。最内ループの C if A && B が多少冗長ではあるがコストの順に並んでいて総合的には得するだとか(少なくともローカルでは)。しかし、点を一列に並べて端っこから2番目の点を無き者にしてループの指数を1減らす試みは失敗した。


2021年06月22日 (火) 競プロ典型 90 問 072 - Loop Railway Plan(★4)」■テストケースが甘々だから通ったけど、16×16 のドットだけのケース(自作)を通せる解答が作れなかった。これって「023 - Avoid War(★7)」の2点小課題(1≦H,W≦17)が未だに通せない理由なんだけど(真っ白の盤面が壁になっている)、72 問目では許されてしまうのか。


2021年06月20日 (日) Ruby で AtCoder をやってるとよく見かける名前と同じ人が Ruby に速度改善パッチを投げていた(ということに気がついた)。え、すごい。これで Ruby で勝てる(そういう話か?)。


2021年06月18日 (金) 「左の問題を中2に出したら3分後に右の解答が返ってきて絶句した https://t.co/hFaGZQbc3j」 / Twitter」■あかん、定積分わからへん。えっ、それだけの情報で面積求まるの?っていうのが最初の感想。範囲が -1 から 1 までってわかるのに気がついて、x^2-1 の(用語不明)が x^3/3 だから、1 と -1 を……どんな式に代入するのか思い出せない。1^3/3-(-1)^3/3 だと思ったけどそれだと 2/3 なので、4/3 (図中)でも 1/3 (訂正ツイート)でもない。■ところで、錐体っていつ習う? 覚えがない。■ X 軸を無視してるのが良くない気がする。つまり、斜線部っていうのは二次関数だけでなく X 軸と組み合わさってできあがってる範囲なわけだから……(で、どこをどう修正したら 1/3 になる?)。■謎は全て解けた! x^2-1 の(用語不明)は x^3/3 でなく x^3/3-x だ。微分のつもりで定数項を捨ててはいけない。で、これに……?■ X 軸に沿って積分をする。\int_{-1}^1 dx が幅。高さにあたる値は y=0 と y=x^2-1 の差であり、y=0 の方が範囲内では上だからこう 0-(x^2-1)。面積は縦×横だから \int_{-1}^1 [0-(x^2-1)]dx。(用語不明)して 1 と -1 を代入して、-(1^3/3-1)--[(-1)^3/3-(-1)] = 2/3+2/3 = 4/3。だいぶ思い出したのではないか。1/3 との訂正ツイートは違う部分を訂正していたものと思う(よく見たら 1/3 は「体積」だってね)。