makeplexさんのー

なんかプログラミング好きな人たちの間で、

makeplexさんの出された問題がはやっていたので、解いてみました。

頑張って解いたのですが、

何の変哲もないプログラムになってしまい寂しかったので、

ショートコーディング(プログラムを可能な限り短くする遊び)をやってみました。

600文字を切ったのでとりあえず満足。

多分ショートコーディングのプロとかがやれば

300文字ぐらいになるのでしょうが、

自分は適当に妥協することにしますw

ソースを貼っておきますが、

ネタバレにならないように色を青っぽくしておきます。

見たい人は選択して色反転させるなりして見てくださいね。


仕様:

入力は複数のデータセットを含み、各データセットは昇順13個の1-9なる数。

出力はmakeplexさんのものの通り。出力順序の入れ替わりは可とする。

Sample Input:

1112224588899
1122335556799
1112223335559
1223344888999
1112345678999

Sample Output:

1112224588899
(111)(222)(888)(99)[45]

1122335556799
(123)(123)(567)(99)[55]
(123)(123)(567)(55)[99]
(123)(123)(555)(99)[67]

1112223335559
(123)(123)(123)(555)[9]
(111)(222)(333)(555)[9]

1223344888999
(234)(234)(888)(999)[1]
(123)(234)(888)(999)[4]
(123)(44)(888)(999)[23]

1112345678999
(123)(456)(789)(99)[11]
(123)(11)(456)(789)[99]
(123)(11)(456)(999)[78]
(123)(11)(678)(999)[45]
(11)(345)(678)(999)[12]
(111)(345)(678)(999)[2]
(111)(234)(678)(999)[5]
(111)(234)(567)(999)[8]
(111)(234)(567)(99)[89]
(111)(234)(789)(99)[56]
(111)(456)(789)(99)[23]

ソースコード:

#define L(c)(f==13-c||b[f]!=b[f+c])
a[5];char b[14];F(int u,int n,int t,int w){int i,k,s,f=0;if(u==8191){for(i=5;i--;){putchar(i?'(':'[');for(k=0;k<13;k++)if(a[i]&1<<k)putchar(b[k]);putchar(i?')':']');}return puts("");}while(u>>f&1)f++;if(!t&&!w&&L(1)){a[0]=1<<f;F(u|a[0],n,1,1);}for(s=2;s--;){for(i=f;++i<13;)if(!(u&1<<i)&&b[f]+s==b[i]){for(k=i;++k<13;)if(!(u&1<<k)&&b[f]+s+s==b[k]&&(s||L(3))){a[n]=1<<f|1<<i|1<<k;F(u|a[n],n-1,t,w);break;}if(!w&&(s||L(2)))a[0]=1<<f|1<<i,F(u|a[0],n,t,1);if(!s&&!t&&L(2))a[n]=3<<f,F(u|a[n],n-1,1,w);break;}}}main(){for(;~scanf("%s",b);puts(""))puts(b),F(0,4,0,0);}

400 solved

There's a programming practice today, and I solved 7 problems.

It's make me feel very happy because this means that

I have solved 400 problems of POJ (peking online judge).

At the same time, I did 1000th submission to pku, too.

I'm very happy now, but I cannot express my happiness very well,

because my notebook computer is something wrong with Kanji-Henkan.

However, again, I'm very happy now!


web Gyotaku

ぶれいんふぁっく

brainf**k インタープリタを作りました。20分で完成しました。

え、何で作ったかって？だってPKUにそういう問題があったんだもの。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2849

暇な人はどうぞw


brainf**kについては以前の日記のコメント欄にちょこちょこ書いた記憶がw

pku

5日前に1000位を切ったと報告しましたが、、

早速900位を切って899位になりましたw

この辺は人が多いから1問解くだけで5人ぐらい抜かせて嬉しいw

ただいま258問、、目標の1日3問を上回って1日4問ペース。

テストは来週水曜からだしこれは結構頑張れる予感。

pku

ついにpkuで3桁順位になりましたっ

http://tinyurl.com/mirac007

あー、、ものすごく嬉しいw

次は300ACが目標ですね、日に3問ペースなので、

来月の頭には達成できるはず。がんばるんば。

grundy number

