ライトニングまさかり

その馬肉で和同開珎の刺繍をしよう

タイトル付け忘れたので今適当につけます

プロラボアドベントカレンダーほげ日目のほげです。アレの記事への張り付け方わかんないです。

 

自己紹介をすると、某IMAGINE THE FUTURE大学に進学した@kusohako です。@ichigo_o_re に書けよと脅されたので書きます。

 

記事に書く内容をtwitterで募集したところ、code festivalのショートコーディング大会である短縮王について書いてほしいといわれたので書きます。

 

ショートコーディングに詳しくない方のために説明しておくと、競技プログラミングの解答コードをできるだけ短くするという問題です。短縮王はAtcoder上で行われました。ページはこちらです。
http://code-festival-2015-shortcoding.contest.atcoder.jp/

 

私がcode festivalの事前公開問題に気づいたのは多分本選の2日前の夜くらいだったように思います。twitterを眺めていたら問題文が話題になっていました。キルミーベイベーは神。

 

A問題は1行目にデータの数nが与えられて、続くn行に1つづつ整数が与えられまして、2行目に与えられたデータ(つまりnの次の入力)がn個のデータの平均の半分以下だったら"Fail",そうでなければ"Pass"を出力する問題です。

 

事前に公開された問題はAnarchy Golfで公開されたんですが、入出力のフォーマットがすごいつらかったうえに本番では変更されるようなことを聞いたので、Atcoder上でコンテストが公開されるまでは本気を出す必要ないかな~とか考えていました。

 

本選会場で@orisano 君や@ichigo_o_re 君に挑発されたのでとりあえずその場で二人のスコアを抜きました。

 

短縮王の開始はcode festival本選の後だったので、本選でとても疲労しているコンディションで始めることになりました。

 

私がショートコーディングするときは、まず普通にAcceptするコードを書いて、それから短くしていくようなスタイルなので、この問題も例にもれず最初にコードを書きました。多分こんな感じでした。

n,s,f,a;
main(i){
scanf("%d",&n);
for(i=s=0;i<n;s+=a){
scanf("%d",&a);
f=i++?f:a;
}
n=!puts(n*f*2>s?"Pass":"Fail");
}

このコードの時点で空白や改行を削ると109byteですね

 

この段階で何やってるかわかんないしなんで動くのかもわかんないと思う人もいると思うので、C言語の仕様を簡単に箇条書きで説明しますと、
・scanf,printf,putsはstdio.hをインクルードしなくても使える
・変数や関数の宣言を省略するとint型と判断される
・x?a:bという演算子は,xがtrueの時aを,falseの時bを返します

 

さらに、AtcoderのCでは通常main関数は0を返さなければREになってしまうのですが、グローバル変数に非定数式で0を代入するとmainの戻り値が0になります。AtcoderC言語のputs()の戻り値は0でないです。

 

この辺の知識はまあ常識なのでわかる人はこの辺まで読み飛ばしてもいいと思います。コードは読めると思うので解説は省略します。

 

ここから、とりあえずfor文を削りたいなーと思ってmain再帰を使ってみたコードがこちらになります。

s,c,t;
main(n){
scanf("%d",c?&t:&n);
s+=~c--?t:-t*n*2-t;
t=n--?0*main(n):puts(s<0?"Pass":"Fail");
}

これで94byteですね

 

コードの解説をしようと思ったのですが思い出せない上に読むのが結構だるいので各自で勝手に読み取ってください。

 

このコードを提出した後は会場にいる人とご飯を食べたりゲームしたりしてました

ホテルに着いた後さあ本気出すぞと思いしているといつの間にか日付が変わっていて、喉が謎の痛みを訴えていました。風邪の初期症状です。

 

とりあえずA問題でC言語1位を取れたので寝ることにしました。そのコードがこちらです。

s,f;
main(n,t){
for(;~scanf("%d",n?&t:&f);)s=n--?s+t-2*f:0;
s=!puts(s<f?"Pass":"Fail");
}

85byteです。やっぱfor文使った方が短かったです。

 

2日目に起きると喉が痛くて体もだるかったです。完全に悪化しました。罪深い。

 

短縮王の評価方法を見ると、解いた問題数が多い方がいいらしいのでとりあえず問題を埋めてからコードを短縮することにしました。順位表を見るとわかる通り、A問題以外は完全にクッソ雑魚だったので風邪のせいにしたいです。

 

BはUnion Findするだけだったんですが、戻り値を省略しようとしたら戻してくれなかったりしたのでブチギレながらreturn文を書きました。

Cは全探索を適当に短くしました。

Dを普通に通すのがとてもだるかったです。だるすぎて短縮するのあきらめました。C++でゴリ押しました。

 

短縮王終了した後に解説が聞けたらしいんですけど、解説会場の告知がとてもわかりづらかったので行けませんでした。悲しい。

 

