満点で45位でした。A: 実は全探索で枝刈りもすれば2^40も見なくてすむことが分かる(らしい)。探索むずすぎィ！ 何でこんなの7分くらいで解けるんですか… #include<stdio.h> #include<algorithm> using namespace std; char c[200][100]; char d[200][100]; long long e[200]; lon</algorithm></stdio.h>…

今思えば簡単だった…各ノードにたいして持っておくのはpriority_queue。中身の合計も別に持っておく。 DFS調に下から各ノードに対して満足度を求めていく。大事なこととして、 「最初にpriority_queueに子ノードたちのぶんを合体させて持っておく。(いぱテク…

こんなの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>…

1回の手紙を持っていくのに途中で曲がるのは無駄なので縦移動か横移動しかない、ということを考察してDPを考え、 DPをSegment Treeで高速化するテクがこんな時代からIOIに出ていたとは…… AtCoderをみると他の人300ms弱とかで通しているのですが、こんな実行…

wakabaです。1位でした。自分が解いた問題だけいろいろ書いておきます。B: Cube Coloring 気合で数えるだけ。必要な気合も少なめ。 (687Byte) #include<stdio.h> #include<algorithm> using namespace std; long long p[1100]; long long q[1100]; long long r[1100]; int ABS(in</algorithm></stdio.h>…

多少はね。250: いかにも二分探索をしたくなるヤツ シミュレーションするだけ。 public class WakingUp{ public int maxSleepiness(int[]a,int[]b,int[]c,int d){ int ret=0; int val=5040; int now=0; int n=a.length; for(int i=1;i<=val;i++){ now+=d; fo…

KCS Irregular Contest #002 のwriterをしていました。各問題について解説とか余談とかをいろいろまとめておきます。 優勝はuseridさん(5点、01:07:15)でした！A: Prime Slash 解法： dp[i]: iだけ存在するところから全部きったときの期待値 で配るDPする。i…

いいよ！ こいよ！ 良問かけて良問！ ……ファッ250: 普段どおりのパフォーマンスでいけた。 public class MinimumSquare{ public long minArea(int a[],int[]b,int c){ int n=a.length; long ret=4100000000000000000L; for(int i=0;i

自分の真面目さを前面に出して書くことによってJOIerの正常な人間性を訴えます。数字は日にちです19 普通にプラクティスしてた。NTT DATAの食堂。今年の諸注意はなんかブラックな背景で怖いですね。リフレクの10+上位ぜんぜんできないぽよ20 競技してた。侍…

最大で折り返すのは２回です。ちゃんと向きとかも考えるとまわす回数は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>

失敗。250 ちゃんと方針を立ててからコーディングしましょう・・・ public class LCMSet{ int gcd(int a,int b){ while(a>0){ b%=a; int c=a; a=b; b=c; } return b; } public String equal(int[]a,int[]b){ boolean ok=true; int c[][]=new int[50][100]; i…

概要：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>…

(正しい名称がわからないのでタイトル丸コピペしました。)JAPLJさん, rng_58さんと参加。6完8位でした。二人ともプロ過ぎて怖い。 自分が解いた問題だけ貼っておきますJ: やるだけ。というより英語を読むだけ。ただし英語が読めず嵌る。りんごさんに英語を読…

東大の前期教養の理系を想定しています。文系は知りません。おすすめする科目とお勧めしない科目のリストアップというより自分が各科目に対して感じたイメージ用語説明 逆評定：時代錯誤社とかいう出版サークルが出している雑誌。毎学期の最初のほうで街頭販…

試験も近いのにAOJ。しかも簡単な問題。1156 Dijkstraするだけ。 #include<stdio.h> #include<queue> #include<algorithm> using namespace std; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; int c[5]; int m[50][50]; int ijk[50][50][4]; int v[50][50][4]; int main(){ int a,b; whil</algorithm></queue></stdio.h>…

僕がよく送ってrejectされるセットにとても近い。250: 自明なgreedy #include<stdio.h> #include<vector> #include<algorithm> using namespace std; class AlienAndHamburgers{ public: int val[1100]; int M[1100]; int T[1000]; int H[1100]; int getNumber(vector<int>a,vector<int>b){ int n=a</int></int></algorithm></vector></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>…

実は参加してました。D: 数え上げだし解法自明だったので解こうとしたが、変なケースがありはまった。WA*3がつらい。 #include<stdio.h> #include<algorithm> using namespace std; int b[110000]; long long fact[310000]; long long factinv[310000]; long long inv[310000]; p</algorithm></stdio.h>…

今日は寝ないでMedium過去問をたくさん解くぞ(^^) レーティングあげるためにがんばろう！笑 問題解き次第ソースコードを張ります←

疲れる問題でした。解法 「空所の左端の位置」「空所の右端の位置」「空所のサイズ(左端だけもっている)」を遅延更新する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>…

これも新年企画ということで、ACするごとにここにソースコードとかをアップロードしていく予定です。適宜更新してみてください。A: やるだけ #include<stdio.h> int dp[10001]; int b[120]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); dp[0]=1; for(int i=0;i<a;i++){ for(int j=10000;j>=b[i];j--){ dp[j]|=dp[j</a;i++)scanf("%d",b+i);></stdio.h>…