grundy numberっていうものがありまして。

以前から知ってはいたのだけど実装(=プログラムを書く)に

使えるほどには理解できてなくて。

この休み、ちょこちょこーと調べたりしてみて、

なんとなく理解した気になってたのだけど、下の問題が全然解けなくて。

あー、、やっぱまだ理解できてないんだーとか思ってたら、

やっと解けましたー、、めちゃ嬉しいw

http://acm.pku.edu.cn/JudgeOnline/problem?id=3537

問題自体はものすごく簡単です。

"n個の升目が一列にならんでいます。
AさんとBさんが交互に、好きな升に１つ。×をつけていきます。
×を3つ連続させた人が勝ち"ってゲーム。

これはn(つまり升目の数)が決まると、Aさん必勝かBさん必勝か分かるのです。

んでまぁこれはgrundy numberとかいう素敵なものを使うと

非常にあっさり解けてしまって…まぁ詳細は書きませんが。

grundy numberを勉強しようという方はこちら。

なんか今までこういう問題って"難しい"っていうイメージがあったけど、

grundy number使うと偉く簡単にできてしまうのですよ。

んー、、知識を蓄えるって大事なことだなぁ・・・

プログラミングday

結構プログラム書いたはずなんだけどなぁ、、

だいぶ頑張ったつもりなんだけどそれでも8問しか解いてないみたい。。

んー、、なんかあれかな、、

テスト前に勉強するのは、たとえどんな教科であっても

(俺の場合は)5時間が限界なように、

プログラム書くのも10問ぐらいが限界なんだろうか。。

いや、もちろん簡単な問題を選べば楽なのだけど、

それだと勉強にならんから一応ランダムで問題選んでて。

そんなことをしてるからなかなか進まんのかもしれんけど・・・w


ランダムで選んだ問題が偶然2001年の日本の問題だったのだけど、

"3次元空間上に点がたくさん与えられます。

それらを全て含むような最小の球の半径を求めてください"

っていう問題だったのです。

幾何的にいろいろがんばらないといけないのかなぁと思っていたのだけど、

解法をネットで探したら、

"とりあえず円の中心を決めて、そこからもっとも遠い点にむかってちょっとだけ動かす"

とか書いてあった。"ちょっとだけ"って計算機科学では存在しない概念なのでは？

とか思いつつもとりあえず"ちょっとだけ"動かすプログラムを書いたら通りました。

幾何の数式変形を使って厳密解を求めた人が見たら、

この解法はえらく適当に見えるんだろうなぁ…


あ、mp3デコーダ作りました。mp3プレーヤーがなくてもmp3が聞けます。

まぁmp3プレーヤーが入ってないPCとかこの時代に存在しないワケではありますが…w

今の成績

uva online judge
SUBMISSIONS:222
PROBLEMS TRIED:81
PROBLEMS SOLVED:67
(4335位)


pku judgeonline
SUBMISSIONS:261
PROBLEMS TRIED:104
PROBLEMS SOLVED:82
(2925位)


それぞれ上から、
問題を提出した回数
挑戦した問題の数
正解を出せた問題の数
です。

こうやってみるとまだまだやなー、、

1500問とか解いてる人にはまだまだかないません。。

SUBMISSIONS/PROBLEMS SOLVEDが3を超えてるっていうのもまずいよね、、

3回提出(submit)してやっと正解(accept)するぐらいってことだから、、

1回目のsubmitでacceptされるようにならないとなー。。

さてお風呂でも行ってくるか。

おはいんなさい

この前書いた新聞屋のおじちゃんは約束の日の翌日に来はりました。

なんか行き違いでもあったかな？w


ここ数日、バイトも学校もないので1日に9時間ぐらいプログラム組んでます。

その割に解けてる問題が少ないというか、学習量が少ないというか。

んー、、もちょっと効率のいい勉強方法を探さないといけないなー、、

他人のソースコード読むのがやっぱりいいんだろうか。

となるとTopCoderの過去問頑張るかなぁ…

まぁ試行錯誤の繰り返しかなー。





あれ、"試行錯誤の繰り返し"って"馬から落馬"みたいな文に思えてきた…

これってどうなんでしょう。教えてエラい人。。

