koba-e964

[todai-2020-1]
(a,b,c,p,x)
4
(E x)[
    [[a x^2 + b x + c > 0 /\ b x^2 + c x + a > 0 /\ c x^2 + a x + b > 0] <==>
    [x > p]] ==> [p = 0]
].
finish

koba-e964

#!/usr/bin/env python3
import random


i_vowel = list('きしちにひみりぴじぎぢ')

tsu = list('っッ')

def is_valid(s):
    l = len(s)

koba-e964

#![feature(prelude_import)]
#[prelude_import]
use std::prelude::v1::*;
#[macro_use]
extern crate std;
use serde::{Deserialize, Serialize};
struct A<T> {
    a: i32,
    b: i64,
    c: T,

koba-e964

制約と validator 自動生成ツール

$ make test-gen-dsl
c++ -fsanitize=undefined -O2    test-gen-dsl.cpp   -o test-gen-dsl
$ ./test-gen-dsl doc
- $n$ は整数である.
- $m$ は整数である.
$ ./test-gen-dsl validator
long long int n = readLong();
long long int m = readLong();

koba-e964

USER_ID=kobae964

curl -s https://atcoder.jp/users/${USER_ID}/history/json | jq '.[] | select(.IsRated) | .NewRating'

koba-e964

Prop. CC <= 2^E とする。CC が indep sys (E, F) (F := { X <= E : C <= X なる C in CC が存在しない }) の circuit の集合であることと、(C1)かつ(C2)は同値
(C1): {} not in CC
(C2): C1, C2 in CC, C1 <= C2 => C1 = C2

(証明): (=>): (C1) は {} in F から明らか。
(C2): C1 <= C2 を仮定する。
Circuit は、どの要素を取り除いても indep set になるような dep set だったので、
仮に C1 != C2 だったとすると x in C2 - C1 を任意にとって C2 - {x} (>= C1) が indep set にならず矛盾。
よって C1 = C2 である。

koba-e964

r: 2^E -> Z>=0 について、以下の3つは同値。
1. F := { X | r(X) = |X| } としたときに、(E, F) はマトロイドで r は F のランク関数。
2.
  (R1) r(X) <= |X|
  (R2) X <= Y => r(X) <= r(Y)
  (R3) r(X \/ Y) + r(X /\ Y) <= r(X) + r(Y)
3.
  (R1’) r({}) = 0
  (R2’) r(X) <= r(X \/ {y}) <= r(X) + 1
  (R3’) r(X \/ {x}) = r(X \/ {y}) = r(X) => r(X \/ {x, y}) = r(X)

koba-e964

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <atomic>

// Modification of https://yamasa.hatenablog.jp/entry/20101016/1287227939

static volatile int flag0 __attribute__((aligned(64)));
static volatile int flag1 __attribute__((aligned(64)));
static volatile int turn __attribute__((aligned(64)));

koba-e964

digraph modules {
	graph [
		dpi = 1000;
	]
	// nodes
	packed;
	"lib::Match";
	state_id;
	error;
	"ahocorasick::MatchKind";

koba-e964

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{