ferinの競プロ帳

競プロについてのメモ

summerFestivalContest StringGuessing

問題ページ
Hamako Online Judge

考えたこと

問題を開いたタイミングでコンテストが残り20分だったのでササっと部分点を拾えないか考える。
1文字目から順番に1文字ずつ二分探索で決定していくとすると、1文字あたり多くとも5回でできそうでだんだん必要な回数は減っていくので130回あれば特定できそう。実装したら通った。

終わったあとTLを読むとP(26, n)通りの文字列の種類を数字に変換し二分探索すればいいらしい。解説を読むとfactorial number system(階乗進法)を使うとあったが配列で実装した階乗進法での割り算がいくら考えてもわからなかった&&英語でググっても何も出てこなかったのであきらめて多倍長整数を使うことにした。何故か自分のローカル環境で__int128が動かなかったのでスパソから多倍長整数を引っ張ってくる。インタラクティブ向けの関数をつくりつつ書いたら通った。

解法

長さnの文字列はP(26, n)種類ある。この文字列を数字に割り当てて数字で二分探索をする。数字が小さいものほど辞書順で小さい文字列となるように割り当てればよい。