A問題C/C++部門で1位だったんですが、他の全ての部門1位は表彰されていたのに私だけ表彰されなかったのでとてもつらい思いをしました。

 

あとA問題の想定解は79byteでした。くやしい。

 

ICPC国内予選参加記

今年もICPCに出ました。

相方は@secondheaven君(以下セカ天君)と@tolro_800君(以下T君)です。

 

この参加記を読むにあたって事前に知っておいてほしいことをまず書いておきます。

・私が所属する研究室から参加する

・使用するPCはT君のノートPCと前に決めておいた

 

では書き始めて行こうと思います。

 

 

PM4:10

今日の4限は体育だったので着替える間もなく研究室へ。

適当に研究室のPCで暇をつぶし始める。

 

PM4:25

おかしい。まだセカ天君とT君が来ない。

おかしい。おいしい。おにぎりがおいしいんだな。

 

PM4:30

IPCPに出る時はね

誰にも邪魔されず自由で

なんというか救われてなきゃあダメなんだ

独りで静かで豊かで・・・

 

PM4:40

ようやくセカ天君とT君が来たのでここで初めて

PCの電源を入れる。寺生まれってすごい。

 

PM4:50

LANがつながLANので結局研究室のPCを使うことに。

この辺でコーチの先生が問題を印刷して持ってきてくれる。

つまり開始直後の20分間をどぶに捨てている。つらい。

 

PM4:55

ようやくコンテストページにたどり着いたので紙コーディング開始。

私は最初CとDを眺めて解法を考えていたので、

その隙にどちらかがAかB通してくれるだろうと踏んでいたが

なぜか二人とも紙コーディング開始。誰もPCに触っていない。なんだこれ。

 

PM5:00~

セカ天君がAをPCで書きはじめる。がしかしvimに苦戦。難航する。

 

PM5:20頃

セカ天君のコーディングが終わらない。バグがやばそう。

さすがに開始50分で0完はやばいのでA代わってもらう。この時初めてAを読む。

セカ天君にCを任せる。

 

PM5:30

問題の勘違いなどがありながらも無事sampleが通る。やったぜ。

そのまま提出。1完。Dにとりかかる。

 

PM5:40

T君がBをPCで書きはじめる。なんかCの方針に気づく。再び代わってもらう。

 

PM6:00

紙コーディング難航。T君もバグにさいなまれる。つらみMAX。

 

PM6:30

紙コーディングが一息ついたのでT君に代わってもらって

Cのコーディングを開始する。打ち込みがちょうだるい。

 

PM6:40

打ち込み終わるもバグ。つらい。

 

PM7:00

くそはこは激怒した。必ず、かの邪知暴虐のバグを除かなければならぬと決意した。

くそはこには原因がわからぬ。くそはこは、高専のコミュ障である。

 

PM7:10

T君と交互にデバッグを繰り返す。

なんかvectorあたりでバグが出る。やばいなぁ~まだ1完だなぁ~

 

PM7:15

ようやくバグの原因がわかる。

なんと今までgccコンパイルしていた。これには流石のプロラボメンバーも苦笑い。

笑えないので必死になる。

 

PM7:20

コンパイル通るも普通にバグ。つらすぎである。

T君の方もコンパイル通るがバグる。頭がフットーしそうだよおっっ

 

PM7:30

この世で最強のものは無・・・

その無より転じて1完を拾う・・

それが無想転生!・・・

 

 

 

 

というわけでICPCお疲れ様でした。

 

adveなんとか

この記事はadveなんちゃらの14日目の記事です。

なんかいい感じに暇だったので書きます。

 

adveなんちゃらに有用な記事が全くないのでICTのレベルの低さが垣間見れますね。

 

ところでICTって何の略ですか?

私はI(イクラ)C(ちゃんと)T(タイコおばさん)だと思います。

 

・はじめに

 

adveなんちゃらから来た人用に自己紹介しておきます。

 

kusohako(@kusohako)

久留米高専プログラミングラボ部所属

ICT委員会には所属していませんしこれからも所属することはありません←重要

愛より暇つぶしが欲しいです。お金でも可。

最近ブログとか書くことに向いてないことをやっと自覚しました。

 

では今回私がこの記事で紹介するのはこちらです。

 

f:id:kusohako:20131214031531p:plain

 

ゲーム作りました。

タイトルは画像の通り「エクストリーム2人組作成アクション」です。

 

・ゲーム作成の経緯

 

時は20XX年、世界は二人組作成の炎に包まれた。

ぼっちは阿鼻叫喚し、瞬く間に奇数人のクラスが地獄絵図となった。

そんな荒れ果てた世界を歩く、一人の若者の姿があった。

彼こそがぼっちに救済を与える者、

