Array#- で残ったものをどれでも出力する。■B 問題 Grid Rotation。回転操作は transpose と reverse をテキトーに組み合わせて実現できることを知っている。テキトーに試してみてどんな具合か出力してみてそれが何回右回転したものかを目視で確認する。あとはそれが T とどれだけ一致しているかしていないか数える。■C 問題 Cycle Graph?。スマートにやろうとかテキトーにやろうとすると WA が出るのを知っています。スマートにっていうのは頂点数と辺の数が一致していることを確かめるだとか、頂点の出現回数がどれもちょうど２回であることを確かめるだとか。入力が単純無向グラフであることで多重辺や自己辺といった罠はあらかじめ取り除かれているけど、グラフが複数のサイクルに分かれている場合が罠になる。再帰関数できっちり全頂点を辿れるかを確かめる。きっちりできるかどうかはがんばりしだい。■D 問題 Goin' to the Zoo。100 ms オーバーで TLE だった。こうなるとましな新しい解法を考えることはできなくて、小手先の試行錯誤でなんとかする頭しかない。E 問題のあとでやろうとして帰って来られなかった。■E 問題 Bowls and Beans。2000 ビットのビットフラグで状態を管理することは TLE になるのでできない。できないけど他に思いつかなかった。どうすれば良かったか。茶碗には２種類しかない。最初から豆が入っていた茶碗と、入っていなかった茶碗。あとから豆を入れられた茶碗というものをとりわけて考えない。茶碗１から順番に考えていく。左側にある C 個の茶碗を参照して、現在の茶碗に豆があるとすると最少何回の操作を追加することになるかを記録していく。そのとき、参照した茶碗が元から豆が入っていた茶碗なら、その茶碗に記録されている操作回数は無視して１回が記録対象になる。もともと豆が入っていなかった茶碗なら、その茶碗に記録されている操作回数＋１が記録対象になる。コンテスト中に引っかかっていて解決できなかったポイントがここにある。元は豆が入っていなかった茶碗が右側にある豆を茶碗０に移動する際の中継点になるとき、もちろん複数の茶碗から豆を集めてからまとめて操作をして操作回数を節約したいと考える。さっきのやり方では操作回数を重複して数えてしまうのではないか。そうはならない。現在の茶碗と参照する豆なし茶碗のあいだに豆入り茶碗が存在しているとき、豆入り茶碗が常に優れた参照先になる。ここまではいい。あいだに豆なし茶碗が存在するとき、それが中継点への中継点として役に立つか無視されるかはわからないけど、重複を心配する必要はない。だってどちらの豆なし茶碗もまだ実際には操作回数が答えにカウントされていないのだから。豆なし茶碗の操作回数は豆あり茶碗から参照された時点で初めて答えに寄与し、そのときから参照した豆あり茶碗が参照された豆なし茶碗より優れた参照先になるので、操作回数の重複カウントが起こらない。そういう関係が見えなかったのでコンテスト中はビットフラグで全パターンを網羅しようとして TLE 解しか書けなかったのだった。提出 #65480897 (AC)。■F 問題 Lost and Pound。残りの試行回数と現在の当たり回数しだいでは１つのボタンに全ベットするしかない状況もあるよね。後ろ向きに全パターンを網羅して埋めていくんだろうか。TKKM≦810000 が微妙に小さくて何か見落としてないか不安。ボタンの選び方が簡単に決まらないのかな。30 の選択肢を 1 から 30 個のボタンにどう分配するか。ボタン当たりの賭け数の比率にしか意味がない。30、29+1、28+2、28+1+1、……。これは何通り？ 状態数が TK で遷移が KM かと思ったけど、遷移の M が M の関数だった。■F 問題。提出 #65484558 (WA×18/TLE×1/AC×35)。サンプル３を合わせるために T 回の試行の各回で k=0 から勝ち抜ける場合を特別扱いしているけど、３分の１ほど WA がある。その他の k も特別扱いすればいいのだろうか。頭の中の整理が追いつかなくてどうやるのかわからないけど。……経路の復元をしますか？ すでに TLE が１個出てるのにまだ手をかけますか。■■■F 問題。提出 #65513292 (AC / 1925 ms)。えっとね、サンプル３の合わせ方が間違っていた。後ろ向きの遷移経路の復元ということで順方向の遷移をたどっていて気がついたんだけど、答えが合わない原因は、当たりの数が１増える遷移、２増える遷移、３増える……ばかり考えていて、当たりの数が増えない遷移を考え忘れていたこと。それを忘れたまま変なこと(最初の提出の 34-37 行目)をしてよくも３分の２ほど答えが合ったものだと逆に驚く。そこをちゃんとやれば最初に考えた構成で素直に答えが出た。後ろ向きの遷移を T 回繰り返したあとで k=0 の位置に答えがある。何種類のボタンに何回ずつ賭けるかという配分のしかたは前半部分でプログラム的に求めている。再帰関数で愚直に。TLE×1 の対策は Hash#to_a をしただけ。t/N を事前に計算して t の値に含めておく案もあったけど必要なかった。あとは分配のしかたを埋め込むとか？■■■E 問題。線形時間で解けると読んだので考えた。提出 #65552947 (AC / 124 ms / 49 ms)。124 ms が最初のテストケースに固有の特異な値だとして無視するとその次に遅いのが 49 ms。いいんじゃないでしょうか。C の値に基づいて次の最善手を範囲取得すると log が付いたり２乗になったりする。後ろから見ていくとうまくいく。そのためには ref1, ref2 という２つの変数を蓄えておくだけでよかった。少しだけがっかりするお知らせは、次の一手を範囲取得するのでも、適時(Ai=1 のとき)参照する配列を空にするようにすると 56 ms までにおさまるということ (#65551430)。考えて字数を費やして複雑にした甲斐がない。%D や /D で RE を出す罠もあったらしい。でも問題文にしっかり「非負整数 D」って書いてあるよ。MEX が典型なんだけど、否定で定義されると理解が１ステップどころか２ステップも３ステップも遅れるので、今日も「非負整数……非負…非負……ゼロ以上ってことね」と理解に時間を費やしていたおかげで、%D を書くときにすっと場合分けができた。所要 20 分＋１ペナ。■E 問題 Forbidden Prefix。スマートには解けなかった。結構力押し。クエリを先読みして X の集合と Y の集合をソートしておく。X の各要素について、どの Y 要素の接頭辞になっているかという範囲を二分探索で求めておく(演算は普通に String#<= と String#start_with?)。ここまでが事前準備で、クエリに沿って削除された Y 集合の範囲と、まだ削除されていない Y 集合の要素を２つの BIT で管理しながら答えていった。所要 31 分。■F 問題 Shortest One Formula。1 と 11 と 111 と 1111 の構成方法は確定している。あとは１から N までボトムアップで最短の積と最短の和を構成していった。積と和を区別しているので積と和を構成するにあたり括弧の要不要の判断が簡単にできる。また、積は a*b、和は a+b という２項演算だけを考えた。例えば a+b+c という形が最短になるというなら、それは d(=a+b) の最短と c の最短の２項を組み合わせるなどして構成することができる。和の構成は n/2 通りの総当たり。積の構成は√n通りの総当たり。終了１分前のこの提出 #65289442 の何が WA の原因か。24 行目の文字列リテラルで括弧の付け方を間違えている。それだけ！ くやちい！ ５分オーバーで AC (#65291201)。所要 43 分。■結果出た。コンテスト成績証。690 番 1665 青パフォ。F 問題がぎりぎりで通っていても 100 番 100 パフォ上がるくらいの差みたい？ E を通した時点で 40 分弱残していたのがわりと早かったのだな。じゃあ時間外でも F が解けたということが素直に喜べる。■■■F 問題。最初から積の最短と和の最短を持とうとしていたわけではない。必要がなければわざわざ分けたりはしない。最初は最短の文字列を検索して + があれば括弧で括って掛け算に利用したり、括弧なしで利用したりしようとしていた。でも (1+1)*(1+1) だったら + があるけど括弧なしで掛け算に利用できる。パースする？ それは明らかな無駄。文字列ではなく和クラスと積クラスをネストさせて最後に文字列化するのがいいでしょう。もうひとつ。ある数を積で表す方法と和で表す方法の２通りがあるとき、括弧でo の隣は無条件に . に書き換えておいた。DP をするのかな復元するのかなどうやるのかなと最初は考えていたけど、出力が必然の o か . かそれ以外の ? かということで、２通りの可能性があるなら即座に ? が決定するのだった。最終的に見つかった条件は、「? を１つ以上 o に変えるかどうか」「? を最大限 o に変えなければいけないかどうか」「(最大限 ? を o に変えるとして)連続する ? の個数が偶数か奇数か」というものだった。これで T が決まる。方針を定める時間と考えながら実装する時間で 30 分かかった。■E 問題 Reachable Set。不可能なケースがあるのかなとまず考えた。ある。サンプル２がそうなんだけど、頂点５を経由しないと頂点１と２が連結にならないので、k=2,3,4 が -1 (不可) になる。じゃあ使える辺を使ったときに 1-k までが連結かどうかを UnionFind で管理したいね。同時に、使えない辺の先に繋がっている消したい頂点の集合を管理したいね。同時にできる？ できる。14 分かけたので D の半分。■F 問題 Add One Edge 3。直径の候補は木１の直径と、木２の直径と、i-j を結んで新しくできた i-j を通る直径の３種類だと思った。木の直径は DFS ２回で求まる。新しくできる直径は、各頂点について最も遠い頂点がどれだけ遠いかわかっていればわかる。それは全方位木 DP で求まる。２回の DFS を２つの木に対して合計４回やると、２秒を超えてしまって TLE だった。なにかへまをしていて５秒 10 秒かかるようなスクリプトになっているなら惜しくはないけど、制限時間が３秒だったら通っていたというならあまりにも残念。■コンテスト成績証。ぴったりギリギリで青パフォ。973 位だから「３桁順位に入りたいよー」と書いていた前回の雪辱は果たせたけど、最近落ち目なのだから今日くらいはもっと調子に乗らせてほしかった。■■■X で予告されていたけど、955 位 1607 パフォに上方修正されていた。でもなあ、F を通して 1800 パフォが欲しかったなあ。Forbidden The server refuse to browse the page. The URL or value may not be correct. Please confirm the value. TIME: 1743945073.137446 (2025-04-06 22:11:13 (+0900)) METHOD: POST PATH_QUERY: /ds14050/diary/update.rb SAKURA Internet Inc.」 Ruby のバッククオートは外部コマンドを実行して出力を埋め込むリテラルなので、OSコマンドインジェクションが疑われているのだと思う。Ruby が疑っているのなら Ruby で書かれた tDiary を設置して実行している自分の管轄だけど、もちろんそうではないと思っている。hikidoc.rb はプレインテキストを整形するマークダウンに類するスクリプトであって、二重バッククオートにマークアップ以外の意味はないし、バグでなければ外部入力を実行したりはしない。だけど外形的にはそのように見えてもしかたがないと思うし、同時に、いいかげんなものだなと思う。