東京工業大学 ロボット技術研究会

東京工業大学の公認サークル「ロボット技術研究会」のブログです。 当サークルの日々の活動の様子を皆さんにお伝えしていきます。たくさんの人に気軽に読んでもらえると嬉しいです。
新歓特設ページ        ロボット技術研究会 HP        ロボット技術研究会 twitter公式アカウント

競技プログラミング

「ロボット技術研究会」通称「ロ技研」は、その名前の通りロボットの制作や研究はもとより、電子工作や機械工作、プログラミングなどの幅広い分野にわたるものつくり活動を行っています。

カテゴリ一覧: loading

Google Code Jam

こんにちは。rogy競プロ部の森田(@yosupot)です。

たまにはブログを書きます。今回はGoogle Code Jam(以下GCJ)という大会についてです。

これは、名前の通りGoogleが主催しているプログラミングコンテストです。競技プログラミングの大会の中では、ICPCと並び、最大の規模を誇るんじゃないかと思います。

システムとしては、何回かに分けて予選があり、人が 沢山(今年は27169人)->3000->500->25と減っていきます。これは全部オンラインの大会で、最後の25人に残ればニューヨークのgoogleオフィスにいって決勝をします。

そして僕は、最後の25人に残った(https://code.google.com/codejam/contest/3224486/scoreboard 7位,日本人最高位)ので、無事ニューヨークに行きます。やり遂げたぜ。


…というだけでは面白みにかけるので、今回は今年のGCJに出題された問題のうち、高度なアルゴリズムを必要としない問題を2題紹介します。興味を持ったらぜひ来年参加してみてください(といっても丸一年後だけど…)

Round2 A問題 Rather Perplexing Showdown
https://code.google.com/codejam/contest/10224486/dashboard#s=p0

あなたは、グー、チョキ、パーの書かれた紙をA, B, C枚持っています。A+B+Cは2の累乗、つまり1,2,4,8,16,...のうちどれかになっています。ただし、最大でも1024枚です。

あなたは、この紙たちからトーナメントを作りたいです。(A+B+Cが2の累乗なので、シードとかは当然無いです。)。紙たちはじゃんけんをして、勝利したほうが勝ち抜きます。そして、トーナメントのどの試合でも、引き分けが起きてはいけません。

このようなトーナメント表を作れますか?POSSIBLEかIMPOSSIBLEで答えてください。(元問題だと、POSSIBLEだったらグー=R, パー=P, チョキ=Sとしてトーナメント表を左から見た時の辞書順最小の文字列を求めないといけないですが、これはもうすこし難しいです。)




Round3(=最終予選) A問題 Teaching Assistant
https://code.google.com/codejam/contest/3224486/dashboard

あなたは、空のスタックと、'A', 'B'からなる長さNの文字列を持っています。スタックの容量は無限です。文字列の長さ、つまりNは100000以下で、しかも偶数です。

そして、文字列の先頭から順番に文字を見ていって、1文字見るごとに次のうちどちらかの操作ができます。

- その文字をスタックに積む。
- スタックから文字を1個取りだす。そしてこの時、取り出した文字と今見てる文字が同じなら5円、違うなら10円貰える。

文字列を最後まで見た時の、もらえるお金の合計を最大化してください。

例えば文字列がAABBなら、push-pop-push-popとすれば20円貰えます。
文字列がABBAなら、push-push-pop-popで20円貰えます。
でも、ABABなら10円しか貰えません。
ほかにも、ABBBとかだったら15円貰えます。




 

yosupot

advent_rogy

rogy advent calender、25日目です。

rogy競プロ部のyosupotです。

今日は競技プログラミングの紹介をします。競技プログラミングのさまざまな魅力をお伝えしていきたいと思います。

楽しい

この記事で一番まともな理由です。

ネットゲームのようなものなので楽しいです。

ですがこればっかりはやってみないとわからない & 楽しいかは個人差があると思うので参加してみてくださいとしか。

ところでAtCoderというサイトでは毎週コンテストを開催しています。時々僕も問題を出しています。

短いコードなら高速に書けるようになる能力

これは情報実験第二という授業で役に立ちます。

暇つぶし

割と無限に時間を潰せます。

男女比

これは魅力ではないんですが、rogyもびっくりの男女比です。さすがに異常。

賞金。

クリスマス

クリスマスイブにはクリスマスコンテストが行なわれます。大変良い風習ですね。
参加者リストを見ることでクリスマスイブに予定があるヤツをいち早く、確実に発見することができます。

旅行

最近は某某某ー某が金をばらまいているので、好成績を取ると上海とか沖縄に行けます。先日沖縄に行きました。

あとICPCという大会では海外に行く人がたくさんいます。僕は去年ジャカルタに行きました。冬にジャカルタに行くと体が壊れます。

某某某ー某

最高。なにがc某某某m某sじゃ

検閲

↑が突然消されないか不安です。

時間割の選択に自由が生まれる

これは明らかに自明ではありません。”風が吹くと桶屋が儲かる”ぐらいには回りくどいです。

まず、海外で開催される競技プログラミングのコンテストはだいたい深夜にあります。今一番勢いのあるcodeforcesというサイトでは、1:30 ~ 3:30が普通の時間となっています。

こんな時間のコンテストに出たらどうなるでしょうか。単位が落ちますね。

単位が落ちるとどうなるでしょうか。学科所属が出来なくなります。

東工大はバグを抱えていて、実は情報工学科においては学科所属をしないほうが明らかに得です。E/Oクラスという縛りに縛られず、好きな方を取れるようになるからです。

ですが、まともに単位を取ってしまうと学科所属しないという選択肢を行うのは非常に面倒なことになります。

もうわかるように、得です。

あと普通の人はj12345みたいなクソダサIDを貰うのですが学科外受講になればx12345というIDが貰えます。xです。かっこいいですね。

文系科目

単位ほしい

部長回避

なぜか研究報告会とプロコンが被りまくります。あと先述したように単位を落とすのですが、これで英語を落とすと部会に出れなくなります。

各種イベントに出れなくなるので、部長から遠のきます。素敵ですね。

部長業務お疲れ様です

@OMA_stさん部長業務お疲れ様です

次期部長

ここで誰かの名前をあげようかと思ったんですが、この記事がネタ記事になってしまいそうなのでやめておきます。

おわりに

プロコンをしていても成績が良い人はたくさんいるので、この記事をまともに受け止めないでください…

RadixHeap紹介

東京工業大学第5類の森田です :)