haskell

俺は普段C++っていう言語でプログラミングしてるのですが、
最近haskellって言語がおもしろいと聞いてここ1週間ほど勉強(本を読んでただけ)

さっきふと実際にソースを書いてみようと思って、
本も何も見ずに書いてみました。

main = putStr "Hello, World\n"

コンパイルして実行したら

Hello, World

と表示されて感動。これC++で書くと、

#include <iostream>
using namespace std;
int main(){
    cout<<"Hello, World"<<endl;
    return 0;
}

っていう長いプログラムになるのだけど、
haskellだとたった1行でいいから気持ちいいなw

誰か一緒に勉強する人を募集中ー◎

本日のバグ。

printf("％d\n"-4*value);
気づくのに数十分かかりましたよw

top

1時ぐらいからとある問題を解いてたのです。

さっき解けたところなのです。

配列のサイズ小さすぎて1回Wrong Answer出してしまったけど。

で、同じ問題を解いた人たちの中で、

自分のプログラムがどれぐらい早いのか、とかが分かる分けです。

今回は0.040秒で解けた(プログラムの実行時間)ので、

「おお、、早い方じゃない？」と思って見てみたら、なんと最速。

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=248&category=5

まぁいろいろ書いてあるけど、

とにかくTop20のランキングの一番上にmiracという名が降臨(笑)

まぁそんなに難しい問題というわけでもないのだけど、

この問題を解いた500人の中で最速のプログラムを書けたのだなぁと思うとちょっと感動。

んー、、今日はいい気分で寝れそうですw

ユークリッドの互除法

ってのは有名なので聞いたことあるはずー、、というか中学とかでやったような(？)

一応書いとくと、「246と138の最大公約数(gcd)は？」って聞かれたときに、

gcd(246,138)=gcd(246%138,138)=gcd(108,138)=gcd(108,138%108)=gcd(108,30) ...

って求めていく方法です。(上の式でa%bはaをbで割ったあまり、って意味です。)



んでー、、今日問題を解いてて、こんな問題を見つけたのです。

icpc関係の方はtryしてみてね(笑)

http://projecteuler.net/index.php?section=problems&id=134


まぁこの問題は、与えられたp1,p2に対して、

(1000*n+p1)%p2=0

みたいな方程式をみたす最小の自然数nを求める問題になるのですが、

この方程式は中学やら高校やらで習った普通の方程式のように簡単には解けないのです。

何故かというと、、方程式の中に％、つまり「割り算のあまり」が入っているから。

まぁ詳しいことを説明すると面倒なので省略しますが、、

こういう式は変形だけで解ける式ではなくて、

nに1を入れて、割り切れたらn=1が答え。

割り切れなかったら、次はnに2を入れて、割り切れたらn=2が答え。

割り切れなかったら、次はnに3をいれて…

みたいな感じで解かないといけないのです。

いや、訂正。

つい2時間前までそうやって解かないといけないと思っていたのです。


でも上に挙げた問題、こうやって解いたらあまりに時間がかかってどうしようもなくて。

何かいい方法ないかなぁとか思って検索して見たのです。グーグル検索。

頑張って調べましたとも。日本語入れたり英語入れたりしてみましたとも。

10個ぐらいキーワード入れたところでさすがグーグル、見つけてくれました。

http://mathworld.wolfram.com/ModularInverse.html


このページの中に「ユークリッドの互除法で解けるよ☆」って書いてあって、

でも「ユークリッドの互除法って最大公約数を求める奴だよなぁ」とか思って、

今度はwikipediaを引いてみました。

http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95


そしたら何か、「拡張された互除法」とか書いてあるじゃないですか。

んー、、何か聞いたことあるような。

実はすっかり忘れてたんですが、、ユークリッドの互除法には拡張版があって、

(といってもほとんど普通の互除法と同じ)それを使えって話だったんです。

んでこんどは「拡張ユークリッドの互除法」で検索して、、

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html

こんなページを見つけて。。どうやら新潟大学のページみたいですw


これを使ったプログラムを書いたら、一番初めに載せた問題も高速に解けました、、

互除法を使う前は5分かかっても解けなかったのが、なんと0.08秒で解けるようになったというw


