今週の火曜日から右足がおかしいな、と思っていたら傷口からばい菌が入ったらしいです。38度の高熱が突然出た上に、ひざ下から足の甲までが腫れあがってしまい、しばらく歩行困難な状態になってしまいました。やらなければならない仕事は在宅でなんとかこなしていたものの、治る見込みが立たないため病院に駆け込み診断を仰いで休養しております。もう少し悪ければしばらく入院と言われちゃいました。
とまあしばらく足に触った瞬間「ｷﾞｬｰｰ」とトムばりの叫び声をあげてしまいかねない状態でしたが、痛み自体はかなり治まっております。しかしまあ痛いことには変わりはなく、明日また診断を仰ぎに行く予定です。
この一週間は目の前の文章を読む集中力さえ維持するのに厳しく、週末のABCはどうしたもんかなと毎晩魘されながら考えていたものですが、参加できなくはなさそう、という判断でratedで突撃することにしました。我ながらアホですね。
ABCE4完で1402パフォ、この病状を鑑みるとよくもまあ落とさずに済んだとは思いますが、D解けてないのはまずいでしょう。
Gを見た瞬間にMoを思いつけないのもけっこうまずく、もうちょっと幅広い勉強というか座学をしないと、後ろの問題へのチャンスを手放し続ける気さえしました。
A - T-shirt
Aにしてはかなり煩雑な部類。けれど、サンプルケースがかなり親切でしたね。
B - Minimize Ordering
これの方がA問題に相応しくないですか？
リストで受け取って、ソートして、joinするだけ。
C - 1111gal password
ついに動的計画法がC問題ですか。DはDPのDと言われて久しい気もするんですが、時代はとにかく突き進んでゆくものです。
1の位が1,9とそれ以外の遷移を気を付ければ終わり。
E - (∀x∀)
Dを眺めていて首をひねってしまったのでEをチラ見したところ、0文字目まで同じ、1文字目まで同じ…という回文をカウントする、という桁DPで行けるな、ってところまでは分かったのでDより先に実装。個人的な感想ですが、EはDよりも発想は簡単ですが、実装自体の難易度を含めるとDEはどっこいどっこいかDの方がややムズくらいかな、と感じました。
ABCZAZという例だったら、
（最初から）0文字被っている回文:Aより早い文字は0個→0*26**2
1文字被っている回文:Bより早い文字は1個→1*26**1（AABBAAとか）
2文字被っている回文:Cより早い文字は2個→2*26**0（ABBBBAとか）
最後にABCCBAが該当するかをチェックすればよいです。
でも実装に時間がかかったのは大いに反省するべき。
26の累乗に関してはどうせ何度も使うので、先に累乗modを計算しておきましょう。
D - ABC Transform
10**18の文字が見えたのでlogベースの計算量になるはず。例を書き出してみて、ぐっと睨めば…と思っていたのですが、時間内に思いつけませんでした。
再帰で計算するにしても、tは1ずつしか減らず、10**18の計算量が間に合わない→一足飛びに計算できないかと悩んでしまったのが良くなかったですね。tは1しか減らなくてもｋは半々に減っていき、0になった瞬間にO(1)で出せる、という事実に気付くことが出来れば…。
ひとまず療養して、ある程度体を動かせる状態にまで回復させるところから。
今回のFもGもまあ題材としては手が届きそうな問題なので、時間を見つけて自分の中でしっかり落とし込んで解説ACしたい。