めっちゃ突然ですがダイクストラ法あるじゃないですか、最短経路を求めるアレです

あれってHeap使うじゃないですか priority_queueとかそういうのです

そのHeapで速いやつでRadixHeapってのがあるんです

今日はそれの紹介をします。

コレです↓
色々なダイクストラ高速化

人生で真面目にスライドを作る機会が無かったので死ぬほど大変でした。
練習しておかないと数年後研究室配属したとき確実に大変なことになると実感しましたね。
頑張ります 


以上森田でした、ではでは〜 

プログラミングコンテスト

こんにちは!14年度入学の@yosupotです.

突然ですがプログラミングコンテストというものを知っていますか?
与えられた課題を解くプログラムを短時間で素早く書くというものです.(実は長時間のもありますが…)

具体的には、
"二次元平面上に沢山点が与えられるから、その中で最も近い2点間の距離はどのくらいか?"
のような問題が5問/2時間ぐらいで出されます.
多少プログラミングをかじった人なら、すぐにO(N^2)(N:点の数)のアルゴリズムは思いつくでしょう.
勿論これではあんまり難しくないです.
ですがこれをO(NlogN)やO(N)で解こうとすると難しいです.
O(N^2)とO(NlogN)というのはめっちゃ違います. 普通のフーリエ変換はO(N^2)で高速フーリエ変換はO(NlogN)です.
こういうのを解くアルゴリズムをウンウン考えたりネットで調べたりするのがプログラミングコンテストですね.

日本ではAtCoderというサイトが有名です.
今週末もコンテストをやるようです、よかったら参加してみてはいかがでしょうか?


それでここからが本題で、
実は僕もコンテストを開催します!!
KCSという、kagamiz(rogyではない)さんが作ったコンテストサイトを借りて、問題を出題します!
3月8日の夜に行う予定です!!
今バリバリ準備をしてますよ〜〜〜〜、ぜひ参加してくださいね!

ではノシ
ギャラリー
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 自作キーボードを作ろうver1.0
  • 第14回ROBO-ONE Light 結果報告
  • ロボット技術研究会紹介
  • ロボット技術研究会紹介
  • rogy2016冬合宿 in 戸狩
  • rogyサバゲ:†革命†をもっと
記事検索
最新コメント