奇数だと思ってたら存在感がなくて気づかれないだけのぼっちkusohakoであった。

 

みたいな感じで深い悲しみを背負って生きていたのですが

別にそれとは関係なくゲーム作りたいと思っていました。

10月22日(火曜日)に部活でゲーム作りたいって言ったら後輩が乗ってきました。

11月3日に文化祭があるのでそれまでに作っちゃおうという話になりました。

翌日にクラスメイトを誘って3人で作ることになりました。罪深い。

 

・イカれたメンバーを紹介するぜっ!!

 

万年冷え性のkusohako!!!!

CG合成疑惑のきつねうどん(@shouhei881)!!!!!

なっちゃんをババア呼ばわりしたやいの(@rorikakke)!!!!!!!!!

以上だ!!!!!!!!!!

 

・ゲームの内容

 

このゲームは二人組でのプレイを前提としています。(重要)

プレイ前から二人組作成は始まっているんだよ!!!!!!

 

ゲームは探索フェイズと戦闘フェイズの2つで構成されています。

探索フェイズでは、プレイヤーは互いに別のフィールドでアイテムを集めます。

一方のプレイヤーがアイテムを取得すると、もう一方のプレイヤーの能力があがります。

つまり自分が頑張るほど相方が得をするということです。人間関係に似ていますね。

探索フェイズの制限時間は3分くらいです。

これが探索フェイズの様子です。

f:id:kusohako:20131214032641p:plain

 

チャチい。あふれる手抜き感が逆にすごく凝っているように見えないこともない。

 

探索フェイズが終了すると、次は戦闘フェイズに入ります。

プレイヤーは一つのフィールドに集められ、そこにいるボスっぽい何かと戦います。

f:id:kusohako:20131214032744p:plain

とってもシュール。背景とは何だったのか深く考えさせられる。

ボスを倒すとゲームクリアになります。やったね。

 

一見協力ゲームに見えるようで実際は

「俺がこんだけ頑張ってやったからその分ちゃんと働けよ( ◠‿◠ )」

という圧力をかけあう友情破壊ゲームです。

私はこのゲームを広めてもっとぼっちを増やしていこうと思います。

 

・開発風景

skypeにて

~~~~~~~~~~~~~~~~~~~~~

やいの「漢字コーディング、いきま…せん」

わたし「日本語名つけたら殺す」

わたし「末代まで呪う」

やいの「お、おう」

~~~~~~~~~~~~~~~~~~~~~

やいの「これpublicにしていい?」

わたし「こっちならいいよ」

~~~~~~~~~~~~~~~~~~~~~

わたし「やいの起きてる?」

やいの「寝てる寝てる」

わたし「そっかー」

~~~~~~~~~~~~~~~~~~~~~

わたし「ビームの歴史を感じる」

きつねうどん「たしかに」

やいの「砲塔が孕んだ」

 

・開発の反省点

今回のゲーム開発から見えてきた反省点を書いていきます。

 

1.プロジェクトは余裕をもって始めましょう。

 

開発開始から十日くらいしか時間がなかったので

授業受けながらコーディングとかするくらいデスマしてました。罪深い。

先生の生暖かい目がつらかったです。でも放課後とかはめっちゃ遊んでました。

 

2.ちゃんと予定表を作りましょう。

全て行きあたりばっかりな開発だったので作業効率がクッソ悪かったです。

きつねうどん君はコーディングをしたがっていたのに

結局素材集めしかやってもらっていないので、

後輩をいいように雑用に回す性格の悪い先輩たちの図になってしまいました。ごめん。

やいの君はなんかマイペースに敵のAIとか作るのを任せてました。

結局最初にまず何作るかとか何が必要かとかちゃんと決めて分担しないとだめですね。

途中何もできない時間とかできてしまったしその辺のノウハウ知ってる人いたら教えてください。

 

3.よく考えて作りましょう

このゲームの7割以上は実装中に考えられた仕様でできています

構想とは何だったのか

あとこのゲーム二人用なのでぼっちな私にはデバッグが困難でした。

このうっかりさんめ

 

・まとめ

こんな感じのノリでプロジェクトを立ち上げても締切さえあれば何とかなります。

逆に締切がなければプロジェクトは炎上すると思いました。

とってもためになる、いいプロジェクトだったと思いました。

(小学生並の感想)

Topcoder SRM585 Div2

doubleはクソ。

異論は認めない。

 

-easy(250)

int cnt = 1;

for(int i=0;i<sec.size()-1;i++)cnt += sec[i]>=sec[i+1];

return cnt;

 

-medium(500)

long long n = pow(2,h+1)-1;

n = (n+2)/3;

return n;

 

hは引数。

doubleの誤差で1行目の-1がなかったことにされて誤差死。

hが53,55,57,59の時に死ぬ模様。

-1をなくして2行目でn=(n+1)/3って書くか

