FrontPage - PukiWiki: 2012年度夏学期「実践的プログラミング」へようこそ
授業について 「実践的プログラミング」は教養学部前期課程で開講されている。全学自由研究ゼミナールです。 履修希望の方はUTAS等をご覧ください。2020年夏学期は月曜5限にオンラインで開講されました。 内容に興味がある方はPDFの資料等をご覧ください。(授業で扱う範囲はこの一部で、また細かくは差異があります) ウェブページについて 現在CMS変更に伴う更新作業中です。過去のページも引き続き閲覧可能です。 なお、国際大学対抗プログラミングコンテスト(ICPC)については、現在は多少状況が変化していますので、過去のページをご覧の際はご留意ください。 ACM-ICPCは、2018年12月までにはACMの後援が外れて、ICPCとなりました。 2020年度は、COVID-19の影響で、各チーム分散した環境で国内予選が行われています。教員による「監督」制度も適用されていません。 なお、来年度以降は未定
Sticks(10) - カメヲラボ
最短コード250B 270byteあたりからは、ロベールさんと私でじわりじわりと削り合い。ちなみに、前回までで紹介しているコードは、はてな用に私が新しく書きなおしたものなので当時のコードとは違う部分もある。どんなインプットでも通るコードというのは、実は260byteくらいまでしか短縮することが出来ない。それ以上縮めるには探索時間やメモリを犠牲にしていかなければならないのだ。 260byte程まで縮んだところで、ロベールさんがTLE(Time Limit Exceed)に掛からない程度に探索ループを書き換え254byte。そして私がそこからさらに短縮して251byte。 L,F,*I; c(n,l,p,j){ --I[p]; for(j=l-=p;F*j;--j)I[j]&&c(n,l,j); for(j=F=--n?F:0;!I[j];)--j;l||c(n,L,j); ++I[p]; }
Sticks(9) - カメヲラボ
意外と読める超短いコード 昨日のコードをさらに短くすると以下のようなコードになる。ここまでくると変数名を一文字にした方が逆に読みやすい。え？読みにくい？そうですか..(´ω｀) int L,F,*I; c(n,l,p,j){ --I[p]; F=n?F:0;for(l-=p,j=l<p?l:p;j;--j)F*I[j]&&c(n,l,j); for(j=50;!I[j];)--j;l||c(n-1,L,j); ++I[p]; } main(s){ for(;s;L&&printf("%d\n",L-1)){ int w[51]={s=F}; scanf("%d",I=w); for(;w[0]--;++w[L],s+=F<L?F=L:L)scanf("%d",&L); for(L=F;F;++L)s%L||c(s/L,L,F); } } if文の代わりに&&や||を使うのはコード短縮の常套
Sticks(8) - カメヲラボ
準備 コードを短縮するには、通常のプログラミングで「だめ！」と言われていることをやっていかなければならない。ここからはプログラミングというよりパズルの問題。いかに少ない文字数で、同等の処理をさせられるか。 まず、手始めにシンボル名をすべて一文字にする。 また、配列の初期化はどうしても文字数が増えてしまうため初期化の代わりに新しく宣言しなおすことにする*1 改行コード・空白を省くと330byte程度。まだまだ短縮可能だ。 int L,F,*I; c(n,l,p,j){ --I[p]; if(n==0)F=1; if(!F){ if(l-=p){ for(j=l<p?l:p;j>0;--j) if(I[j])c(n,l,j); } else { for(j=50;!I[j];)--j; c(n-1,L,j); } } ++I[p]; } main(s,b,m){ for(;s;printf("
Sticks(7) - カメヲラボ
計算量を減らす ちょっとした演算でも数十万回呼ばれる可能性があるのであれば、それなりに時間がかかってしまう。演算回数を減らす努力は、再帰の仕組みを真面目に考えるきっかけになり、コードはスマートになっていく。そして、最終的にはコード短縮につながる。 昨日のコードで無駄な部分は、in[n]のデクリメント・インクリメントを2箇所で行っている点。再帰なら一度ずつで済むはずだ。 ということを考えて修正すると、700byte弱になった。シンボル名を一文字にして改行コードを除けば半分程度になるだろうから、これを短縮すればおそらく300byteくらいにできるだろう。 int length,finish,in[51]; check(count, len, plen) { int j; --in[plen]; if(count==0)finish=1; if(!finish){ if(len-=plen){
ラベルは無駄やの - Cozy Ozy
とりあえず変数を減らしていく inputの値は最大64個、それにあわせてlabelも64個。さらにinputはソートしなければならないとなれば、最短コードを目指すには無駄が多すぎる。簡単な方法はlabelを使わないことだが、inputを0で潰す方法は再帰コードで書くとbacktrackし辛い(一つ余分に変数が必要になる)。 この問題のテストケースは、inputの値が最大でも50と問題に書かれている。ということは、inputの値を配列番号にしてその数のカウントをデータにしてしまえばスッキリする。たとえばこれまでの例で使用したinput 15 11 8 8 8 4 3 2 1は、新しい配列(in[51])を使えば in[15]=1, in[11]=1, in[8]=3, in[4]=1, in[3]=1, in[2]=1, in[1]=1 それ以外のin[n]はすべて0再帰する場合1引いて、b
Sticks(5) - カメヲラボ
サンプルコード とりあえず、今まで書いたことを元にそのままコードを書いてみることにする。それなりに読める形で1100byte強。これを最終的に250byteほどに短縮するわけだが、このままではどう考えても不可能だ。基本的なアルゴリズムは変えずに、まずデータ構造をシンプルにしなければならない。 以下はソースコードベタ貼りなので、興味ない人はスルー 001 int input[64],label[64],length; 002 int n;//inputの個数 003 004 int check(int count) 005 { 006 int i=0; 007 if(count!=0) 008 { 009 while(label[i])i++;label[i]=1; 010 if(!search(length-input[i],i+1,count))label[i]=0; 011 } 012
Sticks(4) - カメヲラボ
探索イメージ 探索方法がイマイチ掴み難いという人もいるかもしれないので、ちょっと図を描いてみた。 ポイントを整理しておくと、 (1)データを降順にソートしておく。 (2)値の大きい順(=配列の前から順)に、stickの長さ(=length)から0になるまで値を引いていく。同時に、使用した値にはラベリングしておく。 (3)長さ0になったら、lengthを元の長さにセットしなおして(2)を再実行 (4)失敗したらバックトラック (5)長さがlengthのstickがsum/length本できれば成功。 DFSの肝は、 最も新しくラベリングされた点に隣接する点を探索するというところだ。つまり図の中では、探索を左側から順に行うことになる。一旦15-4-...と探索を始めたら、「どうやってもムリ！」というところまで探索してからバックトラックしていく。今回の解は15-3-2-...なので、図の①〜③は
Sticks(3) - カメヲラボ
ラベリング 前回のような数字のリストを作るために、inputの各値にlabelをつけることにする。たとえば、入力値input配列を input={ 15, 11, 8, 8, 8, 4, 3, 2, 1 };とすれば、ラベルは label={ 0, 0, 0, 0, 0, 0, 0, 0, 0 };と、最初はゼロにセットしておく。 もし、15-4-1とリストを作れば、15,4,1に対応するラベルを1に書き換える。 input: 15 11 8 8 8 4 3 2 1 label: 1 0 0 0 0 1 0 0 1 このようにして、すべてのlabelを1にすることができれば成功だ。 ラベリングの手順は前回の通り、降順にソートされたinputを、先頭から順に調べる、目標とするstickの長さより短ければラベルリング。stickが完成したらまた先頭に戻り、ラベリングされていない値で同じようにラ
Sticks(2) - カメヲラボ
基本アルゴリズム 前回のような簡単なInputであれば、少々無駄な探索アルゴリズムでも解を求めることが出来る。しかし、PKU1011のテストケースはそこそこ厳しいので、下手なアルゴリズムだとTLE(Time Limit Exceed)要するにタイムオーバーとなる。 とりあえずプログラムを作ってみるのも良いかもしれないが、この手の探索にはDFS(Depth First Search)というものがある。inputの各値を頂点と考えて、最初の点から順番につなぎ木(リスト)を作っていく。 前回までの例は簡単すぎて説明にならないので、次のようなinputを用意する。 8 3 8 15 2 11 4 8 1この9つの値の合計(sum)は60。最大値(max)は15だから、60の約数から15未満の数を省いた、15,20,30,60(=length)について順に調べればよい。 まず、lengthが15にな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
1080 -- Human Gene Functions
++knowl;
JudgeOnline 1012 (5) - とくにあぶなくないRiSKのブログ
JudgeOnline 1012 (4) - とくにあぶなくないRiSKのブログ
2006-02-16
2006-02-15
JudgeOnline 1012 (2) - とくにあぶなくないRiSKのブログ
2006-02-13
http://d.hatena.ne.jp/Ozy/20060419
http://www.4dm.org/PKU/1012.htm