AOJ 0595 Schedule
何を今更と思う方もいると思いますが、AOJ0595をErlangで解いた(未確認)ので記事を書くことにしました。
追記(4:35) JOI 2013-2014 予選 問題文・採点用入出力・解説の入出力例に対してすべて正解していました。
Erlangを書くのが非常に久しぶりだったのですがとても楽しくかけました。
問題概要に関してはAOJを見てください。
以下コードです。ぶっちゃけ普段からErlangを書かないのでErlangとして良いコードかはわかりません。
-module(aoj0595). -export([main/0]). main() -> _ = io:get_line(""), S = string:strip(io:get_line(""), right, $\n), io:format("~p~n", [schedule(S, true, false, false)]), init:stop(). schedule(S, J, O, I) -> ( schedule(S, true, true, true, J, O, I) + schedule(S, true, true, false, J, O, I) + schedule(S, true, false, true, J, O, I) + schedule(S, true, false, false, J, O, I) + schedule(S, false, true, true, J, O, I) + schedule(S, false, true, false, J, O, I) + schedule(S, false, false, true, J, O, I) + schedule(S, false, false, false, J, O, I) ) rem 10007. schedule([$J|_], false, _, _, _, _, _) -> 0; schedule([$O|_], _, false, _, _, _, _) -> 0; schedule([$I|_], _, _, false, _, _, _) -> 0; schedule(_, J, O, I, PJ, PO, PI) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0; schedule([_], _, _, _, _, _, _) -> 1; schedule([_|L], J, O, I, _, _, _) -> LL = length(L), case get({LL, J, O, I}) of undefined -> Ret = schedule(L, J, O, I), put({LL, J, O, I}, Ret), Ret; Memo -> Memo end.
再帰はパターンマッチとか使えるととても書きやすいですね。
Erlangにはプロセス辞書という仕組みがあってメモ化するのも非常に簡単です。
プロセス辞書にキャッシュを入れるのは正しいことなんでしょうかね。。。
追記(3:14):
公開してすぐにもっとシンプルに書けることに気が付きました。Blogに公開することは偉大ですね。
-module(aoj0595). -export([main/0]). main() -> _ = io:get_line(""), S = string:strip(io:get_line(""), right, $\n), io:format("~p~n", [schedule(S, {true, false, false})]), init:stop(). schedule(S, State) -> Bool = [true, false], Cand = [{J, O, I} || J <- Bool, O <- Bool, I <- Bool], lists:foldl(fun(X,Acc) -> Acc + schedule(S, X, State) end, 0, Cand) rem 10007. schedule([$J|_], {false, _, _}, _) -> 0; schedule([$O|_], {_, false, _}, _) -> 0; schedule([$I|_], {_, _, false}, _) -> 0; schedule(_, {J, O, I}, {PJ, PO, PI}) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0; schedule([_], _, _) -> 1; schedule([_|L], State, _) -> LL = length(L), case get({LL, State}) of undefined -> Ret = schedule(L, State), put({LL, State}, Ret), Ret; Memo -> Memo end.
コードの概要
書いていることは至ってシンプルでJ君,O君,I君の今日と前の日の状態を持って,
それをパターンマッチによって遷移できない状態を除外しているだけです。
あり得る組み合わせだった場合、次の状態に遷移します。
遷移できる次の状態がたかだか8通りなのですべての遷移を試すコードになっています。
あとは引数によって状態が変わらないのでメモ化することができます。
終わりに
Erlangっぽいコードが書きたいなら競プロするな👊って感じですね。
第26回高専プロコン競技部門 反省会場
この記事はICT Advent Calendar 2015の7日目として書かれました。
はじめに
ブログの更新は1年ぶりになります、@orisanoです。
去年のICT Advent Calendarぶりの投稿になります。
今年はいろんなイベントや大会に参加しましたし、残り短いですがまだまだ参加します。
今年参加した中で個人的に最も注力したのが"""高専プロコン"""です。
読んでると思われる層の人は知っていると思うので詳しくは説明しません。
今年は競技部門に参加してきました。そのことについて書こうと思います。
高専プロコン競技部門と僕
今回の高専プロコン競技部門(以下競技部門)のチームは進捗優先探索という名前で
- 僕 (専攻科1年) (リーダー兼コーダー)
- レオきゅん (4年) (コーダー)
- じんくん (2年) (コーダー)
- 1年生2人
という構成で役割としてはリーダー(初)のような物をやっていました。
ちなみに僕は競技部門に参加するのが今年で4回目になります。
どの大会も思い出深いですね。(サイコロは絶対にユルサナイ)
初動
今年の競技部門の課題は「石畳職人Z」というタイトルで、
概要としては「全部埋まるかどうかわからないジグソーパズルを出来るだけ埋めよう」というものでした。
詳細が知りたい方はこちら
問題が公開されてすぐに練習場の作成にとりかかりました。
去年と違って競技者として参加するというものあって公開しませんでしたし、内部的にも活用しませんでした。
練習場の作成を通して、ルールの理解や曖昧な部分が理解できるのでとてもおすすめです。
練習場の作成が終わった頃から簡単なサーベイをしたり、チームメンバーに対して
探索アルゴリズムの概要をレクチャーしたりしていました。
それと並行してSiv3Dを用いたビジュアライザー兼手動ソルバーなどを作りました。
(本当はこの辺から一年生に対してちゃんと指示を出したりすべきだったんだろなぁ)
6~8月
土台が出来上がってきたので、ソルバーの実装ににとりかかりました。
非公式練習場(以下練習場)に提出を始めたのこの時期からです。
(練習場自体は5月くらいにはできていて、当時では信じられない解が提出されていた)
今回モチベーションが保てたのも練習場の存在があったからと言っても過言ではないでしょう。
練習場を公開していた@mecha_g3さんには感謝しかないです。
この頃は僕のソルバーはボロボロで全然良い解が出ずとてもつらい思いをしていました。
一方じんくんのソルバーがそれなりに良い解を出しており、評価関数の重みなどを参考にしたところスコアがかなり改善したことを覚えています。
じんくんありがとう。。。
KNCTが練習場にたくさん発生していて上位を独占していた頃でもありました、この時はひたすらKNCT爆発しないかなとか不穏なことを言っていた気がします。
KNCT多すぎてどこの高専かわからないよ!!!!!!!!!!!!いい加減にして!!!!!!!!!!!
— おりさの (@orisano) 2015, 7月 2
KNCT、ランキングに5人くらいいるしやめてくれ
— おりさの (@orisano) 2015, 7月 2
KNCTと名乗ることを法律で禁じよう!(過激派)
— おりさの (@orisano) 2015, 7月 5
競技練習場でKNCTと名乗るやつを爆発させるボタンください #procon26
— おりさの (@orisano) 2015, 7月 6
最終的には僕もKNCTを名乗っていました。
KNCTって名乗ってましたが、これは陰謀によりOkNCTのOがなくなったためです() #procon26
— おりさの (@orisano) 2015, 10月 13
ブレイクスルーとして高速化のために制限をかけたソルバーが
良いスコアを出すようになり、練習場でほとんどの問題で1位になりました。
8月の後半(?)からTMCITの攻撃が始まって、競争が激化します。
がスコアが全然改善せず、モチベーションがどんどん維持できなくなっていきました。
進捗管理も疎かになりました。ほんとにダメですね。
9月~
夏休みの期間はインターンシップで株式会社ABEJAさんとDeNAさんに行きました。
合わせて3週間ほどでしたがとても良い経験になりました。
その間は開発お休みしていました。( ◞‸◟ )
ここからアルゴリズムベースの改良は少なくし、高速化や提出ツールの作成などに入りました。
tcmallocなど修正無しで高速化が見込めるツールの導入や、
Instrumentsなどを見ながらボトルネックを探して高速化していました。
また_GLIBCXX_PARALLELで楽して並列化を行いました。
これでそれまでの4倍程度の速度が出るようになりました。やったね。
提出ツールの作成にあたって、チームの中で僕が一人だけ
Macユーザだったのでマルチプラットフォームを意識しなければいけなくなりました。
ISUCONのために勉強していたgolangで書きました。クロスコンパイル最高!
問題の1位取得数は6個で1位だったので比較的心おだやかに長野へ向かいました。
本番
長野に到着してからはどうやってTMCITの人を闇討ちするかを考えていました。いませんでした。
初日は練習と1回戦があったのですが練習の様子を見ると
自動で問題取得、解の提出ができないと困るということが分かりました。
空いた時間を使って取得、提出の流れを自動化してくれるツールを作りました。これが1回戦で非常に役に立ちました。
1回戦は第2試合だったのですが、1位、1位、2位と最終成績2位で突破することができました。(NAPROCKを除くと1位)
1問目はほとんど提出の速度を競う勝負になっていたので
自動化ツールが火をふき1位を取ることができました。
1回戦に関しては数ヶ月の努力があったのでそんなに不安はありませんでした。
準決勝は、5位、3位、3位と最終成績3位で突破することができました。
僕は4回目で初の決勝進出だったのでとても嬉しかったです。(顔がニヤついた写真が。。。)
決勝は10位と個人的には残念な結果でしたが、特別賞がもらえたのでよかったです。
反省
リーダーとしてもっとちゃんと仕事をふるべきだった。
進捗確認も絶やさずするべきだったし、困っているところをヒアリングすべきだった。
せっかくチームに入ってもらった1年生たちに仕事を振れず、
かと言って何かを教えることもできず、プロコンの楽しさを
十分に経験させられなかったことが一番の反省点です。本当に申し訳ない。
最後に
なんだかんだ個人的には今年のプロコンとても楽しめたので大満足です。
専攻科に進学した意味があったと思える出来事でした。
現地では他の高専の競技部門の人とそれなりに交流できたし、最高でした!!
チャンスがある後輩の皆さんは自分の武器を磨いて高専プロコンに出ましょう!!
以上、老害からでした。
明日は駐日ユーゴスラビア臨時政府大使館(@ICT_yugosoviet)です。
めちゃくちゃおもしろい記事を書いてくれることを期待しています。
AOJ watch toolsの話
AOJ watch toolsの話
この記事はICT Advent Calendarの15日目として書かれました。
前置き
どうもこんばんわ、@orisanoです。Advent Calendarで何を書こうと悩んでいましたが、
今年作ったものがあるじゃないかと気づいたのでそれを記事することにしました。
僕は今年の1月くらいからAOJ watch toolsというものを開発しつつ公開してました。
使ったこと、見たことがあるという人もいるかもしれません。
以下の3つをまとめてAOJ watch toolsと呼んでいます。
今回は僕とAOJ watch toolsの1年間を書いていきたいと思います。
きっかけ
きっかけはraimei10130くんだったと記憶しています。
当時、AOJで何問解いたかを後輩に聞くのが趣味だった僕は
皆のアイドルraimei10130くんと
僕「何問ときましたか?」
raimei10130「(◞‸◟)」
僕「何問ときましたか?」
raimei10130「0問です。」
僕「1日1問解きましょう!!!!!!」
raimei10130「わかりましたよ!!!!!!!!!!!!!!!!!!!」
僕「AOJ監視しとくから」
というやりとりをしました。これがAOJ watch toolsを作るきっかけになったわけです。
といってもこのやりとりのあと2週間ほどは普通にAOJを監視していました。
2週間たって監視も面倒くさくなってきてましたが、当時の他の1年生や2年生にも
同じようなやりとりをしていて引くに引けない状態(自業自得)だったので
ツールをつくろうと決意しました。
(この時点でのraimei10130のSolve数:0)
開発(初期)
ローカルで動く監視ツールでも良かったのですがその時の僕が
何を考えたのかはわかりませんがHTMLでやろう、JS(CoffeeScript)でやろう
という気分になっていました。おそらくその背景にはサーバ借りたくない
気持ちが強かったのだと思います。結果的にそれがいい方向に転がったと思います。
HTML+JS(Coffee)でやってdropboxのpublicフォルダでホスティングしようと
考えていましたが、ちょうどその時期にGithub Pagesの存在を知ったので
そちらでやることにしました。
いろいろやることが決まったのでもりもり開発を始めました。
当時あまりJS(Coffee)を書いたことがなかった僕はコールバック地獄にはまりながらも
ajaxでAPIにアクセスしてSolve数を取得できるようになりました。
aoj_watch(ソースコードめちゃくちゃ)はかなり初期に作られています。
(この時点でのraimei10130のSolve数:0)
開発(中期)
いろいろできることが見えてきたので部内だけのsubmit一覧とか作れると
面白いかなと思い作ることを決意します。この時期くらいまでリファクタリングなど
完全に無視して突っ走っています。完璧にやばいです。
そんな完璧にやばい状況でもaoj_submit_watchは完成します。
複数ユーザの情報取得なんていうAPIは存在しなくて一人ずつ情報を取得して
クライアント側でマージするという処理を行っているのでAPIアクセスが多く
非常に重いページに仕上がっています。
この頃はユーザの追加がかなりだるかったのを覚えています。
(この時点でのraimei10130のSolve数:0)
開発(今まで)
中期を超えたあたりからAOJのdiffを取るツールがほしいと
後輩から言われていたし自分も欲しかったので
次作るのはdiffツールだと決めていました。
AOJのdiffを取るツールがあるのは知っていましたが、
学内からだとブロックされたり、レスポンスタイムアウトしたりなど
まともに使えた記憶がありませんでした。
3つ目のツールを作るときにさすがにリファクタリングをしようということで
勉強してコールバック地獄から抜けだしたり、クラス化を行ったりしました。
このリファクタリングしている時に、seka先輩にaoj_submit_watchの高速化を
やってもらい、その際にgruntでいろんな作業を自動化してもらいました。
本当に感謝しています。ありがとうございました!!!!!!!!!!!!
リファクタリングに結構時間がかかりましたが最後のaoj_compareが出来上がりました。
ぶっちゃけどのAOJ watch toolsより反響が大きく、びっくりしました。
これ以降は細かい機能追加などを今日まで行って来た次第です。
これまでorisano.github.ioにpullreqをくれた、
たいちゃん@imishinistとくまさん@higumachan725、seka先輩
本当にありがとうございました。これからもpullreqくださいお願いします。
(この時点でのraimei10130のSolve数:9)
作って思ったこと
AOJ watch toolsを作って公開してみて思ったことがあります。
それは可視化が重要ということです。これは僕自身の話なのですが
aoj_watchを作って自分のsolve数を見るようになって、
m_kyoujyuやli_saku先輩を越してやろうという具体的な目標を持つようになりました。
具体的な目標を持つことで開発当時100問解いていたかすら
怪しかった僕が376問までになり、ICT委員会の中で2位まで上り詰めました。
可視化、具体的な目標、それを効率的に達成するためツールがあると
切磋琢磨しやすくなると僕は考えています。AOJ watch toolsで
ICT委員会の競技勢の実力が上がると非常に嬉しいです。
(この時点でのraimei10130のSolve数:9)
最後に
全国のICT委員会でもこんなシステムを導入してみるといいかもしれません。
僕のGithub Pagesをcloneして、users.jsonを書き換えると
どこの組織でも使えると思います。役に立てると幸いです。
最後に言いたいのは
raimei10130が1日1問解いてたら360問くらいなはずなので頑張って問題解いてください!
明日はみずきちさんの記事だと思います。
宿題 0b1 #kagapra0715
AOJ 0569
21:31~22:24
外側からラベリングして建物のセルに到達した回数を求めれば良い。
後は6近傍の時の移動が出来ればラベリングするだけ。
外側に番兵を置く実装をすると非常に楽。
僕は6近傍の時の移動ができなかったので時間がかかりました。
53分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020674
AOJ 0033
22:26~22:33
取りうる状態が2^10個くらいなので全探索で余裕。
Aに入れるか、Bに入れるかをDFSする。
7分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020685
AOJ 0118
22:35~22:42
このようなラベリング問はUnionFindで常勝(と思っているので)
必要な部分だけUnionFind書いて終了。
4近傍で同じ文字があればmergeして、最後にgroupの数を出力するだけで良い。
実際dfsとかのほうが短く早く書けそうですが、こういう問題を見ると思考停止してしまう。
7分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020692
AOJ 0558
22:44~23:18
読んで「ダルそう」となった問題。
S -> 1 -> 2 -> 3 -> ... -> N
の最短経路長の和を求める問題だということにすぐに気がついた。
そこからは思考停止してグラフを作って、ダイクストラっぽいもので最短経路長を求めた。
34分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020743
AOJ 0121
23:19~23:35
7パズルを解く問題。
最初の時点で完成版盤面から解くことの出来る
全ての盤面の最短の解をBFSで求めて保持しておく。
盤面が7!程度しかないので問題はない。
BFSを書き慣れていなかったり、いろいろ躓いた。
16分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020767
AOJ 0529
0:37~0:45
半分全列挙を行う問題。
kagamiz先生が講義で言っていたことを素直に実装した。
0点を追加することで必ず4本ダーツを投げるようにして
N^2で2回投げるパターンを列挙しその中から一つ選び,
M-今のパターンの点数 以下の最大を2分探索で求めることで解くことが出来る。
8分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1020833
とりあえずこれからも宿題で解いたものをブログに上げると思います。
毎年恒例の年明けたから書いたコード
あけましておめでとうございます。@orisanoです。
毎年恒例(1年ぶり2回目)の年明けたから書いたコードを適当に晒しておきます。
去年とちょっとネタがかぶってるので来年から本気出します。
説明はしません。見たらわかると思います。
puts();main(){qsort((int[]){2*2*2*3*479*164093,11273*150769,79*1453*14813,7*47*89},2,2*2,puts);}
適当に今年の目標。
ブレない目標を持つこと
が今年の目標です。
今年がより良い年であることを願います。
僕がコードゴルフを始めたキッカケ
こんばんわ。@orisanoです。
この記事はICT Advent Calenderの20日目の記事です。
毎度毎度のことですが、
今日は僕が比較的時間を費やしている趣味である。
コードゴルフについて語りたいと思います。
始めたきっかけ
始めたきっかけはえむきょうじゅでした。
2年の頃?だったので今からちょうど2年前になります。
夏休みの合宿中、プロコンの開発の息抜きでえむきょうじゅにそそのかされたのが
すべての始まり(終わり)でした。
誰もが通るAOJ0000
某くま先輩と某えむきょうじゅが当時聞いたこともないコードゴルフという
趣深い競技をしていたので、開発に疲れた僕は息抜きとしてやってみることにしました。
初めてのコードゴルフがAOJ0000でした。
#include <stdio.h>
int main(void)
{
int i, j;
for (i = 1; i <= 9; i++){
for (j = 1; j <= 9; j++){
printf("%dx%d=%d\n", i, j, i * j);
}
}
return (0);
}
当時の僕はこんな感じのコードを
#include<stdio.h>
int main(void){
int i,j;
for(i=1;i<=9;i++){
for(j=1;j<=9;j++){
printf("%dx%d=%d\n",i,j,i*j);
}
}
return 0;
}
こうすることをコードゴルフと呼ぶ非常に素直な好青年だったに違いありません!!
しかし、最終的に
j;main(i){for(;i%10;(j=++j%10)?printf("%dx%d=%d\n",i,j,i*j):i++);}
こういったコードを書く青年になってしまったようです。
そして
プロコンの開発(2時間)は停滞し、息抜き(5時間弱)が行われて、
おりさのという青年は変わってしまいました。
ここで伝えたかったことは趣味に打ち込むのもいいけど、
「実際のコーディングに影響を出しちゃダメだぞ★」ということです。
あとプロジェクトに火をつけちゃダメ、ゼッタイ
むしろ僕はコードゴルフを始めたから人一倍
コードの綺麗さ、読みやすさを意識するようになりました。
コードゴルフをやることでトリッキーなことをしているコードを読めるようになったり
環境について詳しくなったり、1byteに命をかけるようになったり
といろいろ良いことがありました。
最後に
僕がコードゴルフを始めたキッカケについて語る記事が
長くなってしまって申し訳ありませんでした。
明日はプロラボ現会長の@Pelkiraくんが書いてくれます。
(Accepted 2822byte)
アドレスから添字を求めるのがめんどくさい
どうも、@orisanoです。
今日は、bsearchという関数を使ってて思ったのですが、
ポインタから添字を求めるのってちょっとだけめんどくさいなって思いました。
ので、ソースコードを書いて、忘備録的にあげようかなと思った次第です。
以下コード
typedef unsigned long long ulong; ulong ptr2index(void *head, void *cur, size_t size) { ulong ha = (ulong)head; ulong ca = (ulong)cur; if (ca < ha) ha ^= ca ^= ha ^= ca; return ((ca - ha) / size); }
追記: どの処理系でもできるか保証できないですが
int ary[1024]; int *p = ary; int *q = ary + 54; int d; d = q - p;
という感じでやっても添字は求まるっぽいです。(詳しくは調べてないです
処理系によってアドレスが64bitだったりするので、最初からlong longにしておけば32bitの処理系でも大丈夫なんじゃないかっていう甘えです。