結果

問題 No.1646 Avoid Palindrome
ユーザー yuruhiyayuruhiya
提出日時 2021-08-13 21:42:12
言語 Crystal
(1.14.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 11,585 bytes
コンパイル時間 13,359 ms
コンパイル使用メモリ 295,600 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-11-08 15:04:51
合計ジャッジ時間 28,341 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 674 ms
5,248 KB
testcase_05 AC 669 ms
5,248 KB
testcase_06 AC 637 ms
5,248 KB
testcase_07 AC 653 ms
5,248 KB
testcase_08 AC 656 ms
5,248 KB
testcase_09 AC 622 ms
5,248 KB
testcase_10 AC 639 ms
5,248 KB
testcase_11 AC 632 ms
5,248 KB
testcase_12 AC 668 ms
5,248 KB
testcase_13 AC 663 ms
5,248 KB
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 AC 341 ms
5,248 KB
testcase_30 AC 339 ms
5,248 KB
testcase_31 AC 336 ms
5,248 KB
testcase_32 AC 346 ms
5,248 KB
testcase_33 AC 341 ms
5,248 KB
testcase_34 TLE -
testcase_35 AC 3 ms
5,248 KB
testcase_36 AC 2 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
testcase_39 AC 2 ms
5,248 KB
testcase_40 AC 2 ms
5,248 KB
testcase_41 AC 2 ms
5,248 KB
testcase_42 AC 2 ms
5,248 KB
testcase_43 AC 338 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# require "/template"
# require "./tuple/times"
struct Tuple
def times(&block) : Nil
{% begin %}
{% for i in 0...@type.size %}
{% if @type[i].has_method?(:each) %}
self[{{i}}].each do |i{{i}}|
{% else %}
self[{{i}}].times do |i{{i}}|
{% end %}
{% end %}
yield({% for i in 0...@type.size %} i{{i}}, {% end %})
{% for i in 0...@type.size %} end {% end %}
{% end %}
end
private class TimesIterator(T)
include Iterator(T)
def initialize(@n : T)
tuple = {% begin %}
{ {% for i in 0...T.size %} T[{{i}}].zero, {% end %} }
{% end %}
@index = tuple.as(T)
@first = true
end
def next
if @first
@first = false
return @index
end
{% begin %}
{%
type = @type.type_vars[0]
size = type.size
%}
{% for i in 1..size %}
if @index[{{size - i}}] < @n[{{size - i}}] - 1
@index = {
{% for j in 0...size %}
{% if j < size - i %}
@index[{{j}}],
{% elsif j == size - i %}
@index[{{j}}] + 1,
{% else %}
{{type[j]}}.zero,
{% end %}
{% end %}
}
return @index
end
{% end %}
stop
{% end %}
end
end
def times
TimesIterator(self).new(self)
end
end
# require "./comparable/min_max"
module Comparable(T)
def min(x : T)
self > x ? x : self
end
def max(x : T)
self < x ? x : self
end
end
# require "./array/new"
class Array
def self.new(sizes : Tuple(*T), initial_value) forall T
{% begin %}
{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { {% end %}
initial_value
{% for i in 0...T.size %} } {% end %}
{% end %}
end
def self.new(sizes : Tuple(*T), &block) forall T
{% begin %}
{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { |index{{i}}| {% end %}
yield({% for i in 0...T.size %} index{{i}}, {% end %})
{% for i in 0...T.size %} } {% end %}
{% end %}
end
end
# require "./array/change"
class Array(T)
def chmin(i : Int, value : T)
(self[i] > value).tap do |f|
self[i] = value if f
end
end
protected def chmin(i : Int, *indexes, value)
self[i].chmin(*indexes, value: value)
end
def chmin(indexes : Tuple, value)
chmin(*indexes, value: value)
end
def chmax(i : Int, value : T)
(self[i] < value).tap do |f|
self[i] = value if f
end
end
protected def chmax(i : Int, *indexes, value)
self[i].chmax(*indexes, value: value)
end
def chmax(indexes : Tuple, value)
chmax(*indexes, value: value)
end
end
# require "./scanner"
# ### Specifications
#
# ```plain
# Inside input macro | Expanded code
# -------------------------------------+---------------------------------------
# Uppercase string: Int32, Int64, etc. | {}.new(Scanner.s)
# s | Scanner.s
# c | Scanner.c
# Other lowercase string: i, i64, etc. | Scanner.s.to_{}
# operator[]: type[size] | Array.new(input(size)) { input(type) }
# Tuple literal: {t1, t2, t3} | {input(t1), input(t2), input(t3)}
# Array literal: [t1, t2, t3] | [input(t1), input(t2), input(t3)]
# Range literal: t1..t2 | input(t1)..input(t2)
# If: cond ? t1 : t2 | cond ? input(t1) : input(t2)
# Assign: target = value | target = input(value)
# ```
#
# ### Examples
#
# Input:
# ```plain
# 5 3
# foo bar
# 1 2 3 4 5
# ```
# ```
# n, m = input(Int32, Int64) # => {5, 10i64}
# input(String, Char[m]) # => {"foo", ['b', 'a', 'r']}
# input(Int32[n]) # => [1, 2, 3, 4, 5]
# ```
# ```
# n, m = input(i, i64) # => {5, 10i64}
# input(s, c[m]) # => {"foo", ['b', 'a', 'r']}
# input(i[n]) # => [1, 2, 3, 4, 5]
# ```
#
# Input:
# ```plain
# 2 3
# 1 2 3
# 4 5 6
# ```
#
# ```
# h, w = input(i, i) # => {2, 3}
# input(i[h, w]) # => [[1, 2, 3], [4, 5, 6]]
# ```
# ```
# input(i[i][i]) # => [[1, 2, 3], [4, 5, 6]]
# ```
#
# Input:
# ```plain
# 5 3
# 3 1 4 2 5
# 1 2
# 2 3
# 3 1
# ```
# ```
# n, m = input(i, i) # => {5, 3}
# input(i.pred[n]) # => [2, 0, 3, 1, 4]
# input({i - 1, i - 1}[m]) # => [{0, 1}, {1, 2}, {2, 0}]
# ```
#
# Input:
# ```plain
# 3
# 1 2
# 2 2
# 3 2
# ```
# ```
# input({tmp = i, tmp == 1 ? i : i.pred}[i]) # => [{1, 2}, {2, 1}, {3, 1}]
# ```
#
# Input:
# ```plain
# 3
# 1 2
# 2 3
# 3 1
# ```
# ```
# n = input(i)
# input_column({Int32, Int32}, n) # => {[1, 2, 3], [2, 3, 1]}
# ```
class Scanner
private def self.skip_to_not_space
peek = STDIN.peek
not_space = peek.index { |x| x != 32 && x != 10 } || peek.size
STDIN.skip(not_space)
end
def self.c
skip_to_not_space
STDIN.read_char.not_nil!
end
def self.s
skip_to_not_space
peek = STDIN.peek
if index = peek.index { |x| x == 32 || x == 10 }
STDIN.skip(index + 1)
return String.new(peek[0, index])
end
String.build do |buffer|
loop do
buffer.write peek
STDIN.skip(peek.size)
peek = STDIN.peek
break if peek.empty?
if index = peek.index { |x| x == 32 || x == 10 }
buffer.write peek[0, index]
STDIN.skip(index)
break
end
end
end
end
end
macro internal_input(type, else_ast)
{% if Scanner.class.has_method?(type.id) %}
Scanner.{{type.id}}
{% elsif type.stringify == "String" %}
Scanner.s
{% elsif type.stringify == "Char" %}
Scanner.c
{% elsif type.stringify =~ /[A-Z][a-z0-9_]*/ %}
{{type.id}}.new(Scanner.s)
{% elsif String.has_method?("to_#{type}".id) %}
Scanner.s.to_{{type.id}}
{% else %}
{{else_ast}}
{% end %}
end
macro internal_input_array(type, args)
{% for i in 0...args.size %}
%size{i} = input({{args[i]}})
{% end %}
{% begin %}
{% for i in 0...args.size %} Array.new(%size{i}) { {% end %}
input({{type.id}})
{% for i in 0...args.size %} } {% end %}
{% end %}
end
macro input(type)
{% if type.is_a?(Call) %}
{% if type.receiver.is_a?(Nop) %}
internal_input(
{{type.name}}, {{type.name}}(
{% for argument in type.args %} input({{argument}}), {% end %}
)
)
{% elsif type.name.stringify == "[]" %}
internal_input_array({{type.receiver}}, {{type.args}})
{% else %}
input({{type.receiver}}).{{type.name.id}}(
{% for argument in type.args %} input({{argument}}), {% end %}
) {{type.block}}
{% end %}
{% elsif type.is_a?(TupleLiteral) %}
{ {% for i in 0...type.size %} input({{type[i]}}), {% end %} }
{% elsif type.is_a?(ArrayLiteral) %}
[ {% for i in 0...type.size %} input({{type[i]}}), {% end %} ]
{% elsif type.is_a?(RangeLiteral) %}
Range.new(input({{type.begin}}), input({{type.end}}), {{type.excludes_end?}})
{% elsif type.is_a?(If) %}
{{type.cond}} ? input({{type.then}}) : input({{type.else}})
{% elsif type.is_a?(Assign) %}
{{type.target}} = input({{type.value}})
{% else %}
internal_input({{type.id}}, {{type.id}})
{% end %}
end
macro input(*types)
{ {% for type in types %} input({{type}}), {% end %} }
end
macro input_column(types, size)
{% for type, i in types %}
%array{i} = Array({{type}}).new({{size}})
{% end %}
{{size}}.times do
{% for type, i in types %}
%array{i} << input({{type}})
{% end %}
end
{ {% for type, i in types %} %array{i}, {% end %} }
end
# require "/math/mint"
macro static_modint(name, mod)
struct {{name}}
MOD = {{mod}}i64
def self.zero
new
end
def self.raw(value : Int64)
result = new
result.value = value
result
end
macro [](*nums)
{% verbatim do %}
Array({{@type}}).build({{nums.size}}) do |%buffer|
{% for num, i in nums %}
%buffer[{{i}}] = {{@type}}.new({{num}})
{% end %}
{{nums.size}}
end
{% end %}
end
getter value : Int64
def initialize
@value = 0i64
end
def initialize(value)
@value = value.to_i64 % MOD
end
def initialize(m : self)
@value = m.value
end
protected def value=(value : Int64)
@value = value
end
def ==(m : self)
value == m.value
end
def ==(m)
value == m
end
def + : self
self
end
def - : self
self.class.raw(value != 0 ? MOD &- value : 0i64)
end
def +(v)
self + self.class.new(v)
end
def +(m : self)
x = value &+ m.value
x &-= MOD if x >= MOD
self.class.raw(x)
end
def -(v)
self - self.class.new(v)
end
def -(m : self)
x = value &- m.value
x &+= MOD if x < 0
self.class.raw(x)
end
def *(v)
self * self.class.new(v)
end
def *(m : self)
self.class.new(value &* m.value)
end
def /(v)
self / self.class.new(v)
end
def /(m : self)
raise DivisionByZeroError.new if m.value == 0
a, b, u, v = m.value, MOD, 1i64, 0i64
while b != 0
t = a // b
a &-= t &* b
a, b = b, a
u &-= t &* v
u, v = v, u
end
self.class.new(value &* u)
end
def //(v)
self / v
end
def **(exponent : Int)
t, res = self, self.class.raw(1i64)
while exponent > 0
res *= t if exponent & 1 == 1
t *= t
exponent >>= 1
end
res
end
{% for op in %w[< <= > >=] %}
def {{op.id}}(other)
raise NotImplementedError.new({{op}})
end
{% end %}
def inv
self.class.raw(1) // self
end
def succ
self.class.raw(value != MOD &- 1 ? value &+ 1 : 0i64)
end
def pred
self.class.raw(value != 0 ? value &- 1 : MOD &- 1)
end
def abs
self
end
def abs2
self * self
end
def to_i64 : Int64
value
end
delegate to_s, to: @value
delegate inspect, to: @value
end
{% to = ("to_" + name.stringify.downcase.gsub(/mint|modint/, "m")).id %}
struct Int
{% for op in %w[+ - * / //] %}
def {{op.id}}(value : {{name}})
{{to}} {{op.id}} value
end
{% end %}
{% for op in %w[< <= > >=] %}
def {{op.id}}(m : {{name}})
raise NotImplementedError.new({{op}})
end
{% end %}
def {{to}} : {{name}}
{{name}}.new(self)
end
end
class String
def {{to}} : {{name}}
{{name}}.new(self)
end
end
end
static_modint(Mint, 1000000007)
static_modint(Mint2, 998244353)
n = input(i)
s = input(c[n])
if n == 1
puts s[0] == '?' ? 26 : 1
exit
end
dp = Array.new({26, 26}, 0.to_m2)
(0...26).each do |i|
next unless s[0] == '?' || s[0] == 'a' + i
(0...26).each do |j|
next unless s[1] == '?' || s[1] == 'a' + j
if i != j
dp[i][j] += 1
end
end
end
s[2..].each do |x|
dp2 = Array.new({26, 26}, 0.to_m2)
if x == '?'
(0...26).each do |i|
(0...26).each do |j|
next if i == j
next if dp[i][j] == 0
(0...26).each do |k|
next if i == k || j == k
dp2[j][k] += dp[i][j]
end
end
end
else
(0...26).each do |i|
(0...26).each do |j|
next if i == j
next if j == x - 'a'
next if i == x - 'a'
dp2[j][x - 'a'] += dp[i][j]
end
end
end
dp = dp2
end
puts dp.sum(&.sum)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0