問題はこちら。入力文字列Sについて、長さをn、最小周期をpとします。 さらに、q=p*floor(n/(3*p)+1)とおきます。 このようにすると、 2*q<nであるときかつそのときに限り、題意を満たす文字列A,Bが存在し、さらに求めるべきABの長さはqとなる ということが容易に証明できます。以上の考察を基にコードを書くと次のようになります。 #include <stdio.h> #include <string.h> char s[1000010]; int mp[1000010]; int main(){ int i, n, t, p, q = 0; fgets(s, sizeof(s)…</string.h></nであるときかつそのときに限り、題意を満たす文字列a,bが存在し、さらに求めるべきabの長さはqとなる>

JAG春コンテスト2012の問題がAOJに収録されたので，以前書いたコードを投げてみました． 公式の解説によれば 座標変換 平面同士の交線を求める 円と直線の交点を求める ということをするらしいですが，そんな回りくどいことしなくても解けるということで久し…

この問題では、「弾が点Aから壁上の点Pで反射して点Bに達する」という条件を満たす点Pを求める必要があります。これは二分探索や三分探索で求めることもできるらしいですが、今回は探索なしで求める方法を述べます。以後、壁の中心座標を(0,0)、半径をrとし…

今回はこの問題を取り上げます。 まずはショートコーディングではなく、普通に解いてみることにします。この問題では割と珍しいことに、16進数で入力されます。まずはこの入力部ですが、scanfには%xというフォーマットがあるので、これを使えば一発で終わり…

ブログを1ヶ月以上放置していたので、久しぶりに投稿してみます。問題はAOJ 0257です。早速ですが、コードは以下のようになります。 a[];main(){read(0,a,5);*a=!puts(*a%3<1|a[1]&1?"Open":"Close");} 今回は、低レベルな入力関数であるreadにより入力を行…

これの続きです。このコードを短縮します。まずは、配列pow3をわざわざ用意するのは長くなるので、毎回pow関数を使って値を求めることにします。 また、この問題の特徴として、#0と#2が入れ替わっても答えが変わらないことが挙げられます。そこで入力の際、#…

AOJ(Aizu Online Judge)の環境でC言語を使う場合のメモです。特にショートコーディング*1を行う場合、以下の点に注意する必要があります。なお、これらはあくまでショートコーディングを行うためのものであり、通常のプログラミングでは考慮する必要がない(…

実質初投稿です。 書くネタはほとんどないのですが、以前書いたコードの解説でもしてみようかと思います。 題材はAOJ 0503です。私のお気に入りの問題の一つです。問題ではコップが使われていますが、このままだと微妙に図で説明しづらいです。 というわけで…