お久しぶりです。
相変わらず結構毎日忙しいのですが、競プロは変わらず趣味として続けております。レートはほとんど伸びていませんが…
また主に自分の整理の為、ということで、時間の許す限り振り返りを文字にしておこうかなと考えたので、久しぶりに復活です。
まずは土曜日のABC271。
66分5完3ペナ。
Cの貪欲の判例が最初思いつかず、投げた後にWAが出て、ドツボにはまる前にDEを通してきた後に、Cに戻って悪戦苦闘した感じです。Fは40分考える時間あったのに通せなかったのは鍛錬不足ですわね。
しかしまあDEを通すのがあっさり行けたこともあり、自分としてはそこそこパフォーマンスが出てほぼhighestに。「もう1問解けたな…」って時が一番悔しいので何とも言えないですが…。
A - 484558
16進数に直すだけですが、めんどう。
pythonだとhex()を使えばいいという説があるのですが、これはこれで大文字変換がいる。'0123456789ABCCDEF'と文字列を書いた方が早かったかも。
B - Maintain Multiple Sequences
上手くリスト内リストへ格納できますか？系統の問題、初めて見たかも。
C - Manga
ぱっと考えて反例を思いつかず、貪欲を投げちゃいました。
ソートし忘れで1WA（バカ）、そもそもの嘘解法で1WA、よくわからんミスで1WA。
結局ダブった巻数をすべて（-1）にして、deque()の末尾に放り込んだ後、左側がとれるなら左の巻数を取って、だめなら右から2冊取る、を繰り返すコードを書いてAC。ここさえすんなりと行けていたなら…。
D - Flip and Adjust
表裏で2通りあるので、普通の考えれば2の100乗、状態数が必要になるのですが、Sが10000以下という表記があるため、状態数は最悪10000個×100枚分で収まる。
1枚めくるごとに辞書D[i]=['HTTT']みたいに更新して、使い回しDPのようにコードを書きました。カードの置き方の一例を示せばよいので、辞書の中身の通りは1つあればそれだけしか記録しなくてよいです。文字列の追加は文字列分だけ時間がかかっちゃうので、リストにしてappend→最後に文字列出力という手順を取りました。
TLでは復元が話題になっていましたが、復元…？？（苦手分野）
あまり復元というのを考えなくてよい方法だったかなとは。
E - Subsequence Path
2*10**5という制約を見て、UnionFindとかダイクストラかなーと一瞬思いましたが、道が使えるのはEの部分列＝Eiの道のスタートに居る人しか進む権利が無いので、1か所ずつ順番の遷移で済む、ということに他なりません。なので、K回遷移させれば終わりです。
この都市に至るまでの最短距離を10**10としたあと、最小値を順番に更新すればおしまい。ダイクストラと疑いドツボにはまった人も多いらしかったのですが、自分は２，３分ほどの考察で済んで幸運でした。実装もかなり軽かったですしね。
F - XOR on Grid Path
結論から言うと、半分全列挙でした。
N=20なら半分に分割して2**10オーダーにして間に合う、という至極当然の発想ではあるんですが、フォローしていたり同じdiscord鯖に入っている暖色erによるとかなり設定が自明とのことで、いやはや、何も云い訳が出来ないですな。ダーツの例の問題しか問題設定知らなかったんですよね。半分全列挙のことを英語で" Meet in the middle "というらしいのですが、うわなるほどね、と思わされる感じがすごいです。知識不足！
xor、まだお友達（よそよそしい表現）になっていないので良く忘れがちなのですが、ある数字にxorして0にするには同じ数字をぶつければよいです。従って、スタートから真ん中まで、ゴールしてから真ん中までのxor値が一致すればそれで問題なし。
以下はコンテスト後AC。
G,Hは問題未確認。Gは時間をかければ行けそう。
続いてARC149。
ARCは本当に安定していません。緑パフォもまだとりますし、水色を何とか確保していても水下位パフォであることも多く、正直分のいい勝負はさせてもらっている感触はないです。（自分の力不足がもちろん原因ですが…）
当日、10時過ぎからゆる～り3km泳いだ後、買い物に行ったり部屋で作業をしたりして夕方仮眠を取ったのですが、これがまあ最悪の方向に転んでしまいまして、疲れはさほど感じないけど、頭が酸欠の状態に近くどうもこれはまずいのではないか、と夕食を食べながら考えておりました。しかしまあunratedで不参加に出来る選択が、利口だと思えるレートには達していないこともあり、n度目のhighest更新チャレンジと相成りました。果たして結果は＿＿＿（ﾄﾞｺﾄﾞｺﾄﾞｺﾄﾞｺ
何と前日のABCと同じパフォで耐えきり、実に半年ぶりのhighest更新です。微々たるものですが、そりゃあ嬉しいものです。参加できてよかった。下手なりに考えた甲斐があったというものです。
A - Repdigit Number
桁の数字1~9と、N桁なのでおおよそ10*Nの計算量。
数が大きすぎるので、逐一modを取っておく、という動作について、自分はかなり早い段階で履修すべき技術（茶くらい？）と認識していたのですが、kysくん「我々はそりゃあ手足のように使えますけど、これ発明しようと思ってもけっこう編み出す無理じゃないですか？」という言葉に「確かにな」と思いました。知ってるか知らないかで緑のdiffが出来たのかな。
自分は1~9のそれぞれで最大桁数だけ記録して、最後にソートでどれが一番大きくなるか判定しています。
B - Two LIS Sum
Bの設定にとっかかりがなさすぎて、当初Cの問題文を先に読んで10分くらい考えていたのですが、いくらなんでもBの正解者が多すぎる、ということでBにトンボ返り。
で、3例くらい適当に作って紙で実験してみたんですが…ん、これもしかして片方さえ最長に並べれば良くない？と気づく。ここまで15分。
流石に未証明で投げるほどまだ時間は使っていないので少し考えていたのですが、
・Aを1~Nと順番に並べる。この状態からBのLISの長さを増やすために任意の場所2点をswapさせようとするが、swapするとAのLISは少なくとも1減るにもかかわらず、BのLISは増えるかどうかすらわからない
ということに気付きます。
あ、じゃあ片方さえきれいに並べれば最長だ、と自分の中で決まりまして、A,BそれぞれでソートしたもののLISを求めて無事AC。これで目標というかノルマ達成だ～
C - Avoid Prime Sum
こういうのって、偶奇を気にしたあと、市松模様に埋めるのが定石じゃない（どこから市松模様そう思ったんだ？）と当初思っていたのですが、それだとN=3の中心のマスが上下左右4つに応対しなければいけません。偶数を足して合成数になる奇数は7（7+2と7+8）しかないので、極力偶数・奇数の組み合わせが少なくなるような勢力図を示す必要がありそうでです。
Nが偶数の時は真ん中で横に区切ればよいです。
N=4の場合だったら、
[1,3,5,7]
[9,11,13,15]
[2,4,6,8]
[10,12,14,16]
となり、2行目+3行目さえなんとかすればよいです。
自分は[1,3,5,7]と[2,4,6,8]を中心に持ってきて、片方のリストをひっくり返して、合計9になるように配置しました。さすがにN=4で見つかるのだから、Nが大きくなっても合成数に合計がなる組み合わせは1つは見つかるでしょ、と高をくくり、実装。
問題は奇数です。
困ったときはNが小さい時から実験なので、N=3を一先ず埋めてみることに。
3,9,1
5,7,8
4,2,6
が該当します。表の左側は二行目と三行目、右側は一行目と二行目の間に、奇数・偶数の境目があるイメージです。
で、ここからNが奇数の時に全部応用できないかなと考えていたのですが、終了30分前にN=5やN=7のときも1~9の数字を使うんだから、N=3を中央部にカパッとうめれば、わざわざ「7 」みたいな数を見つける必要ないのでは？と気づきます。
流石に偶数+奇数で3の倍数となる数は十分にあるはずですので、Nが奇数の時は
・N=3の結果を真ん中にｽﾞﾄﾞｰﾝする
・偶数+奇数=3の倍数となる（1~9）の入っていない組み合わせを、境界にN-3個入れる
・使った数字を辞書で管理しておいて、残った奇数は上半分、残った偶数は下半分に入れる
で実装。汚いコードになりましたが、無事ACしました。やった～～
↓ほんとうに汚い。
本来ならもう30分早くACしても良かった難易度だと振り返って思いますが、今までのARCで負けるたびに反省してきた「手を動かして実験すること」が一応実践できて、それが実を結んだ形になりましたので、手ごたえがしっかり残った感じです、嬉しい。
上記の「7」みたいな数とその相方を見つける段階も、「N=3を埋め込む」を思いついたためその辺をサボれたのもファインプレーだったかなと思います。ぎりぎりだったけど、今まで続けてきたことが生かされているのかもな、と感じる時間でした。
D,E,F。歯が立たず！ｗ
自分は情報系の出身ではないですし、情報系に向いているかと聞かれたらそうではないと自信を持って言えるのですが、競プロは結構いろんなことを経験させてくれる/思い起こさせてくれるなと強く思います。クイズやっているときも同じことを考えていたような気がするな。
もちろん自分がまた失敗する回も来るでしょうし、ひどく落ち込むことも確実にあると思いますが、自分が少しずつ経験値を貯めていけている感覚を大事にしながら青を目指して行ければなと思います。またがんばりますよ。
え？kysくんもう黄色になるの？