最初から n = 1 << (h+1) って書くかすればよかった。

なんにせよ本来なら解けていたし深い悲しみを生む。罪深い。

 

-hard(1000)

幾何っぽいと体が拒否反応を起こす。泣き寝入り。

とりあえず全探索っぽいものを書くものの最大ケースでは間に合わないし

そもそもsample一つも合わない。撃沈。

 

ICPC国内予選レポート

そういえばもうすぐセレクトバグの季節ですね

うちわで鯉の滝登りを使っていたころが懐かしい

 

チームメイトはodiak君とi_l君でした

 

とりあえず問題をざっと眺める。

Aは解けるけどめんどくさそうだと考えてi_l君に投げた。

自分はBを神コーディング開始。罪深い。

Cは読まずにodiak君に投げる。まあたぶん余裕でしょう。

 

ライフガードっておいしいよなぁと考えながらトイレまで3往復した。

ようやく神コーディング終わって状況を聞いてみるとAバグっていて詰まっていた。

この時点でAのケースを読めばすぐかけるコードだったことに気づく。罪深い。

でももうすぐ終わるとのことだったのでDを読んでみる。だるい。

Eを読んでみる。幾何はちょっと書けない感じ。

Fを読んでみる。あっこれわかんないわ。むり。

 

仕方なくDの実装を考える。解答自体は簡単なDPのはず。

問題は数をらせん状に並べること。配列を使うには初期位置とかめんどい。。。

どうすれば・・・?

 

とりあえずA通ったと聞いたのでBを実装する。

神からのコピペに失敗したり誤読があったりして20分くらい手間取る。

あと提出の仕組みわかってなくてそこでも10分くらい手間取る。罪深い。

ようやくBを通す。

その間にCは構文解析っぽいとのことなのでodiak君がCをi_l君にパス。

なのでodiak君にはDのらせん状に並べる部分をお願いする。

 

ふと順位表を見ると我が校のガチチームがまだ1問しか解いていない。

これはもう出場決まったなとか思いつつDの解答部を神コーディングはじめる。

 

その神コーディングがすぐ終わったので、

自分なりにらせん状に数字を並べる方法を考える。

そうだmapを使おう。pair<int,int>が好みのタイプである自分ならたぶんかける。

そう思ってすぐにmapを使ったコードを考える。あ、割といけそう。

i_l君がCを通す。とりあえず3完達成。

 

せっかくなのでodiak君にDのお願いした部分を任せてみる。

その間に先ほどのコードを煮詰める。

神コーディングがひと段落したので時計を見るとCを通してから結構経っている。

odiak君に申し訳ないが代わってもらう。実装開始。

 

黒いバグが鳴いている・・・ 

動いちゃダメ!バグが出ちゃう!いい子だから動かないで。

デバッグを大事にしないやつは大嫌いだ!

あ!ババ様!赤いerrorが見えます!どんどん増えているみたい。時間を食うんだわ!

ふん、kusohakoというのかい・・・贅沢な名だね、今日からお前の名前はクソだ!

動け、動け、動いてよ!今動かなきゃ、今やらなきゃ、みんな落ちちゃうんだ!

もうそんなのやなんだよ!だから、動いてよ!!!!

桂ァ!あとバグ何個ォ!?(ドボォ

----------------------------------------予選終了----------------------------------------

 

結局バグって死亡。その間にガチチームが4完を決める。おうふ。

まあでも0WAなので結構健闘したと思いこんだ。

odiak君とi_l君ごめんなさい。

 

みりん書いてんだけど臨界点

最近よく爆発するので盆踊りマシーンを建造した。

 

実は前から言おうと思っていたのだが、

「前から言おうと思っていた」って硫黄っていうよりモリブデンっぽい。

私は「右から左脳と思っていた」のほうが好きだ。

 

物覚えが紫色の綿棒みたいな虚数だった。

割り箸を武器にするのはありえないと思う。

 

/**/

/*/

//*/

赤い/だけでコメントアウトを切り替えられて罪深い。

Topcoder SRM580 Div2

斧はナブラが使いやすいのでさっさとパネルを手に入れて閃くべき

 

-easy(250)

つまるところ難読。読解に時間かかって200点を逃す。罪深い。

みっともなく翻訳サイトを3つ頼る。

ぶっちゃけ全探索やったら通った。

かぶってる領域を探すのもめんどくさかったのである時間ごとにペア判定やった。

いちいちそんなことするより領域からどうのこうのした方が早い。

 

-medium(500)

easyとだいぶ似ていたので300点とれる。うれしい。

これも座標圧縮して全探索やるだけ。

やるだけという名のハラスメントになりそう。

 

-hard(1000)

なんか文字列がどうのこうのめんどくさかった。鑑賞してた。

後で考えてみれば案外解けそうだった。