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

脳log[20230115]



2023年01月15日 (日) [AtCoder] 今日は ABC285 があった。自分のすべての提出。A-E の5完。かけた時間が A=2分 / B=15分 / C=6分 / D=8分 / E=(21+27)分。■やるだけの B 問題「Longest Uncommon Prefix」の問題文が難しすぎた。パラメータが i,k,l と3つもあるのが良くない。1つを固定して2つ目を動かしているうちに3番目のパラメータに目移りしてその隙に固定していたはずの1つ目が動き出す。その繰り返し。■C 問題「abc285_brutmhyhiizp」は桁数を固定して 26 進数を足していった。■D 問題「Change Usernames」は「お前が名前を変更するのを待ってるぜ」行列を作って変更できる人からどんどん変更していった。グラフ用語で Functional Graph というらしいというのをちょっと前のなもりグラフの問題の時に読んだ気がする。このとき>20220827。解答に際してはグラフとか閉路とかは考えずに単にシミュレートしただけ。待ち行列を配列にしたのは失敗で、1人の改名を複数人が待てるべきではなかった。入力制約のきれいさに助けられた。■最後は E 問題「Work or Rest」。曜日がループしているのでとりあえず1日目を休日にする(最低1つある休日を1曜日と定めたともいえる)。問題文をわかりやすいように解釈すると、休日どうしが近傍の平日の生産性を早い者勝ちで取り合う構図になる。i 日目を休日にしたときの生産性の合計の最大値を記録する DP で、i-1 日目が最後の休日だったら、i-2 日目が最後の休日だったら、と考えていく。係数が2分の1なので N^2 = 2500万でも通るはずだと思ったけど TLE だった>提出 #38064073。ループの回数が2分の1でもその中で配列参照1回に関数呼び出しが3回、関数呼び出し1回につき配列参照2回で、ループ1回当たり 10 の処理をしていたのでは足が出る。Ruby にとってはそういう厳しい制約。これが通っていれば E にかけた時間は 21 分だったけど、TLE 解消に 27 分かかったよね。提出 #38078419 (AC / 1026 ms)。改善ポイントは2つで、1つ目は P (生産性)関数を予め計算してメモしたこと。2つ目は DP で記録する値に i に固有の値を加算していたせいでその値を利用するときには減算していたこと。加算をやめれば減算もいらない道理。なお、この改善はコンテスト終了後のものであり、コンテスト中は C++ で AC を取った。サンプル2の答えが 33 ビット整数だったから 64 ビット変数を使ったらローカルでは実行時エラーになった。コードテストでは通ったので提出したら AC だったけど、慣れないものは使いたくないものだ。■Ruby で自分の改善バージョンより倍ちょっと速くなるらしい>「ABC_285_E "Work or Rest"をrubyで解く」。■F 問題「Substring of Sorted String」はセグメント木で範囲内が昇順かどうか判断できる気がしたけど RE に加えて WA もあるのではお手上げ>提出 #38082557 (WA×8 / RE×1)。一部に AC もあるけどこの提出 #38074190 の AC と一致しているのでは価値がない。この提出は隣接する2文字の転倒関係だけに注目した勘違いの産物だから。■転倒位置の管理が意図に対して誤った手段、というわけではなく、いつもの手抜きセグメント木を修正してモノイドを載せる試みが(RE×1を除いて)失敗というわけでもないとしたら、そもそもの考えが足りていないために AC が9個足りない結果になっている可能性がある。なんだろ。■「S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。」 折りたたまれた用語の説明を読んでいなかった。今回の「部分文字列」は連続部分文字列と呼ばれることもあるものだった。やつあたりに聞こえるだろうけど、知らない人のための用語解説なら折りたたむのも結構だけど、問題の一部としての定義なら隠してはいけないと思う。必ずクリックして開かなければいけないなら(それなしでは問題文が曖昧になるのなら)隠す目的はなんだ。■F 問題。提出 #38104204 (AC / 1984 Byte / 634 ms)。ソースを見るに余裕のなさが窺える。「脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい」。日本語をクラス名にするために Class オブジェクトを明示的に new しているとはずいぶんな余裕のなさ(※日本語は小文字扱いなので(=定数ではないので) class 構文が使えなかった)。間に合うみたいだったのでセグメント木はやめて転倒位置をソート済み配列で管理する当初の方式に BIT 26 本の利用を付け加えた。これを時間内に解くのは無理だよ、量的にも。青 diff でした。青 diff ならもう射程に入ってないといけないんだよなあ。■経緯を忘れてあらためて考えると、転倒位置の管理に BIT を使わない理由がないなあ>提出 #38325205 (AC / 1645 Byte / 593 ms)。BIT 27 本。