ｻの練習。蟻本みて書いた。勉強しないといけないですね。 PKUにはこの手の問題が大量にある。 #include<stdio.h> #include<algorithm> using namespace std; int b[410000]; int c[410000]; int z[410000]; int n; int k; int rank[410000]; int tmp[410000]; int sa[410000]; bo</algorithm></stdio.h>…

こんなのsegment treeでO(n log n)で余裕だな！とやってたらずっとTLEしていて頭が悪い… [0,a]と[b,n]のクエリしか使わないんだから線形でしょうに・・・ #include<stdio.h> #include<algorithm> using namespace std; int b[1100000]; char str[5000000]; int sz; int c[1048576</algorithm></stdio.h>…

最大で折り返すのは２回です。ちゃんと向きとかも考えるとまわす回数は4回ですよね。(3回にしていた・・・) この問題の最もクソなところは制約が怪しいところだと思う。答えがsigned-64bitに収まると言われてもinfすら決められないんだが… #include<stdio.h> #include<algorithm></algorithm></stdio.h>…

数年間の誤読の末AC. PKUの中でも超良問の類だと思う。両端の強引な帳尻合わせが最高にCool. #include<stdio.h> #include<algorithm> using namespace std; int segtree[524288]; int query(int a,int b,int c,int d,int e){ if(d</algorithm></stdio.h>

概要：1～nまでの異なる数をいくつかかけて最大になる平方数作ってね 解法：n!の素因数分解で出てくる指数を考える。偶数ならそれは問題ないし、奇数ならそこだけ1でほか0の数(いわゆる素数)で1回だけ割ればよいので、素因数ごとに独立に計算できる。Java逃…

こういう文字が3種類ある問題はコードが3倍になるので嫌いであるということを報告しておきます。 必要な配列のサイズが入力依存で形が変わって(A+B+C=500でA*B*C必要)すべてを1回の宣言で網羅しようとするとMLEするので今回はJavaで。 import java.util.*; c…

遅延系のsegtreeの練習を定期的にしている気がする。 し、デバッグに時間がかかりました。 やることは区間に1を代入、0を代入、xorだけで十分。ほかのはこの三つの組み合わせでいける。というか2つで(1を代入とxor)十分だと思う。 #include<stdio.h> #include<algorithm> using n</algorithm></stdio.h>…

ようやく通った… 100人目のACです。問題文にかかれていない注意点： ・最初は速度が0なので、動けるようになるまで1秒かかります。すなわち開始から1秒後はかならず場所0にいます。 ・最後は速度1で入ってきてもゴール地点で0になるので大丈夫です。 ・最後…

削除のある配列のi番目をlogでわかるようにする。 Segment Treeの典型。IOI2012のpracticeでも本番でもこんなの書いた覚えがある。 #include<stdio.h> #include<algorithm> using namespace std; char str[500010][16]; int c[500010]; int v[500010]; int segtree[1048576]; voi</algorithm></stdio.h>…

点が与えられるのでそれらを含む最小の正方形は？二分探索して角度をがんばって決める。まじめに考えるのが面倒だし制約が小さかったので大量に区間を追加して楽した。 二分探索の回数が足りなくて(30回)誤差死した #include<stdio.h> #include<algorithm> #include<math.h> #include<complex> usi</complex></math.h></algorithm></stdio.h>…

単調増加列用と単調現象列用にすこしずらした配列を持ってあとは典型的なやつ。 あとはまとめて計算してオーダーを落とすタイプのDP。 #include<stdio.h> #include<algorithm> using namespace std; int c[1500]; // use in increasion int d[1500]; // use in decreasion int C[</algorithm></stdio.h>…

この手の問題は大嫌いです。 http://www.ioi-jp.org/ioi/2011/tasks/day1/garden.html に似ています。やることは最初と最後だけまじめに計算して間がループの繰り返しであることを利用して適当にサボるだけです。 #include<stdio.h> #include<algorithm> #include<queue> using namespac</queue></algorithm></stdio.h>…

疲れる問題でした。解法 「空所の左端の位置」「空所の右端の位置」「空所のサイズ(左端だけもっている)」を遅延更新するsegtreeで持つ。 WAの原因はホテルに人を入れるときの「空所の左端の位置」を人数分右にずらすのを忘れていたからでした。 #include<stdio.h> #i</stdio.h>…

ついに解けました。 解法はBFS+DP。何となくJOI 2011のOrienteeringを彷彿とさせる面倒な問題です。 ちなみにBFSの「1回みたところはもうみない」を忘れてREとTLE量産していて初心者すぎた。 #include<stdio.h> #include<algorithm> #include<queue> using namespace std; int c[35][35]</queue></algorithm></stdio.h>…

数年前からそろそろ解かねばなあということで思っていたのでついに解きました。 遅延更新のsegtreeってこう書くんですね。なれとかないと。 ちなみにクエリで与えられる範囲の値が左右逆になることもあるらしいです。普通気がつかないと思う。 #include<stdio.h> #inc</stdio.h>…

