結果

問題 No.238 Mr. K's Another Gift
コンテスト
ユーザー ともき
提出日時 2015-07-06 14:41:00
言語 Scala(Beta)
(3.6.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,435 bytes
コンパイル時間 9,258 ms
コンパイル使用メモリ 296,572 KB
最終ジャッジ日時 2024-11-14 19:06:04
合計ジャッジ時間 9,632 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:20 ---------------------------------------------------
32 |      private[this] val pow_memo = scala.collection.mutable.HashMap[Long,Long]()
   |                    ^
   |The [this] qualifier will be deprecated in the future; it should be dropped.
   |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 # 

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