結果

問題 No.238 Mr. K's Another Gift
コンテスト
ユーザー ともき
提出日時 2015-07-06 14:41:00
言語 Scala(Beta)
(3.8.2)
コンパイル:
scalac _filename_
実行:
/usr/bin/scala_run _class_
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,435 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,357 ms
コンパイル使用メモリ 258,720 KB
最終ジャッジ日時 2026-03-09 13:35:21
合計ジャッジ時間 10,916 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
-- [E007] Type Mismatch Error: Main.scala:54:6 ---------------------------------
54 |     (for(i <- 0 to n;
   |      ^
   |      Found:    IndexedSeq[(Int, Char)]
   |      Required: Int
55 |          c <- 'a' to 'z') yield (i,c))
   |
   | longer explanation available when compiling with `-explain`
-- [E007] Type Mismatch Error: Main.scala:58:3 ---------------------------------
58 |  }
   |   ^
   |   Found:    Unit
   |   Required: Option[String]
   |
   | longer explanation available when compiling with `-explain`
-- Warning: Main.scala:32:13 ---------------------------------------------------
32 |      private[this] val pow_memo = scala.collection.mutable.HashMap[Long,Long]()
   |             ^^^^^^
   |Ignoring [this] qualifier.
   |The syntax `private[this]` will be deprecated in the future; just write `private` instead.
   |See: https://docs.scala-lang.org/scala3/reference/dropped-features/this-qualifier.html
   |This construct can be rewritten automatically under -rewrite -source 3.4-migration.
1 warning found
2 errors found

ソースコード

diff #
raw source code 

import scala.io.StdIn.readLine
import scala.collection.mutable.PriorityQueue
import scala.annotation.tailrec
import scala.util.control.Breaks

object Lib {
  object Number {
    def doubling[T](x : T, n : Long, zero : T, bop : (T,T) => T) : T =
      if(n == 0) zero
      else if(n % 2 == 0) doubling(bop(x,x),n/2,zero,bop)
      else bop(doubling(bop(x,x),n/2,zero,bop),x)
  }
  object String {
    // ex. b = 26 (if alphabet), mod = 1000000007
    class RollingHash[T](val b : Long,val mod : Long,val conv : T => Long) {
      final def hash(n : T) : Long = conv(n)%mod
      // n = (c0,c1,c2,c3,...cn)
      //  => (c0*b^n + ... + cn*b^0) mod 'mod'
      final def hash(n : Traversable[T]) =
        n.foldLeft(0l)((c,t) => (conv(t)+b*c)%mod)
      final def scan(n : Traversable[T]) =
        n.scanLeft(0l)((c,t) => (conv(t)+b*c)%mod)
      final def apply(n : T) = hash(n)
      final def apply(n : Traversable[T]) = hash(n)
      final def insert(scan_result : IndexedSeq[Long], what : T, i : Int) : Long = {
        val n = scan_result.length-1
        val left  = (scan_result(i) * b_pow_mod(n-i))       % mod
        val right = (scan_result(n) - left + mod)           % mod
        val ins   = (hash(what) * b_pow_mod(n-i))           % mod
        (b * left + ins + right)    % mod
      }
      private[this] val pow_memo = scala.collection.mutable.HashMap[Long,Long]()
      final private def b_pow_mod(n : Long) = pow_memo.get(n) match {
          case Some(v) => v
          case None    => {
            pow_memo(n) = Number.doubling(b,n,1l,(lhs : Long, rhs : Long) => lhs*rhs % mod)
            pow_memo(n)
          }
        }
    }
    object RollingHash {
      def apply[T](b : Long, mod : Long, conv : T => Long) = new RollingHash(b,mod,conv)
    }
  }
}

object Main {
  def solve(s : String) : Option[String] = {
    val r = Lib.String.RollingHash(103,1000000007,(c : Char) => c-'a'+1)
    val a = r.scan(s).toVector
    val b = r.scan(s.reverse).toVector
    val n = s.length
    val p = (0 to n).scanLeft(1l)((i,j) => (i*r.b % r.mod))
     (for(i <- 0 to n;
          c <- 'a' to 'z') yield (i,c))
       .find({case (i,c) => r.insert(a,c,i) == r.insert(b,c,n-i)})
       .map({case (i,c) => s.take(i) + c + s.drop(i)})
  }

  def main(args : Array[String]) : Unit = {
    val s = readLine
    val ret = solve(s) match {
        case Some(j) => j
        case None    => "NA"
      }
    println(ret)
  }
}
0