AGC047

Aのみの1完。それなりに楽しめたと思うけど、地力のなさを露呈するのがつらい。まあ、最近競プロモチベがかつてないほど低いのと、体調(?)がわりと深刻に悪い(アクセル全開にしないよう心がけていた)ので、仕方ないところはある。

A - Integer Product

入力をどうするか迷うが、文字列として受け取って10^9倍して格納すればよさそう。あとは因数として2と5を何個持っているか数えて、その情報を元に、ペアにして2と5が18個ずつあるものが何通りあるか数えればいい。ここの処理が思ったほど典型ではないなあという印象。18個を超えるものは18個として問題ないので、前から見て18^2通りに分けて何個あるかカウントしておいて、足りるところだけ全部足していく。計算量は20万*18^2なのでまあ間に合う(もう少し速くできないか?)。

入力の実装とその後の考察に時間をかけてしまったと思ったが、意外にいい順位だった。

B - First Second

ここからは、BとCを交互にやっていた。Eもやればよかったけど、BCが解けない見た目はしてなかったからなあ。

K回操作をするとき先頭のK+1文字のうち好きなK文字を削除できる(好きな1文字を残せる)。Kは文字数の差で決まる。文字列をreverseして1文字削除(削除した文字は記録しておく)。辞書順にソートして隣同士の先頭からの一致文字数を見る(計算量は問題ない)。何の文字が欲しいかで26通りの情報を持つ?どこまで一致するかが自分の文字数以下になったら見込みなし。(横書きの文字列をソートして縦に並べたイメージで)上からやって可能性のある範囲を知り、下からやって欲しい文字があるかの情報を更新していく?文字列たちを縦に切って(計算量を総文字数の定数倍で押さえる)右から情報もらって、辞書順だから長さが短くなれば使えなくなると思うので。しかし遠くに短い文字列があるときとかを考えると計算量ダメか。

ロリハは思いつかねえよ……。解けそうだと思ってやっていたけど、まとまらなかった。

C - Product Modulo

「九九」で画像検索して十の位をにらんでいた。20万*20万の表の行と列を何倍かするのとか、FFTとか考えた。

解ける可能性はあると思ってやっていたけど、最終的には全く届かず。