読者です 読者をやめる 読者になる 読者になる

Tsuzu' Notes

主にIT系備忘録

フェルマー方程式/Fermat(JOI2007春合宿Day2 2nd)

春合宿まで精進するぞって言ってし始めたんですが結構始めから躓いていて早速数学に苦しめられています。(本選参加記はもう少ししたら書きます。)
Fermatも理解できず、LatteMaltaさん(@latte0119)に教えていただいてなんとか理解できたので忘れないうちに備忘録としてまとめます。(ありがとうございました!)

続きを読む

JOI2016/2017予選参加記

最後ということもあり書きます。
JOI(情報オリンピック)は中一から参加しているのでもう5回目ですね・・・。時の流れは早いものです。 前回、前々回は本選まで出場していますがいずれもそこで敗退しています。

事前準備

今回はいくつかのツールを事前に準備して挑みました。具体的には

  • テストケースの入力ファイルをダウンロードフォルダから自動分配するプログラム
  • 計5つのテストケースを実行ファイルの標準入力に渡して実行し結果をファイルに書き込むプログラム
  • 一度提出したファイルとローカルに残っているファイルが一致しているかを確認するプログラム。(結果として公式が公開した答えと自分の答えを照合するプログラムにもなりました。)

などです。
5回目にもかかわらず少し戸惑いながらなんとかログインなどの準備を完了しました。

1

JOI予選1問目恒例ifでとく感じの問題ですね。a≠0なので0を基準に考えればOKです。 gist.github.com

2

これもJOI予選2問目恒例forと配列でとく感じの問題ですね。 問題を勘違いしてやたらバグらせてしまったのが反省。 gist.github.com

3

O(NMD)で問題ないので3重ループしてあげれば終わりです。 gist.github.com

4

ここで難易度が急上昇してビビる。とりあえず問題を読んでDPっぽいなとは思いつつまだ思いつかなかったので飛ばして5問目。

5

UnionFindとかDBS/BFSとか考えて微妙にうまくいかなかったのでなにも考えず遡るようにsetでゴリ押すコードを書いたらケース5でも5sほどで終わってしまいまぁいいかとなってそのまま4問目へ。

gist.github.com

4

考察をすると最終的な状態を決めてしまえばどれを移動すればいいかが求められることがわかる。最終的な状態の並び方はM!通りあるがこれをbitDPで処理してやるとO(2M)で良いことがわかる。また、状態を確定させた時にいくつを移動しなければならないかはあらかじめ累積和を利用して数えておくことができる。

gist.github.com

6

ダイクストラに寒暖の異なる部屋に入れるまでの時間、寒暖、経過時間を持っておけば良さそうだとは思ったがそれでうまくいく確証と計算量がオーバーしそうな予感がしてそのまま終了。

結果

まだ結果は出ていませんが自分で答え合わせをした感じだと解いたところは全部あっていたようで5完(500/600点)でした。今回は各ツールのおかげでだいぶスムーズにできました。
本選にも出場できると思うので後悔の無いよう頑張ろうと思います。

カード情報が盗まれたっ!と一人で慌てていた話

自戒も含めて文字に起こす。

12月4日の夜、私はデビットカードを利用している銀行のインターネットバンキングにログインした。 そこで異変にすぐ気づいた。使った記憶がないのに口座から1万円以上なくなっていたのだ。慌てた私は不正利用の可能性を考えそこですぐにデビットを停止した。

