最終更新: 2022-01-25T19:28+0900
A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで４完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。
30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、３分岐のうち２つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の２択ではなく AC/WA/RE の３択にするテクニック。WA がなかったということで、中身のある２分岐にミスはなさそう。
複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。
DP です。１行目から行ごとに考える。
罠があるとすれば、同じ行から２つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。
m1 が同じ行内からもう１駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。
その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。
ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。
」で問題文が締められているのだけど、２、３回読み直したよね。え？ どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています
」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。
A1+A2+...+AN≤8888 があからさまな弱点なので、そのサイズの配列にそって処理を進めることにした。不可能なペアはビットフラグにしてカードごとにまとめた。88 ビットは微妙に大きなサイズだけど気にしない。8888 サイズの配列に組み合わせをたくわえていって、かぶりが出たら答え。88 個の組み合わせの総数が 2^{88}-1 なのでどうなるかと思ったが、通った。提出 #24083340 (AC / 213 ms / 同じ内容) 想定解は組み合わせにどんどんカードを足していく深さ優先探索だったのでちょっと違う。こちらは和が小さくなるものから順番に組み合わせを作っていったのだが、無駄が多かったかもしれない。■今日の１問は「089 - Partitions and Inversions（★7）」。典型知識の組み合わせだからとっかかりのない難しさというのではないが、脳がオーバーフローするややこしさなのがつらい。制約が緩かったら再帰でも配列ナメナメでも理解に沿った素直な実装ができるのだが、それが許されないせいでコードを変形して最後の５、６行に行き着くまで何時間もかかった。AC がすごく嬉しい。■しかし毎日 AC を(１つ)増やしてもラストスパートをかける人が増えているのか日々順位は下がっているのだ。くっそー。俺は凸包の点数はいらねーんだ。２点問題が TLE するからって他の言語を使ったりしねーんだ。……なんて考えでいるあたり、「くっそー」と言いつつ全然悔しくはなさそうである。■明日の１問は 9:00 から 19:00 のあいだに提出しないといけない。家を離れている時間とほぼ重なっているのと、スマホコーディングなんて考えられないオールドタイプなせいで、かなり厳しい。チャンスは２時間。★６★７なら見込み薄。■■■一日経ったので(89 問目)>提出 #24092271 (AC / 932 Byte / 805 ms)。驚いたことに想定解法である>ツイート。６つ７つの典型キーワードが列挙されてるけど、すごい人は意識せず当たり前にそれらの考えを適用しているから逆にキーワードが見えにくかったりするのではないか。そういうことが @evima さんおすすめの書『習得への情熱 ─チェスから武術へ─ 上達するための、僕の意識的学習法』に書いてあったよ。自分は意識して自分のものにすべき段階。■「コードを変形して最後の５、６行に行き着くまで何時間もかかった」 これはつまり、問題を解くのに方程式を解くようなやり方ができていないということ。どういうことか。変数を習う前の小学生は速さを求めるのに距離÷時間を、距離を求めるのに速さ×時間を、時間を求めるのに距離÷速さを考える必要があるけれど、中学で変数と方程式を習えばどれか１つの式に変数と値を割り当てて機械的な変形・展開で解ける。求める対象に変数という形を与えることで掛けたり割ったりの対象にできる。そういう強力な道具を与えられた中学生の方がある意味小学生より楽をしている。中学生になりたい。■最終結果。75/90 問、334/423 点でぴったり 200 位。★別集計>★2(8/10)、★3(20/20)、★4(14/14)、★5(14/17)、★6(12/14)、★7(7/15)。★7は部分点付きなので、なんらかの点を取ったものは 15/17 問であり、点数にすると 67/108 点。require'prime' して K.prime_division をこねくりまわす方針が良くなかった。提出 #24021051 (AC / 121 ms / 同じ内容)■ソースコード共有やツイートを見てると「ポリアの数え上げ定理」や「バーンサイドの(ではない)補題」といった異次元キーワードが目に入る。チョトナニイテルノカワカリマセン。■そして今日の問題「086 - Snuke's Favorite Arrays（★5）」も数え上げ。★５つでは足りないよ。でも ABC-E かというと(最近の ABC-E は緑でも水でもなくて青ときどき黄なので)それほどではない。518 バイトは書きすぎだと思うので無駄に難しくしてる可能性あり。■■■一日経ったので(86問目)>提出 #24040292 (AC / 518 Byte / 217 ms / 同じ内容)。てっきり掃き出し法のように干渉する条件をうまくまとめて数えるのだと思った(結局ビット列を列挙して条件列でテストにかけているあたり、自分がうまくやれているとも言えないが)。最終更新: 2021-07-14T01:38+0900
解説を読めば半分全列挙と同じように、汎用的な手法であるが故に問題から解法を見出そうとしても出てこないタイプの問題と解法だったと言えるのではないか。
以下は解説を読む前の提出。
クエリを先読みして頂点ごとに関連するクエリ番号をためておき、メインループは辺について繰り返すことにした。メインループの中ですることは辺が結ぶ２頂点が持つクエリ番号列のマージ。色の伝播を担うのが辺だということと、現在の色を決めるのは直近のクエリだということに着目した解法。
解説１にも書かれているように、これは特定の頂点に辺とクエリが集中したときに処理時間をオーバーする。とはいえこの提出のマージ部分は不必要に時間をかけている。２つのクエリ番号列の長さの和に比例した時間ではなく、二分探索を繰り返してもう少し(＜コレ)ましな時間にできる。その場合の TLE は(おそらく)４つ(random_challenge のうち２つと random_clique ２つ)>typical90_83_TLE4？.rb27。
この問題の悩みの種は、クエリに応じた色の変化を隣接ノードに「通知する」ことも、逆に隣接ノードに現在の色を「問い合わせる」ことも、制約から許されていないということ。
ここで、親にだけ通知してみるのはどうだろうと考えた。隣接ノードの数は N のオーダーになりかねないとしても、親であれば１つに決めていい。問題は親の決め方で、この問題のグラフは木ではない。
この提出ではノード番号が小さいものを親の側にあるとした。いきなり「親は１つ」ではなくなっているがしかたがない。だからこその TLE×8 なのだ。
所与のノード番号を利用するアイディアはお手軽に過ぎたので、今度はちょっと手間をかけて深さ優先探索で親子関係を決め、閉路が見つかったときに限り余分な親を追加することにした。残る TLE は５つ。
テストケースをダウンロードしたら、TLE になっているのは random_clique と名付けられた全２ケースと random_kill と名付けられた全３ケースの合計５ケースだった。自分の解法に弱点があり、そこを見事に狙い撃ちされたといったところか。定数倍の改善では全然間に合わない。
閉路が見つかったときにどちらをどちらの親にするかは好きに決めていい。親の数を比べて親の数が少ない方に他方を親として追加することにしたら、random_kill と名付けられた３ケースの TLE が解消した。
残るは random_clique が２ケース。random_kill が特定の１、２ノードに辺が集中していたのに対して、この２つのケースはまんべんなく多くの辺が伸びている。クエリに応答する負荷が全体的に底上げされていて逃げ場がない。
クエリの先読みをしたらメインループの前準備で探索のためのスタックがいらなくなった。クエリに関与しない頂点は無視していいし、入力された辺も片方向だけ記憶しておくのでいい。どちらをどちらの親にするかを決める
# P[v].size は親の数。Qn[v] はクエリで参照される回数 if P[a].size*Qn[a] < P[b].size*Qn[b]
という判定はメインループの負荷をよく反映していて気が利いてると思う。すべてクエリ先読みの効果。でもダメ(TLE)です。さっきの TLE×2 からはローカルで 12 秒が 7 秒になったけど、ならジャッジサーバーでは良くて 5 秒だろう。制限は 3 秒。
従来の日本語で「重複」と言うと「１つ以外は無駄」というニュアンスで使われることも多かったため知らないと混乱することがあるが(実際ゲーム関連サイトや攻略本などで逆の意味で使われることもあるようだ)、既にかなり定着しているのでそういうものと割り切るしかないだろう。誤解を招きたくない場合は「重複する」を「重ね掛けできる」等と言い替えることも出来る。」 つまり、「効果が重複する」とは「効果が１つ以外は無駄になる」という意味なんだけどゲーム用語では逆の意味になることも多いから「重ね掛けできる」と言い替えた方がいいかもね、と言っている。■ひとつ疑問があります。自分に言わせればトンデモな内容のスクリーンショット(文章)のソースが、検索では見つけられなかった。見つけたら是非、「重ね掛けできる」という用語をゲーム以外のどの界隈で使用するつもりなのか知りたかった。だってゲーム用語としての重複は(そして自分に言わせれば伝統的な日本語としての重複は)もう「
既にかなり定着しているのでそういうものと割り切るしかない」と書かれているのだ。誤解のおそれはない。なら誤解を避けるために「重ね掛けできる」と言い替えた方がいいのは、どの界隈の話なのか。俺はゲーム業界の中のさらに狭いジャンルの中で広まりつつある誤用だと思ってる。課金のように。■たぶんまとめ方が恣意的だっただけで、コメント欄が“そこそこ”まともなことに救いを感じてる。■あ、
ユースケースのコードをオブジェクトよりも上のレイヤーに取り出す、ということをやってみましょう。今、ユースケースのコードは、オブジェクトのクラスの中にあります。このユースケースの部分を、クラスの外側に出すのです。そうすると、オブジェクトの方は基本的なクラスのインスタンスのままなので、とても単純です。しかし、これらは実際のところユースケースの一部にはなりません。では、ユースケースの部品は何でしょうか？ ロールですね。ユースケースの部品は、ロールの中にあります。開発者は、このようなロールの中からいくつかを選んでまとめます。このまとまりを、コンテキストと呼びます。 つまり、コンテキストがユースケースに相当します。」■ゲームの造りにこれと似た構造があるという話。世界があってプレイヤーキャラクターがいて、プレイヤーははしごを登ったり椅子に座ったり運転席に乗り込んだりする。ゲームの造りとしての話だけど、プレイヤーが世界中のあらゆるオブジェクトに対してどう振る舞えばいいのか何が起こるのかを知っているのではなく、逆にインタラクティブオブジェクトの方がプレイヤーキャラクターの動きをプログラムして操っているのだとか。なんか似てない？
