結果
| 問題 |
No.265 数学のテスト
|
| コンテスト | |
| ユーザー |
 Haar
|
| 提出日時 | 2025-03-15 00:15:46 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 20 ms / 2,000 ms |
| コード長 | 13,851 bytes |
| コンパイル時間 | 18,760 ms |
| コンパイル使用メモリ | 401,924 KB |
| 実行使用メモリ | 19,712 KB |
| 最終ジャッジ日時 | 2025-03-15 00:16:07 |
| 合計ジャッジ時間 | 17,227 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 32 |
ソースコード
// Bundled at 2025/03/15 00:14:16 +09:00
// Author: Haar
pub mod main {
use super::*;
#[allow(unused_imports)]
use haar_lib::{get, input, iter::join_str::*, utils::fastio::*};
#[allow(unused_imports)]
use std::cell::{Cell, RefCell};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::rc::Rc;
#[derive(Clone, Default)]
pub struct Problem {}
#[derive(Clone, Debug)]
struct Poly {
data: [i64; 11],
}
impl Poly {
fn new() -> Self {
Self { data: [0; 11] }
}
fn one() -> Self {
let mut ret = Self::new();
ret.data[0] = 1;
ret
}
fn x() -> Self {
let mut ret = Self::new();
ret.data[1] = 1;
ret
}
fn add(a: Self, b: Self) -> Self {
let mut ret = Poly::new();
for i in 0..=10 {
ret.data[i] = a.data[i] + b.data[i];
}
ret
}
fn mul(a: Self, b: Self) -> Self {
let mut ret = Poly::new();
for i in 0..=10 {
for j in 0..=10 {
if i + j <= 10 {
ret.data[i + j] += a.data[i] * b.data[j];
}
}
}
ret
}
fn differentiate(a: Self) -> Self {
let mut ret = Poly::new();
for i in 0..10 {
ret.data[i] = a.data[i + 1] * (i + 1) as i64;
}
ret
}
}
use haar_lib::parser::ll1::*;
#[derive(Copy, Clone, Hash, PartialEq, Eq, Debug)]
enum State {
Number,
Factor,
Term,
Term2,
Expr,
Expr2,
}
impl Problem {
pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
let mut io = FastIO::new();
let _n = io.read_usize();
let d = io.read_usize();
let s = io.read_chars();
let mut parser = LL1Parser::<State, char, Poly>::new();
parser.add_rule(
State::Number,
|c| c.is_digit(10),
|_, input| {
let n = input.consume()?.to_digit(10)?;
let mut ret = Poly::new();
ret.data[0] = n as i64;
Some(ret)
},
);
parser.add_rule(
State::Factor,
|c| c.is_digit(10),
|slf, input| slf.parse(State::Number, input),
);
parser.add_rule(
State::Factor,
|c| c == 'x',
|_, input| {
input.consume_eq('x')?;
Some(Poly::x())
},
);
parser.add_rule(
State::Factor,
|c| c == 'd',
|slf, input| {
input.consume_eq('d')?;
input.consume_eq('{')?;
let temp = slf.parse(State::Expr, input)?;
let ret = Poly::differentiate(temp);
input.consume_eq('}')?;
Some(ret)
},
);
parser.add_rule(
State::Term2,
|c| c == '*',
|slf, input| {
input.consume_eq('*')?;
slf.parse(State::Term, input)
},
);
parser.add_rule_empty(State::Term2, |_, _| Some(Poly::one()));
parser.add_rule(
State::Term,
|_| true,
|slf, input| {
let a = slf.parse(State::Factor, input)?;
let b = slf.parse(State::Term2, input)?;
Some(Poly::mul(a, b))
},
);
parser.add_rule(
State::Expr2,
|c| c == '+',
|slf, input| {
input.consume_eq('+')?;
slf.parse(State::Expr, input)
},
);
parser.add_rule_empty(State::Expr2, |_, _| Some(Poly::new()));
parser.add_rule(
State::Expr,
|_| true,
|slf, input| {
let a = slf.parse(State::Term, input)?;
let b = slf.parse(State::Expr2, input)?;
Some(Poly::add(a, b))
},
);
let s: String = s.into_iter().collect();
let mut input = Input::new(&s);
let ans = parser.parse(State::Expr, &mut input).unwrap();
io.writeln(ans.data.into_iter().take(d + 1).join_str(" "));
Ok(())
}
}
}
fn main() {
main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod iter {
pub mod join_str {
pub trait JoinStr: Iterator {
fn join_str(self, s: &str) -> String
where
Self: Sized,
Self::Item: ToString,
{
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
impl<I> JoinStr for I where I: Iterator + ?Sized {}
}
}
pub mod macros {
pub mod io {
#[macro_export]
macro_rules! get {
( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
{
let n = $num;
(0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
}
};
( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
($(get!($in, $type $(as $to)*)),*)
};
( $in:ident, i8 ) => { $in.read_i64() as i8 };
( $in:ident, i16 ) => { $in.read_i64() as i16 };
( $in:ident, i32 ) => { $in.read_i64() as i32 };
( $in:ident, i64 ) => { $in.read_i64() };
( $in:ident, isize ) => { $in.read_i64() as isize };
( $in:ident, u8 ) => { $in.read_u64() as u8 };
( $in:ident, u16 ) => { $in.read_u64() as u16 };
( $in:ident, u32 ) => { $in.read_u64() as u32 };
( $in:ident, u64 ) => { $in.read_u64() };
( $in:ident, usize ) => { $in.read_u64() as usize };
( $in:ident, [char] ) => { $in.read_chars() };
( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
#[macro_export]
macro_rules! input {
( @inner $in:ident, mut $name:ident : $type:tt ) => {
let mut $name = get!($in, $type);
};
( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
let mut $name = get!($in, $type as $to);
};
( @inner $in:ident, $name:ident : $type:tt ) => {
let $name = get!($in, $type);
};
( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
let $name = get!($in, $type as $to);
};
( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
$(input!(@inner $in, $($names)* : $type $(as $to)*);)*
}
}
}
}
pub mod parser {
pub mod ll1 {
use std::{collections::HashMap, hash::Hash};
pub struct Input<Char> {
input: Vec<Char>,
pos: usize,
}
impl Input<char> {
pub fn new(s: &str) -> Self {
Self {
input: s.chars().collect(),
pos: 0,
}
}
}
impl<Char> Input<Char>
where
Char: Copy + Eq,
{
pub fn consume_eq(&mut self, e: Char) -> Option<Char> {
let c = *self.input.get(self.pos)?;
(c == e).then(|| {
self.pos += 1;
c
})
}
pub fn consume(&mut self) -> Option<Char> {
let ret = *self.input.get(self.pos)?;
self.pos += 1;
Some(ret)
}
pub fn peek(&self) -> Option<Char> {
self.input.get(self.pos).copied()
}
}
pub struct LL1Parser<'a, State, Char, Output> {
rules: HashMap<
State,
(
Option<Box<dyn 'a + Fn(&Self, &mut Input<Char>) -> Option<Output>>>,
Vec<(
Box<dyn 'a + Fn(Char) -> bool>,
Box<dyn 'a + Fn(&Self, &mut Input<Char>) -> Option<Output>>,
)>,
),
>,
}
impl<'a, State, Char, Output> LL1Parser<'a, State, Char, Output>
where
State: Copy + Eq + Hash,
Char: Copy + Eq,
{
pub fn new() -> Self {
Self {
rules: HashMap::new(),
}
}
pub fn add_rule<F1, FP>(&mut self, state: State, check_first: F1, proc: FP)
where
F1: 'a + Fn(Char) -> bool,
FP: 'a + Fn(&Self, &mut Input<Char>) -> Option<Output>,
{
self.rules
.entry(state)
.or_default()
.1
.push((Box::new(check_first), Box::new(proc)));
}
pub fn add_rule_empty<FP>(&mut self, state: State, proc: FP)
where
FP: 'a + Fn(&Self, &mut Input<Char>) -> Option<Output>,
{
self.rules
.entry(state)
.or_default()
.0
.replace(Box::new(proc));
}
pub fn parse(&self, state: State, input: &mut Input<Char>) -> Option<Output> {
for (check_first, proc) in self.rules.get(&state)?.1.iter() {
if let Some(c) = input.peek() {
if check_first(c) {
return proc(self, input);
}
}
}
if let Some(proc) = self.rules.get(&state)?.0.as_ref() {
return proc(self, input);
}
None
}
}
}
}
pub mod utils {
pub mod fastio {
use std::fmt::Display;
use std::io::{Read, Write};
pub struct FastIO {
in_bytes: Vec<u8>,
in_cur: usize,
out_buf: std::io::BufWriter<std::io::Stdout>,
}
impl FastIO {
pub fn new() -> Self {
let mut s = vec![];
std::io::stdin().read_to_end(&mut s).unwrap();
let cout = std::io::stdout();
Self {
in_bytes: s,
in_cur: 0,
out_buf: std::io::BufWriter::new(cout),
}
}
#[inline]
pub fn getc(&mut self) -> Option<u8> {
let c = *self.in_bytes.get(self.in_cur)?;
self.in_cur += 1;
Some(c)
}
#[inline]
pub fn peek(&self) -> Option<u8> {
Some(*self.in_bytes.get(self.in_cur)?)
}
#[inline]
pub fn skip(&mut self) {
while self.peek().is_some_and(|c| c.is_ascii_whitespace()) {
self.in_cur += 1;
}
}
pub fn read_u64(&mut self) -> u64 {
self.skip();
let mut ret: u64 = 0;
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
self.in_cur += 1;
}
ret
}
pub fn read_u32(&mut self) -> u32 {
self.read_u64() as u32
}
pub fn read_usize(&mut self) -> usize {
self.read_u64() as usize
}
pub fn read_i64(&mut self) -> i64 {
self.skip();
let mut ret: i64 = 0;
let minus = if self.peek() == Some(b'-') {
self.in_cur += 1;
true
} else {
false
};
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
self.in_cur += 1;
}
if minus {
ret = -ret;
}
ret
}
pub fn read_i32(&mut self) -> i32 {
self.read_i64() as i32
}
pub fn read_isize(&mut self) -> isize {
self.read_i64() as isize
}
pub fn read_f64(&mut self) -> f64 {
self.read_chars()
.into_iter()
.collect::<String>()
.parse()
.unwrap()
}
pub fn read_chars(&mut self) -> Vec<char> {
self.skip();
let mut ret = vec![];
while self.peek().is_some_and(|c| c.is_ascii_graphic()) {
ret.push(self.in_bytes[self.in_cur] as char);
self.in_cur += 1;
}
ret
}
pub fn write<T: Display>(&mut self, s: T) {
self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
}
pub fn writeln<T: Display>(&mut self, s: T) {
self.write(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
}
impl Drop for FastIO {
fn drop(&mut self) {
self.out_buf.flush().unwrap();
}
}
}
}