Skip to content

Instantly share code, notes, and snippets.

View ia7ck's full-sized avatar
🍨

ikd ia7ck

🍨
2 followers · 2 following
View GitHub Profile
@ia7ck
ia7ck / ARC033C.rb
Last active April 1, 2017 17:24
ARC 033-C データ構造
class BinaryIndexedTree
def initialize
@N=200_001
@bit=Array.new(@N){0}
end
def add(k, x)
while k<=@N
@bit[k]+=x
k+=(k&-k)
@ia7ck
ia7ck / LIS.rb
Last active April 29, 2017 09:29
LongestIncreasingSubsequence(strictly increasing)
class SegmentTree
def initialize(n)
@root, @nil=0, 0
@sz=2**(Math.log(n)/Math.log(2)).ceil
@seg=Array.new(2*@sz-1){@nil}
end
attr_accessor :seg
def max(a, b, i=@root, l=0, r=@sz)
@ia7ck
ia7ck / CSA10D.cpp
Created August 6, 2017 06:53
CSAcademy Round #10: D.Subarray Medians
#include<iostream>
#include<vector>
using namespace std;
#define int long long
#define repeat(i,n) for(int i=0;i<(n);i++)
struct Median{
int K, k, md;
vector<int> prv, nxt;
@ia7ck
ia7ck / ARC082F.d
Last active September 24, 2017 11:23
ARC082-F Sandglass
void main(){
import std.stdio, std.string, std.conv, std.algorithm;
import std.typecons;
int x, k;
rd(x); rd(k);
auto r=readln.split.to!(int[]);
alias Q=Tuple!(int, "t", int, "a");
auto qs=new Q[](0);
foreach(t; r) qs~=Q(t, -1);
@ia7ck
ia7ck / ノエルちゃん問題.md
Last active January 3, 2018 04:13

https://twitter.com/yfba_/status/948287028415770624

問題１

増加列（Judge ver.）

概要

(1, 2, ..., n)の順列pが与えられる。pの広義増加部分列の個数はいくつか。

方針

dp[i]:=the number of increasing subsequence which ends with i-th element とする。遷移はdp[i]=sum(dp[j])+1。ただし、和はj

@ia7ck
ia7ck / httf2018qual.d
Last active February 19, 2018 02:53
import std.stdio, std.string, std.conv, std.algorithm;
import std.exception, std.random, std.typecons, std.math;
import std.datetime;
auto sw=StopWatch(AutoStart.no);
class Problem{
const int N=100;
const int Q=1000;
const int TL=6000; // ms
@ia7ck
ia7ck / sudoku.rb
Last active August 14, 2018 18:07
solve sudoku
class Sudoku
attr_accessor :table
def initialize(table)
@n, @k = 9, 3 # n=k^2
@table = table
end
def solve
def ok(i, x) # 場所iに数字xを置けるか
@ia7ck
ia7ck / mybinaryheap.d
Last active August 25, 2018 14:16
BinaryHeap
// - Test
// dmd mybinaryheap.d -main -unittest [-cov]
// ./mybinaryheap
//
// - import
// import mybinaryheap : MyBinaryHeap
module mybinaryheap;
unittest
@ia7ck
ia7ck / main.d
Created August 25, 2018 14:19
Benchmark BinaryHeap
void main()
{
import mybinaryheap : MyBinaryHeap;
import std.container.binaryheap : BinaryHeap;
import std.container.rbtree : RedBlackTree;
import std.datetime.stopwatch : benchmark;
import std.stdio : writeln;
import std.random : Random, unpredictableSeed, uniform;
auto rnd = Random(unpredictableSeed);
@ia7ck
ia7ck / index.html
Last active September 6, 2019 11:04
https://cdn.rawgit.com/ia7ck/4b39ce1d14bd0e60fecc9c8fe8e04934/raw/2da46c6335b100e209cdb57bd6f02b822d7645b7/index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title>ABC108/ARC102 D</title>
<meta name="viewport" content="width=device-width, initial-scale=1">
<script src="https://cdnjs.cloudflare.com/ajax/libs/svg.js/2.6.5/svg.js"></script>
<script src="./svg.path.js"></script>
<link href="https://fonts.googleapis.com/css?family=Inconsolata|Lato:400,400i" rel="stylesheet">