f:id:tsuyochi23182:20161205191248p:plain
見てみると12月3日の夜にVisaデビットで13800円が利用されていた。しかし私は全く利用した記憶がない。いよいよ不正利用の可能性が高まってきたぞと思いつつ利用明細を開くとAmazonからの請求になっていた。 盗んだカードをAmazonで利用したりするだろうかと疑問に思いつつ自身のAmazonアカウントの注文履歴を見てもそのような請求は見当たらなかった。まぁAmazonなら返金される可能性も高いだろうし安心だと考えとりあえずAmazonのカスタマーサポートに連絡をしてみようかと考えていた時ふと13800円とはなんの金額なんだろう、と気になったのだ。 まぁそう簡単にヒットするわけはないだろうと思いつつGoogleで「Amazon 13800」と検索。しかしここで予想を裏切られた。f:id:tsuyochi23182:20161205184811p:plain
あっ...(全てを理解

時を遡ること数ヶ月前、国内のAmazon CloudDriveの無制限プランが解放された。無制限のクラウドドライブを渇望していた私は一目散に無料体験に飛びついた。その際にカード情報を登録する必要があったのだが、とりえあず入力して使ってみたところ思ったよりも速度が出ず実用的でないと判断したため金を払う価値はないと感じた。私はここでなぜか体験プランの終了を押すのではなく支払い情報から自分のカードを無くしておくことで体験プランが終了すると同時に支払いが完了せず勝手に終了してくれるだろうと考えていた。

しかし実際にアクセスしてみると実際支払いが完了していた。どうやらAmazonで普段買い物をするために登録しているカード情報から支払いが行われてしまったらしい。まさかそっちの情報から引き落とされるなど予想だにしていなかった。

仕方ないのでAmazon CloudDriveのカスタマーサポートに連絡をしてこの旨を伝えた。 このメールを送ったのは確か23時過ぎで、まぁ翌朝には返信が来るだろうと期待していた。しかしなんと日付が変わって2時ごろに返信があった。 まさか夜中にサポートしてくれるとは思っていなかったためとても驚いた。
結果はOK。 f:id:tsuyochi23182:20161205190328p:plain
ありがとうAmazon!今後はこのようなことがないように気をつけます...。

(今回事実に気づく前に一度銀行の方にも連絡を入れてしまい慌てて、なんでもありませんでしたという謝罪の連絡を入れ直したりしており、多くの人にご迷惑をおかけしてしまいました。この場を借りて謝罪を述べさせていただきます。申し訳ございませんでした。)

Node.JSでアンプをLAN経由で操作

以前家の今のテレビを父が購入した際、なぜか導入されたMarantz NR1604。(今や家で使う人は私一人のみでとてももったいない。)
NR1604はDLNAやネットワークラジオ、AirPlay*1などの機能をサポートしており、その一環としてLAN経由で操作ができるようになっている。
f:id:tsuyochi23182:20160709181127p:plain:w400

このNR1604は、音質などに疎い私には十分満足のいくものであり、よく家に一人でいる時にAirPlayを利用して音楽を流している。
NR1604は電源が切れている状態でもLANには接続されており、AirPlayで再生を開始すると自動的に電源が入るようになっている。
しかし、AirPlayが終了した後でも自動で電源が切れる機能はないため、私はよく電源を切り忘れてしまう。アンプは非常に熱を持つためよろしくない。

そこでタイマーをセットして指定された時間になるとLAN経由で電源を落とすスクリプトを軽く組んでみた。以下、開発環境。

まず、LAN上に存在するNR1604のIPアドレスを取得するところから始めた。プログラム内にIPアドレスを直で書いてもよかったが、度々変動していることもあったので動的に取得させることにした。
LAN上のデバイスのIPアドレスを取得する方法として、DLNAでよく使われているUPnPなどがあるが、今回はAppleが開発したBonjourを用いた。(そもそもUPnPをNR1604をサポートしているかは不明)
Node.JSにはBonjourを利用するなんとマルチプラットフォームなライブラリを公開してくれている人がいたため、開発はスムーズに行うことができた。Node.JSなんでもライブラリあってすごい!本当に。
Bonjourを利用して、サービスの種類をAirPlay(raop.tcp)にしてやると、以下のようにデバイスの情報が取得でき、その中にIPアドレスも書いてある。
f:id:tsuyochi23182:20160709183705p:plain:w400

あとは指定の時間にCronJobが発火するようにセットし、このIPアドレスに対してHTTPリクエストを送信するだけで電源を切ることができた。
今更ながらリクエストを送るために今回は既存をライブラリを用いたがそのライブラリが古いものであったため、バグ修正に追われて自分で書いた方が圧倒的に楽だったのが残念。
(一応コードを貼り付けますが基本的にmarantz-avrがおかしいのでまともに動きません。)
これで気兼ねなくMarantzアンプを使えるようになったので満足。

Marantz NR1604 Auto PowerOff

*1:Appleが開発した、iOS/macOSなどでサポートされているLAN経由で音声、ビデオなどを転送する機能。

気になってるものまとめ

面白そうなものを見かけても忘れちゃうので備忘録的なまとめ

続きを読む

スクリプトを毛嫌いしていたがCoffeeScriptを使ってみる

CoffeeScriptを使ってみました。 f:id:tsuyochi23182:20160101234544p:plain

続きを読む

2015年を振り返る

今年したあれこれを振り返ってみます。
なんかAdC記事と被りまくってますね、書いちゃったからいいや。

続きを読む