ついにBarn Expansionが解けました。 解法： よく考えたらこれ可変長じゃなくて入力によってサイズが変わるので二次元配列にしづらい配列の間違いでした (もちろんvectorはTLEするし、いつもの隣接リストではソートできません)配列のサイズが最初で全部決め…

久しぶりにPOJ Monthlyでもやってみようと思ってやることにしました。3422: Kaka's Matrix Travels いつしかこのブログに書いたはずのDiv1Hardとほとんど同じ問題です。まったく同じ最小費用流をすれば解けます。 #include <vector> #include <algorithm> #include <iostream> #include <queue> #</queue></iostream></algorithm></vector>…

左右をもつタイプのDP。 結構大変ですが、なんとかはなります。 #include<stdio.h> #include<algorithm> using namespace std; pair<int,int> p[1000]; int t[1001]; int dp[1001][1001][2]; int ABS(int a){return max(a,-a);} int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int</int,int></algorithm></stdio.h>…

KMP.久しぶりにオンラインジャッジをやるにはいい問題だと思います。これでPKUのUSACO Unsolvedは16→13に。 #include<stdio.h> #include<algorithm> using namespace std; char str[10000][76]; int fail[10001]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i</algorithm></stdio.h>

7問残っています。 3667 Hotel 2042 USACO 2008 February Gold 2185 Milking Grid 1279 USACO 2003 Fall 3613 Cow Relays 1053 USACO 2007 November Gold 3167 Cow Patterns 536 USACO 2005 December Gold 3168 Barn Expansion 311 USACO 2005 December Gold…

概要 O(N log^2 N)くらいで繰り返しとなる数列(平行移動できる)を求めてください。一般人の解法 さtozangezanの(嘘)解法 ロリハ。いろんなkeyでやったら衝突したしkey2つにしたらTLEが見えているのでkey1つとkeyを1にしたような謎hashでkey1.5みたいなよくわ…

もうすこし真面目に考えてからソースを書くことにします #include<stdio.h> #include<algorithm> #include<queue> using namespace std; struct wolf{ int depth; int r[4]; int c[4]; wolf(){} wolf(int a,int b,int C,int d,int e,int f,int g,int h,int D){ r[0]=a; c[0]=b; r[1]=C; </queue></algorithm></stdio.h>…

ここまでひどい悪問も珍しい。問題のタイトルどおりCensored!されるべき悪問。概要 とりあえずAho-Corasickでも書いてDPしてくださいね。あと、long longなんてものには入らないし答え最大で80桁越えるのでおとなしく多倍長使ってください。一般人の発想 と…

概要： ある数aが与えられるので、 であらわせるものをすべて出力せよ。解法： 基本的にはしゃくとり法でいけます。 を用意してを計算するとかやりたくなりますが、 よく考えるとくらいなのでオーバーフローします。 ここで普通に足し算引き算してやれば解け…

見出しの使い方がわかりません。この記事がCompetitive Programming Advent Calendarの23日目の記事に当たります。JOIについてはあんまり見つからないので、PKUについて紹介したいと思います。PKUというのは(よくPOJという名前で聞く人が多いかもしれません…

なんとかして1000ACを達成。これからも代表になれるまでがんばります。DFSをするだけです。枝刈りもいらないみたい。 #include<stdio.h> #include<algorithm> using namespace std; char str[6]; int p,q; int dat[6][8]; int c[6]; int val[8]; int best[8]; int ret; void dfs(</algorithm></stdio.h>…

みなさんはくれぐれもこんなソースを書かないようにしましょう。 やってることは区間DP #include<stdio.h> #include<algorithm> #include<queue> using namespace std; pair<long long,long long> dp[1000][1000][2]; bool in[1000][1000][2]; int dat[1000]; struct wolf{ int left; int right; int LR; wolf</long></queue></algorithm></stdio.h>…

いい問題だと思います。+1やら やってることは二分探索してほげってるだけです。 #include<stdio.h> #include<algorithm> using namespace std; int a; int dat[100000]; long long count(int b){ int left=0; int right=1; long long ret=0; while(right<a){ while(dat[right]-dat[left]>b)left++; ret+=right-le</a){></algorithm></stdio.h>…

考えずとも解ける簡単な平面走査をしていました。この類はいくらでも過去問ある気がする。解法：問題の図を見て直感的にコードを書く #include<stdio.h> #include<algorithm> using namespace std; long long p[10000]; long long q[10000]; int r[10000]; int segtree[65536]; l</algorithm></stdio.h>…

解法が面白かったのであげておきます。概要n個の点(n ある点を定めて小屋を置く。牛がいるところには小屋は置けない。一番いい場所というのは、小屋とそれぞれの牛たちのマンハッタン距離の和が最小になる点である。 一番いい小屋の位置においたときのマンハ…