2021年07月24日 (土)
[AtCoder] 今日の ABC211-E Red Polyomino。K マスの連結な形を列挙して照合するのかなと思って、時間的には間に合うみたいなんだけど(サンプルの３が最大ケースだよね)、答えが合いません。■ C 問題が競プロ典型 90 問の 008 - AtCounter（★4）そのままだった。同じ文字が２回現れるというようなひねりくらいあるかと思って何度も chokudai の文字を眺めたけど、どの文字も１回しか出てこないのだった。■E 問題。C1 の初期化を見直したらサンプルの３が合ったので提出した>提出 #24521210 (1 WA)。なんでだよー。■やった！ 提出 #24522032。さっきの提出でもまだ C1 の定義がテキトーだった。たとえば N が 3 で K が 7 のようなとき、中心部分を塗らない形があるのに考えられていなかった。■N.times.with_index((N+1)*(N/2)){|i|...} とか謎なことしてる……。結果的に不要な考慮だったので無駄だけど問題なし。
2021年07月21日 (水)
最終更新: 2022-02-17T12:53+0900
♪ [AtCoder] 第七回 アルゴリズム実技検定 過去問
第四回までの日記>20201111p01。
課金ユーザーじゃなくてごめんね。@atgolfer1 に流れてきたツイートを見てはじめて問題が公開されていること、第七回が行われていたこと、終了していたことを知ったよ。
A - チェックディジット
やるだけ。提出 #24382962
B - 蒸気圧
小さい方を選ぶだけなんだけど、10 分以上切り捨てたり余りを取ったりして悩んでいたのは内緒。提出 #24383193
C - 入力チェック
Ruby なので 10 進 100 桁はなんの障害でもなかった。提出 #24383281
D - 書き換え
５つのパターンをじっと見れば最終結果に影響するような文字の取り合いがないことがわかる。提出 #24383341
E - 青木君のいたずら
探索が許されていることと操作が１回に限られていること、それと遷移が足し算ではなく掛け算だという点が違うけど、問題の形としては ARC122 の C 問題 Calculator を思い出した>20210612p01.03。これが解ければ ARC122-C も解ける！
F - ダブルブッキング
スケジューリングの問題だけど、求められているのが最適化ではなく判定だという点で、最も簡単な部類。提出 #24383711
G - べき表現
20 分考えた。
どんな正の整数でも、テキトーに選んだ正の整数を基数としてその冪乗の和で表せるのは当然だけど(N 進数ってそういうもの)、使える数字が 0 と 1 と -1 に限定された 3 進数ではどのように事情が異なってくるか、という問題。
2×3^x = 1×3^{x+1} - 1×3^x
という感じで、2 を -1 に置き換えてから次の桁にツケをまわしていくのがいいでしょう。提出 #24384055
H - 折れ線グラフ
解けてないよ。制約が小さいから探索していいのだろうけど、それでも 100 の 100 乗になるようなバカな探索は許されない。私はバカです。
@2021-11-15 TLE→AC
上限の揃った制約が DP だと告げている。それも３乗の。まだ８問目だからって雑な探索で解けるとなめてかかっていたのではないか？
- 提出 #27281059 (TLE×4) 腰を据えてもこれである
- 提出 #27281255 (AC / 476 ms)
なだらかな折れ線グラフを書きたいのだから、遷移先の幅は自ずと限られる。(W = A.sum/[N-2,1].max+1 -2, +1 はテキトー)
I - ほくろ
「ABC-D 虐殺三銃士」のひとつ「Congruence Points」を思わせる問題だけど、両目の位置を手がかりに確定した情報が得られるところが優しい。
図形問題は行列や複素数に計算を丸投げしがちなので、これは自分で式を書いた。25 分かかった。提出 #24392172
J - 終わりなき旅
「強連結成分分解をしよう」がキーワードだった競プロ典型 90 問の 021 - Come Back in One Piece（★5）がすぐに思い浮かんだんだけど、深さ優先探索を２回するんだというアルゴリズム解説は何か所かで読んでたんだけど、これは 17 問ある★５問題のうちで解いてない３問の１つなのだった。
雰囲気は掴んでいたので雰囲気で書いた。提出 #24393748。細部が詰められてなくて無駄があるかも。競プロ典型 90 問のおかげでアルゴリズムの顔見せだけは済んでいたので、今度は実装するところまでこぎつけた。
K - 急ぎ旅
理解が甘くて 1 TLE。実装ミス(< にすべきところを <= にしていた)で 1 WA。AC はこれ>提出 #24424698。
最短経路問題ならダイクストラ法なんだけど、満足度と所要時間の２つを考えなければいけないのをどう考えるか。所要時間が最短であることが第一で、満足度の高さはその次に考慮すればいいだけなんだけど、だけど、「満足度について、同じ都市を 2 回以上経由してもその都市の景観は 1 回しかカウントしません
」という文言がちょっとひっかかるよね。経路を記録して重複を排除しないといけないの？(それには無視できないコストが……)
もちろん負の移動時間はないから、同じ都市を２度訪れる経路が最短になることはない。だけど次の２つのようなパスで所要時間の合計が同じになる場合をどのように扱うか迷った。
都市 M に着いたときの満足度の総和は明らかに２、３、４を経由してきた経路の方が大きくなるんだけど、もう一方の経路は M のあとで７、８、９を経由することで取り返すことができるかもしれない。M に着いたときの満足度の低さを理由にして一方のパスを捨てていいのかどうか。
実は上の図には嘘があって、上の図のような状況の実際は下のようになっている。
これは１と M とのあいだの最短所要時間と、M と N とのあいだの最短所要時間がどちらも１つの値に決まることからわかる。最短経路であるどの２つのパスを取り上げても、分岐と合流を繰り返す第３のグラフのような関係になることが納得できたら、ある都市に最短で到着する経路のなかから最大の満足度を記録するのでいい。
L - たくさんの最小値
セグメントツリーなんだけど、最小値を持っているインデックスをどうやって列挙するかという問題。
最小値の記録と添字の記録をセグメント木と配列で分担しようとして TLE を出したり(提出 #24408482)、セグメント木の実装ミスで大量の WA を出したりしつつ(提出 #24412768)、三度目の正直で AC>提出 #24413254。
セグメント木を上から下に下るのって苦手。(根っこが上です。逆にすると頭が働かない)
M - 分割
全部を分割した状態から始めて、損をしない範囲で統合していくのかなと思ったけど、並べ替えができなくて境界が入り乱れるのを、どう整理して扱えるのかわからない。
とある赤亀コーダーさんによると全体でこの M が一番難しかったらしい。
N - モノクロデザイン
昨日これの簡単なバージョンを解いたよ>「B - すぬけ君の塗り絵 2 イージー」(提出 #24414821)。
二次元累積和かなと思うんだけど、ABC203-D Pond も競プロ典型 90 問の 081 Friendly Group（★5）もまだ解いていない。二次元累積和って累積和の累積和とは違うんだなー、という感想を持ったのは覚えてるけど、よく思い出せない。
O - コンピュータ
O 問題が解けたのは初めて。
入力を圧縮したり累積を記録したりして計算量を削減するのは、競プロ典型 90 問の 089 - Partitions and Inversions（★7）ぽいなーと思った。
以下は考えたこと。
- ある B より後ろにあって、前にある B と同じかそれより小さい B は無視できる。
- だから N 個の入力は、B の増加列といくつかの A を足してまとめたもののペアとして圧縮できる。
- 最終日までに得られる報酬の総額は決まっている。コンピュータに支払う金額をどれだけ減らせるかという問題。
- 十分な資金があるなら明らかに B の最大値と同じ値段のコンピュータ１つだけを買うのが最適。
- しかし資金が足りない場合は目の前の障害(B)を超えられるだけのコンピュータを買って、目先の報酬を得るようにしなければいけない。
- なんですかね、貧しさ故に最適な選択ができないって、現実ですか。保険とか追証とか宝くじとか。
- 複数の買い方。障害(B)が１、２、５、６、９と並んでいるときに、１を買って５を買って９を買うのがいいか、２を買って６を買って９を買うのがいいか。局所的な判断では決まらないので貪欲法は使えない。
- 迷うたびにキューを伸ばすと爆発するので DP っぽいなー。
- N^2 のループは許されていないので、すべての i についてそれより後ろにあるすべての要素を処理対象にすることはできない。
- i<j<k とする。コンピュータはできるだけ買わないのが正解だから、ある i と j がともに k にある障害を越えるというとき、j から k への遷移が i から k への遷移より得するということはない。
- i を通過する時点ですでに k を超えられるだけのコンピュータを買う資金があるのだから、到達地点が同じ k なら j で足踏みする価値がない。
- j で足踏みする価値は k より遠くへ(k を超えて一足飛びに)到達できる可能性にある。
- という感じであとはがんばってコーディングする。提出 #24429839
.each_with_index.eachとか謎なことしてる……。幸いにしてこれは無駄なだけで害はないけど、部分的な修正を繰り返すとこういう風に、(通して書き下したときにはありえない)謎なバグを仕込みがち。
2021年07月18日 (日)
最終更新: 2021-07-19T22:56+0900
♪ [AtCoder]AtCoder Regular Contest 123／C 問題 1, 2, 3 - Decomposition (+ B + A)
悔しいなあ。手も足も出ない方がまだあきらめがつく。
提出 #24373137 (WA×20 / RE×12 / AC×2)
１時間かけてコンテスト終了直前に投げた。サンプルすら通っていないけど、５つあるケースの最後の１つの答えが違っているのに気がついていなかった。ダメダメである。
RuntimeError の原因は Array#compact が false を取り除いてくれていないのに気付かずそのまま min メソッドを呼んだこと。
Wrong Answer の原因は比較して小さい方を選ぶべきところで、勝手に優先順位を付けて先に値が得られた方を選んでいたこと。それともう１か所(b+(d-1)%10 の %10 が完全に余計)。
プログラムの型は Send More Money と同じ>20210412p01。桁を見て、キャリー(ボロー)を伝えて、最後まで矛盾なく桁が確定できるかどうか。それを k を増やして条件を緩和しながら最小値を探った。
答えの上限が５だと見抜いていたところは偉いと思うんだ。なぜ５かといえば、項数が１ならある桁に関して作れる数字が 1..3。２なら 2..6、３なら 3..9、４なら 4..12、５なら 5..15 ということで、最初に 10 種類の数字が作れるのが５項の和。0..4 の数字を作ろうとすると繰り上がりが不可避なのが制限だけど、それは隣の桁で吸収できる。６以上に項数を増やしてもできることは増えない。
提出 #24375535 (AC)
ほとんど違いませんよ。でも A から F まで６問ある中の３問しか相手にしていないのに、時間内に完成させられないんだなあ。
実行時間から判断するにだいぶ無駄が多いみたいだけど、制約に苦しめられてたったひとつの解法、たったひとつの記述を探らないでいいってすばらしい。
B 問題 Increasing Triples
ただの貪欲。提出まで 15 分>提出 #24363550
A 問題 Arithmetic Sequence
AC まで 2 WA、33 分。どういうこと？ 10 分時点で９割５分は完成していた>提出 #24355415。デバッグ出力を消し忘れてるのと、入力を勝手にソートしてるのがいけない。列(Sequence)は順序付き！(知らないわけではない。括弧と波括弧に使い分けがありそう？ それは知らない)
AC>提出 #24361099。ほとんど違いませんよ(２回目)。
2021年07月17日 (土)
最終更新: 2022-01-25T19:28+0900
♪ [AtCoder]AtCoder Beginner Contest 210／E 問題 Ring MST (+D 問題)
A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで４完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。
提出 #24322478 (RE×11 / AC×19)
30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、３分岐のうち２つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の２択ではなく AC/WA/RE の３択にするテクニック。WA がなかったということで、中身のある２分岐にミスはなさそう。
提出 #24337207 (AC / 273 ms)
複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。
D 問題 National Railway
DP です。１行目から行ごとに考える。
- ある行について。処理済みの地点に建てた駅からこの行この列に至る最小のコストを記録することにする。
- その次の行にて。各列 Aij の費用を払って駅を建てたとする。前の行の j 列に記録されたコスト(の先にある地点)をもうひとつの駅として、建設費用を計算する。
- 建設費用の最小値が答え。
罠があるとすれば、同じ行から２つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。
提出 #24314328 (AC / 559 ms)
m1 が同じ行内からもう１駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。
その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。
ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。
」で問題文が締められているのだけど、２、３回読み直したよね。え？ どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています
」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。
2021年07月16日 (金) [AtCoder]「083 - Colorful Graph（★6）」で苦しめられた(20210704p01)ケースが random_clique という名前だった。「045 - Simple Grouping（★6）」でべらぼうに速い tinsep19 さんの提出 #22975499 で気になる MinCliqueCover というクラス名。clique ってグラフ用語だった！ 「Clique (graph theory)」■tinsep19 さんの解答のアイデアは、距離がある長さ以下の点間に辺を張ったグラフを考えるとき、K 以下の Clique で全頂点をカバーできる最短の長さを効率的に求めるものだと思う。でも cover? メソッドの @sign と k 乗がまだ全然わからない。もうちょっと考える。■今思えば自分は最初にこの問題を考えたとき、UnionFind を使ってクリークの数が K 以下になる辺の長さを見つけようとしていた。クリークという概念も知らないまま。でも UnionFind でわかるのは連結成分なのであって、連結成分をクリークに分解できないとクリークの数は数えられないんだよね。連結成分を構成する頂点の数と辺の数を見比べて何か見えたりしないか、とか考えてた。
2021年07月15日 (木) [Ruby] Crystal には Enumerable#max_of というメソッドがあるらしい。それ！ Ruby にある Enumerable#max_by はブロックが返した比較のための値(の最大値)ではなく元々の値を返すから、比較関数を与えて最大値を求めたいケースの９割以上で max_by を横目に見ながら .map{}.max って書いてる(あえて F[A.max_by(&F)] と書くのも煩わしいだけなので)。あまりに .map{}.max と書くケースが多いから専用のメソッドが欲しいな、そのときの名前は max_of だと max_of{...} が {...} の中から max を選ぶという意味が明確でいいだろうなと夢想していた。of って単独でも out of のイメージがある。■どれだけ max_by/min_by を使う機会がないかを確かめるためにエディタのログを検索したら、わりと使ってた。少なくとも 13 回>ABC019,ABC023_d,ABC151_f,ABC153,ABC155_c,ABC159,ABC167,ABC178_e,ABC201_d,ARC083_a,ARC103_a,ARC121,tenka1_2012_10。でもずっと多くの回数 .map{}.max と書いてるのは間違いない。
2021年07月14日 (水) 先月 この本(『「決め方」の経済学 「みんなの意見のまとめ方」を科学する』(坂井豊貴 (著) / ダイヤモンド社))を読んだのだけど、そこではボルダルールが大きく取り上げられていたのだけど、その著者の人だ(※未認証)。「戦略的操作の観点からは、MJはボルダよりずっとよいです。だからMJとボルダどちらかを選べと言われたら、MJでしょうか。なぜ私が以前はそんなにMJを評価してなかったかというと、(略)」 書籍は置いていかれている。
2021年07月10日 (土)
昨日の競プロ典型 90 問「088 - Similar but Different Ways（★6）」■88 問目にちなんだ制約 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 点。
2021年07月08日 (木) 今日の競プロ典型 90 問「087 - Chokudai's Demand（★5）」■先週の ABC 後のツイート「D：あああああ なんで今出たの」の理由がわかった。
2021年07月07日 (水)
昨日の競プロ典型 90 問「085 - Multiplication 085（★4）」■★４つにしては難しいと思ったけど、数え上げが(問題を見たくもないレベルで)苦手だから難しく見えているのだと思った。想定解は約数を列挙する全探索だったらしいので、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月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 が出てからが本番です。■２番目の提出 #23980117 (TLE×11 / 21時54分) k から k+1 への遷移にダイクストラ法が必要ないことに気がついた。便宜上 k=0 の場合を想定し、すべての s について１回だけダイクストラ法を実行することに。TLE は１つだけ減った。■３番目の提出 #23981771 (TLE×10 / 22時01分) あれ、k=0 の場合にダイクストラ法っていらなくね？と気がついた。プライオリティキューを削除してダイクストラ法はなし。TLE がまた１つ減った。■４番目の提出 #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日 (日) プレイ中。アルノサージュの世界はわかりやすい。巨乳は敵！ 巨乳は敵！ しかしイオンちゃんはそれなりに……。イオンちゃんは敵？(わかりやすくバカなのはお前だ)■アルノサージュは実質的にアルトネリコ４だと評するコメントがあった。アルトネリコの３は発売前から悪ノリが目に余って回避したが、１と２はプレイした。アルトネリコの１と２と４はおすすめできる。再発売される Legend of Mana の横に並べてもいい。特に１がおすすめです。あんなにプレイヤーをやきもきさせる心配なヒロインは初めてでした。■■■「「聖剣伝説 レジェンド オブ マナ」のHDリマスターを遊んだら軽く感情が暴走したので全力でお勧めする：今日書きたいことはこれくらい（1/2 ページ） - ねとらぼ」■■■「『聖剣伝説 レジェンド オブ マナ』HDリマスター版発売を機に、石井浩一氏＆高井浩氏にインタビュー。オリジナル版開発秘話を訊く - ファミ通.com」
最終更新: 2021-07-14T01:38+0900
♪ [AtCoder] 競プロ典型 90 問／083 - Colorful Graph（★6）
解説を読めば半分全列挙と同じように、汎用的な手法であるが故に問題から解法を見出そうとしても出てこないタイプの問題と解法だったと言えるのではないか。
以下は解説を読む前の提出。
提出 #23928493 (TLE×9 / 同じ内容) ※TLE×4 に改善できる
クエリを先読みして頂点ごとに関連するクエリ番号をためておき、メインループは辺について繰り返すことにした。メインループの中ですることは辺が結ぶ２頂点が持つクエリ番号列のマージ。色の伝播を担うのが辺だということと、現在の色を決めるのは直近のクエリだということに着目した解法。
解説１にも書かれているように、これは特定の頂点に辺とクエリが集中したときに処理時間をオーバーする。とはいえこの提出のマージ部分は不必要に時間をかけている。２つのクエリ番号列の長さの和に比例した時間ではなく、二分探索を繰り返してもう少し(＜コレ)ましな時間にできる。その場合の TLE は(おそらく)４つ(random_challenge のうち２つと random_clique ２つ)>typical90_83_TLE4？.rb27。
提出 #23932276 (TLE×8 / 同じ内容)
この問題の悩みの種は、クエリに応じた色の変化を隣接ノードに「通知する」ことも、逆に隣接ノードに現在の色を「問い合わせる」ことも、制約から許されていないということ。
ここで、親にだけ通知してみるのはどうだろうと考えた。隣接ノードの数は N のオーダーになりかねないとしても、親であれば１つに決めていい。問題は親の決め方で、この問題のグラフは木ではない。
この提出ではノード番号が小さいものを親の側にあるとした。いきなり「親は１つ」ではなくなっているがしかたがない。だからこその TLE×8 なのだ。
提出 #23933074 (TLE×5 / 同じ内容)
所与のノード番号を利用するアイディアはお手軽に過ぎたので、今度はちょっと手間をかけて深さ優先探索で親子関係を決め、閉路が見つかったときに限り余分な親を追加することにした。残る TLE は５つ。
テストケースをダウンロードしたら、TLE になっているのは random_clique と名付けられた全２ケースと random_kill と名付けられた全３ケースの合計５ケースだった。自分の解法に弱点があり、そこを見事に狙い撃ちされたといったところか。定数倍の改善では全然間に合わない。
提出 #23996165 (TLE×2 / 同じ内容)
閉路が見つかったときにどちらをどちらの親にするかは好きに決めていい。親の数を比べて親の数が少ない方に他方を親として追加することにしたら、random_kill と名付けられた３ケースの TLE が解消した。
残るは random_clique が２ケース。random_kill が特定の１、２ノードに辺が集中していたのに対して、この２つのケースはまんべんなく多くの辺が伸びている。クエリに応答する負荷が全体的に底上げされていて逃げ場がない。
提出 #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 秒。