んー、、拡張ユークリッドの互除法の話をするつもりでブログを書き始めたのに

その前後の話で書きすぎてしまったなぁ。。

気になる方は上の新潟大学のページを読むか、、miracまで聞いてくださいw


ぐだぐだになったので無理やりまとめてみると、、

(1000*n+p1)%p2=0

みたいな方程式はO(log p2)ぐらいで解ける、と。

n=1の場合、とかn=2の場合、とかがりがりやらなくても解ける、と。

しかもそれはユークリッドの互除法をほんの少しいじるだけでできる、と。

んー、、さらにぐだぐだになった感が否めないな。。

まぁまた今度暇だったら書きます☆



前にプログラムの日記書いたときから25問ぐらい解いた形跡があるので、

目標の200問まであと156問!!　国内大会まであと31日!!

最近といた問題

projectEuler 60　　http://projecteuler.net/index.php?section=problems&id=60
実行時間が20秒かかってしまう。
掲示板見てると早くとくのは結構難しいみたい。

projectEuler 80
100以下の自然数の平方根を100桁求める問題。BigIntegerを使った。

その他
projectEuler 35,63,187,115,114,94,108
書くの疲れた笑”

よほどすごい問題以外は書かなくてもいいかなぁなんて思ってみたりw

あ、projectEuler 108 は解けたのですが、それの発展問題である110が全然解けません。

んー、、アルゴリズム悪くて時間が足りないという感じ。さてどうしたものかー。

りんく；http://projecteuler.net/index.php?section=problems&id=108

問題はすごくシンプルなのになかなか解けなくて、いい問題だと思います☆

9問ぐらいといたのであと181問！(多分w

今日といた問題

projectEuler 94
各辺の長さが整数の、”ほぼ正三角形”のうち、面積も整数のものを求める問題。
12秒ぐらいかかるけどまぁ1分以内なのでOKかと。
場合分けとかして無駄な計算減らしたけど、まだまだ減るのだろうな、、
「正解者が見れる掲示板」があるのでそれを見て勉強したいと思いますw
http://projecteuler.net/index.php?section=problems&id=94

projectEuler 108
ちょと説明しにくいから問題は下のURL見てくださいな。
問題も式も簡単だからと思って単純に実行したらなかなか終わらず、、
いろいろ式を変形してたら別の問題に帰着できたのでそれをときました。
やりごたえのある問題を求める人にはいいのではないだろうか？
http://projecteuler.net/index.php?section=problems&id=108

通算10問。あと190問！笑”

今日といた問題

projectEuler 125 ->これはハマってしまったけど良い問題。おすすめ。
http://projecteuler.net/index.php?section=problems&id=125

projectEuler 123 ->BigIntegerの練習が出来たw以降URL略。

projectEuler 116,117 ->spojのpcv3の1問目とその類題。

projectEuler 65 ->分数の分数の分数の…ってのeを求める問題。面白かったw

projectEuler 58 ->飛び飛びの値を素数判定する必要があったので、
そういう場合にはどうしたらいいのかを考える練習になった。
あとdouble使ったら桁落ちして答えが1つ違ったり笑”
http://projecteuler.net/index.php?section=problems&id=58
−>やっぱ勉強になるやつはURL載せることにするw

projectEuler 91 ->51x51の座標の上に直角三角形が何個作れるか、という問題。
簡単な(といっても俺はハマったけど)幾何問題と言うことで勉強になりました。
http://projecteuler.net/index.php?section=problems&id=91

projectEuler 77 ->素数の和5000通り以上で表せる最小の数は？という問題。
例えば整数10なら「2+2+2+2+2」「2+2+3+3」「2+3+5」「3+7」「5+5」の
計5通りで表せるのだけど、じゃぁどれぐらい大きな数なら5000通りで
表せますか？ということ。答えに相当驚きましたw
プログラム的にはよくある手法を使うだけなので暇な人はどうぞw

てかこれだけ大量に書いたけど誰か読むのかな、、自分用ログってことでw

パソコン起動した時刻と見比べたら全部で２００分ぐらい、、１つあたり25分かぁ
ちょっと…というか難易度の割にかなりかかってるなぁ〜(="=;;)

合計：2008/05/18から8問。