AtCoder Petrozavodsk Contest 001
apc001.contest.atcoder.jp
Petrozavodskって何だ?
というのはさておき。土曜深夜に5時間コンテスト。
寝ぼけててlong longにし忘れてWAみたいなのが多かったけど残り5分で5問目を通して5完。眠いけど頑張った。
ooooo----- (147th) 1616->1715 (+99)
順位表では147なのに142ndなのはなぜだろう
パフォーマンスは2216(黄)とな
続けて出てれば黄色(2000〜2399かな)までは行ける気がしてきた。
Coursera: Introduction to FPGA Design for Embedded Systems
コロラド大学ボルダー校のTimothy Scherr先生による組み込みシステム向けFPGA設計入門の4週間コースをCourseraで受講しました。
そもそもFPGAに関しては全くの初心者(電子回路とか論理回路については素人とまでは言わないけれど)で、中級者向けのこのコースについていけるのかは未知数でしたが、論理回路に関するなけなしの知識を総動員して最終週までたどり着けました。
Quizは満点が出るまでやり直して、無事100%で修了できました。(1/24)
受講の動機
去年の秋からCourseraの専門講義 deeplearning.ai を受講していて、第5講の開講が延期になって1ヶ月空いたので何か受けようかなと思ったのと、とある社内プロジェクトでFPGAをいじることになったのとで受講を決めました。
概要
実際に手を動かしながら、FPGA開発の基礎を四週間で習得します。
・プログラマブル・ロジック・デバイスの歴史
・FPGAの選び方(各社のFPGAの特長やFPGAのアーキテクチャの違い)
・開発環境の使い方(インストールから回路設計まで)
・回路設計ハンズオン(加算器からNios II*1を使った組み込みシステムまで)
生徒同士で採点し合うpeer assessmentの仕組みを採用しているコースなので、自動採点のみのコースと違って締め切りが重要になります。(システム的には課題の提出は可能ですが、採点してくれる生徒がいなくなってしまう為)
講義は全て英語で、とてもアメリカっぽい*2英語です。
英語字幕とトランスクリプションはありますが、日本語字幕は(現在のところ)用意されていません。
イントロダクションがスパイ・エージェント養成コースみたいな演出になっています*3が、ビデオを見ながらFPGA開発環境(IntelのQuartus Prime)をインストールして実際に使いながら進めていくハンズオン形式のチュートリアルといった感じでした。ビデオを適宜止めながら画面を操作するので、ビデオの長さ以上の時間がどうしてもかかります。
推奨環境
Quartus Primeの動作環境がWindowsとLinux(RedHatもしくはCentOS)のみで、Macでエミュレータを動かすのは非推奨、と明言されていましたが、残念ながら手元にはMacBookやiPad Proしかないので、仮想化技術で行けるところまで行って、駄目なら駄目でその時考えることにしよう、と思って始めました。
Macでもなんとか最後まで受講できましたが、この講義に関してはWindowsマシンがあるならWindowsでの受講をお薦めします。
メモリは(WindowsにせよLinuxにせよ)8GB以上推奨、とのことです*4。
Linux絡みの注意点
・講義でも使われている設計検証ツールModelSimの無料版は32bit版で、これを64bit環境で動かすのにあれこれ(デフォルトでは入っていないi686なものを)追加インストールする必要がありました。
・IP CatalogのライブラリからIP部品(乗算器、SQRTなど)を調達する時に出てくるMegaWizardが、先に進むごとに重くなって三ページ目ぐらいでフリーズします。これはCentOSのデスクトップ効果(ビジュアルエフェクト)を標準からCompizにするとなぜか直ります。(普通逆かなと思うんだけど)
・回路図でユーザ定義シンボルの右上に余計なテーブルみたいなのが表示されて、小さくはできるけど消し方が分かりませんでした。
macOS上で頑張りたい人のためのメモ
・最初Docker for Macで行けないか試しました。CentOSを入れて、画面はXQuartzに出してインストーラを走らせて、インストール自体は完了しますが起動しようとすると謎ダンプを表示して落ちます。(CentOSのバージョンを色々試したり、Xの画面が出なくて右往左往したりで半日ぐらい格闘してたと思います)。
・その後(Dockerは諦めて)VirtualBoxにCentOS(6.9。依存ライブラリの都合上6.x系推奨)を入れた上で無事動きました。Dockerではハードウェア的な何かをチェックされて落ちたのでしょうか。
・メモリは8GB以上推奨とのことでしたが、3GB強程度の割当てで最後まで行けました。
以下受講記録
*1:IntelのソフトコアCPUで、XilinxでいうところのMicroBlazeに相当。RISCアーキテクチャCPUのFPGA実装。
*3:Week 4でシステム設計ツールQsysを使って組み込みシステムを作る話のところで"By the time you are done, people may mistake you for Q!"って言ってるけどQって何?誰?と思った人。ジェームズ・ボンドのコードネームです。
*4:多分4GBなくても行けますが。
GCCのバグ?未定義動作?g++とclang++で違う結果になるコード
こないだAtCoderの過去問を解いてて
ローカルでは正解が出ているのにサーバ上でREが出まくってはまったのでメモ。
再現できる形で変形&単純化を繰り返した結果がこんな感じ
#include <vector> #include <cstdio> std::vector<int> a, b; int f() { a.push_back(-1); b.push_back(-1); return (int)a.size(); } int main() { int first = f(); printf("a[0]=%d, b[0]=%d\n", a[0], b[0]); a[0] = f(); printf("a[0]=%d, b[0]=%d\n", a[0], b[0]); return 0; }続きを読む
ARC006-D アルファベット探し
みょんみょんがツイートしてたやつ
競プロ全然やったことない人でも、業務でやってるならこれくらいは書けてほしいな、と思う問題がこの辺なんだけど、ちょっとハードル高いかもなあ、とは思ってる。https://t.co/yxKa9oIwUM
— chokudai(高橋 直大) (@chokudai) 2017年6月30日
7x7ピクセルで定義されたA,B,Cの文字(正の整数で等倍拡大したもの、90度刻みで回転したものを含む)の出現回数を数える問題。
Codeforces Round #421 (Div. 2)
http://codeforces.com/contest/820
今日もC→B→A(→D)の順で。2完 (oox--)。
(C問題(Div1だとA)のごたごたでunratedになった模様)
拡張ユークリッド互除法の話
先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)
拡張ユークリッド互除法というのは、 を満たす を求める方法。
を で割れば (a'とb'は互いに素)という形になる。
Crayfish Scrivener (IOI 2012, day 1)
6月は永続データ構造強化月間(そういうことにしました)、ということで
qnighy先生の
Re永続データ構造が分からない人のためのスライド
で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。