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

CODE FESTIVAL 2015 Final I 風船ツリー

注意 この記事を書いた人はまだACしていません 解けました (2015/11/16) 問題 http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_i 前提 整数のmultiset (日本語では多重集合と呼ぶそうです by @climpet さん) Sに対…

AOJ 2667 Tree (クエリ平方分割解法)

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2667 解法 クエリをB個ごとのブロックに分割する。ブロックのはじめにやる処理をSetUp,ブロックのおわりにやる処理をTearDownと呼ぶことにする。 SetUp ブロック内のクエリで関係する頂点だ…

ICPC 2015アジア地区予選のSystem Trial DVDを試した

System Trial DVDって何? ↓これです システム環境 | ACM-ICPC 2015 Tsukuba ↓起動するとこんな感じです 最初にやること キーマッピングの変更 (本番ではおそらく不要) 競技概要 | ACM-ICPC 2015 Tsukuba なお、キーボードはつくば大会が準備した日本語キー…

Topcoder Marathon Match 89 MazeFixing 参加記

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&compid=12525 ルール グリッドの中に迷路っぽいものがあります 迷路の周囲のセルをborder cellと呼びます 任意のborder cellから迷路に入ります。迷路に入ったら,セルに…

clang-formatのスタイル設定

C++

clang-formatはC/C++/Objective-Cのソースコードを整形するツールです。「美しいフォーマット」について自分で考えるのが面倒になってきたので導入しました。動作例などは以下を参照してください。 歌舞伎座 tech #2 LT 資料 · GitHub スタイルオプションは…

HackerRank Simply SQL Contest参加記

www.hackerrank.com SQLについては素人なのでググりながらやりました。 RDBMSはMySQLを選択しました(本当はSQLiteかPostgreSQLを選びたかったのですが,HackerRankがDB2, MySQL, Oracle, SQL Serverしか対応していなかったので)。 The Blunder お給料の平…

二分探索をバグらせないための考え方

問題設定 整数二分探索とは,以下の矢印の位置を求める問題である。 パターンA パターンB 解き方 前提として,範囲を閉区間で扱うと微妙にバグるので半開区間で扱う。while文の条件はどちらのパターンでも ub - lb > 1 である。 パターンA [lb, ub) として範…

CODE FESTIVAL 2015 予選A D問題 壊れた電車

23:26追記 私の考えていた80点解法は100点解法だったようです http://www.slideshare.net/chokudai/codefestival2015quala 問題文 http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_d 20点解法 次のようなケースを考える …

ICPC JAG夏合宿2015 参加記

2015/Practice/夏合宿/案内 - ACM-ICPC Japanese Alumni Group 2日目 (University of Tsukuba + Sugim48 contest) 3完25位だった。つらい 3日目 (Russian Camp contest) 2完22位だった。つらい 4日目 (JAG contest) 4完11位だった。つらい

normalizeNumexpインストールメモ

本家 http://www.cl.ecei.tohoku.ac.jp/~katsuma/software/normalizeNumexp/ 本家 http://www.cl.ecei.tohoku.ac.jp/index.php?Open%20Resources%2FnormalizeNumexp GitHub https://github.com/nullnull/normalizeNumexp 性能 NAISTテキストコーパスで適合率…

topcoder SRM 666 WalkOverATree

頂点数N (1 <= N <= 50) の木がある。スタート地点が決められており、辺の上を移動できる回数L (1 <= L <= 100) が与えられたとき、最適な動き方をすれば、(重複を許さないで) 最大で何個の頂点に行くことができるか? O(LN3) よりは小さい解法 頂点v以下に…

AOJ 0254 Scone

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0254 概要:N個の正整数列 (1 <= N <= 3*104) が与えられる。連続する部分列の和 mod M (1 <= M <= 105) を最大化したときの値を求めよ。 O(N3) 解法 [begin,end) をO(N2)で決めて,和のmod …

AOJ 0270 Modular Query モジュロ・クエリ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270 カードが6, 7, 11, 13, 14, 15, 16, 19で,q=5のクエリに答えたいとする。 5で割った余りが最大になり得るのは,5*1のlower_boundの1つ前,5*2のlower_boundの1つ前,……,なので,ソートして…

AOJ 1505 Dungeon

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1505&lang=jp 前処理 とりあえずスタート地点からの最短距離d_s,ゴール地点からの最短距離d_gを計算する。 たとえば,各頂点のd_s,d_gが以下のような感じだったとする。 d_s d_g 0 5 1 1 1…

NAIST受験記(情報科学研究科 2016年度 第1回)

奈良先端科学技術大学院情報科学研究科に合格しました。 Web上で公開されている合格体験記にお世話になったので,私も記録を残しておきたいと思います。 小論文 取り組みたい研究についてA4用紙2枚にまとめて,出願時に提出します。 小論文と面接の配点が極…

ICPC 2015 国内予選 参加記

チーム ikura-hamachi-salmon で参加して32位でした。 登場人物 私 (B4, ICPC 4回目) 23氏 (M1, ICPC 4回目) OUDON氏 (B2, ICPC 2回目) 出来事 打ち合わせ通り,私がA問題を担当する。例年より難しいような…。うちの1年生チームは解けるかな…?とりあえず合…

scikit-learnメモ

GridSearchCV,RandomizedSearchCVのverboseオプション ドキュメントには単に"Verbosity level."や"Controls the verbosity: the higher, the more messages."としか記載されておらず闇っぽい。 verbose=1では一定の間隔でログを表示,verbose=2ではテスト毎…

HDDの返品保証制度を使ってみた (Western Digital, RMA)

HDDの返品保証を使ってみた from Sho Iizuka 姫路IT系勉強会で発表してきました。 実際に利用してみての感想はスライドの最後から2ページ目のことが全てです。 交換のための手続きに合計で半日以上を費やしてしまったので、時給換算して考えると、高々数千円…

SuffixArrayの説明に便利な単語を探す

SuffixArrayやその周辺領域での解説では、説明のための文字列としてabracadabraやmississippiといった単語が使われることが多いです。唐突ですが、別の単語を使ってみたくなったので、NLTKに付属のテキストから、使えそうな単語を探す指標をいくつか考えまし…

D3.jsでパーセプトロンを可視化した

授業でソフトコンピューティングについて勉強したので、パーセプトロンを実装したい気分になりました。 http://arosh.github.io/perceptron-playground/ 遊び方 どちらかお好きな方法でお楽しみください。 左下のボタンでClass1 or Class2を選択して、線形分…

ウェーブレット行列とFM-indexで全文検索を書いてみた

www.youtube.com 去年のはじめに高速文字列本を買ったのですが、アルゴリズムを眺めるだけで実装はしていませんでした。特にウェーブレット行列は実装が大変そうにしか見えなくて敬遠していたのですが、ICPCの夏合宿で @hirokazu1020 さんに「あれはアイデア…

scikit-learnとOpenCVで電子部品の画像分類

11月の1日〜3日に学祭がありました。サークルとしても何か出そうということになり、「とりあえず手続きだけはして夏休みに何か作るってことで〜」ということになったのですが、各々がICPCの練習やCTFに熱中しすぎたあまり、肝心の展示物が@akihiro01051先輩…

CODE FESTIVAL2014参加記

すごいイベントがあったので、参加してきました。これまでに参加してきたプログラミングコンテストの中で最大規模だと思います。

ACM-ICPC アジア地区 東京大会 2014 参加記

チームbroken_keyboardで参加して、ABCDFを解いて19位でした。 順位表

ICPC JAG夏合宿2014 参加記

夏合宿に参加していました。2回目の参加です。

OS X 10.9でMonoのSystem.Drawing.Bitmapを呼び出すとハングアップする件

C#

タイトルの件について、2ヶ月くらい前から改善されなくて困っていたのですが、先週bugzillaで説明が投稿されていました。 Bug 17225 – OS X 10.9 stuck on System.Drawing.Bitmap constructor calls FontCacheの生成に時間がかかっているだけのようです。時…

ICPC模擬国内予選&国内予選2014

チーム broken_keyboard で参加していました。*1 模擬国内予選は4完23位で、ちょっとうまくいきすぎたので本番で失敗するんじゃないかと不安になっていました。 本番は4完26位でした。CとDの傾向が過去とかなり違っていて動揺しましたが、ほかの2人の活躍に…

Mac (iMac Mid 2007) にUbuntu 14.04をインストール

なぜUbuntuをインストールしたのか? Linuxディストリビューションは何でも良かったのだけれど、とにかくOSXのまま使い続けるのが難しい状況だったためです。 インストールされているOSXが10.4でgccすらインストールされていない状態でしたので、OSXのバージ…

閉路の検出に負辺が入るとつらい

今回つまづいた問題はAOJでライブラリのverify向けの問題として公開されているAll Pairs Shortest Pathです。負の辺があり得る有向グラフ(|E| <= 9900, |V| <= 100, 多重辺や自己ループは無し)が与えられるので、負閉路が存在するなら"NEGATIVE CYCLE"を出力…

RUPC 2014参加記(立命館大学競技プログラミング合宿)

オンサイトで参加していました 1日目 @alotofweさん、@dhibo_77さんとPutterというチームで参加して、他の2人が解いてくれたAとBで2完でした。 要するに、私は1問も解けませんでした。すいませんすいません。 2日目 @not_522さん、@lyozさんとnshlyというチ…

Recruit Programming Contest アメリカツアーに参加してきた

12月に行われた「6問解いたらアメリカに連れて行ってもらえる謎のコンテスト」で参加権を得ることが出来たので2/9〜2/14にかけてコンテストツアーに行ってきました。 ASCIIさんの記事 gizmodoさんの記事 1日目 私は関西在住なので、伊丹から成田まで飛行機で…

明治チョコレートパズルを解くプログラムを書いてみた

www.hanayamatoys.co.jp 問題 以下のブロックを6*11のグリッドにぴったり入るように置いてください。 答え コード ライセンスはMITです #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <limits> #include <iterator> using std::vector; using std::string; namespace { co</iterator></limits></vector></algorithm></iostream></cstring>…

近況

リクルートのプロコンで米国コンテストの参加権を手に入れました プロコンサークル(仮)を設立しました TopCoder Marathon Match 82に参加しました。無色 -> 1301 問題概要と私の解法を簡単に書いてみました 今年の1月に購入したポータブルHDDが激遅 (700KB/s…

ICPC 2013 アジア地区予選 参加記 (競技について)

競技以外についてはこちら チームに割り当てられた端末のホームディレクトリ以下のsouvenirフォルダに入れたファイルはおみやげとしてメールで送られてくるというシステムでした。 先ほど届いたので提出コードを貼り付けます

ICPC 2013 アジア地区予選 参加記 (競技以外について)

結果は23位 (大学別17位) でした。 1日目 伊丹空港から飛行機で福島に向かいました。最寄りの駅から空港まで出ているリムジンバスに乗っていったのですが、NiCoPa (神姫バスが発行しているICカード) が使えないことを知らずに2100円*2回分のチャージをしてし…

ICPC 2013 国内予選

チーム wire stripper で出場し4完33位でした。 解くのにかかった時間は 20+25+15+120 (min) といった感じでした。 A. 整長方形 問題文 「高さと幅はともに150を超えない」とご丁寧に書いてあるので、全探索して条件に合うものを見つけるだけです。 競技時間…

TopCoder SRM 575 Div2

Easy - TheSwapsDivTwo Johnさんは数列を持っています。Brusさんは、その数列の異なる位置にある任意の2つの数字を選んで、1度だけ入れ替えることができます(Brusさんが選んだ2つの数字は、同じ数字になることもあります)。 Brusさんはこの入れ替え操作に…

std::map.operator[] に std::map.size() を代入した時の挙動が怖い

C++

助けてください > 闇の軍団の方々 問題のコード #include <iostream> #include <map> int main() { std::map<int, int> dict; dict[123] = dict.size(); std::cout << "result: " << dict[123] << std::endl; } 実行結果 /Users/arosh/clang clang++ -v Apple LLVM version 4.2 (clang</int,></map></iostream>…

TopCoder SRM 574 Div2

Easy - CityMap マナオさんは初めて来る街に到着したので、とりあえず地図を買うことにしました。 その地図は高さH・幅Wのグリッドとして表されていて、各セルには道路を表す '.' 、もしくは、施設の種類を表す記号として [A-Z] のアルファベット1文字(例…

Codeforces Round #175 Div2

順列に関する問題セットでした。 A. Slightly Decreasing Permutations http://www.codeforces.com/problemset/problem/285/A 順列 について となる の個数のことを、その順列の decreasing coefficient と呼びます。 整数nとkを与えるので、長さnで decreas…

Codeforces Round #174 Div2

A. Cows and Primitive Roots http://www.codeforces.com/problemset/problem/284/A 素数pについて x - 1, x2 - 1, ..., xp-2 - 1 (mod p) != 0 かつ xp-1 (mod p) == 0 が成り立つx (1 <= x < p) を、pのPrimitive Rootといいます。日本語では「原始根」と…

立命合宿2013 3日目

1日目 2日目 立命館大学の方々による3時間セットでした チーム決めPhase @ik11235 と @refiute で re_ikura というチームで参加します #rupc— しょラー@アカウントハックに完全敗北 (@shora_kujira16) March 13, 2013 ミーティングPhase エディタはCotEditor…

立命合宿2013 2日目

1日目の様子はこちら 大阪大学の方々による5時間コンテストでした チーム決めPhase @mi2uさんと会津大の方とチームを組ませて頂きました ミーティングPhase エディタはgedit 言語はC++ けしからんマクロは無し 「問題読み終わったよ表」を作る 私は最初にA問…

立命合宿2013 1日目

立命館大学競技プログラミング合宿に参加しています。 現地集合Phase 何もかもが上手くいけば11:30ごろには到着するような予定を組んでいきましたが、残念ながら乗り換えで間違えたり(湖西線と琵琶湖線)、電車が遅れたりして、結局30分ほど遅れて到着しま…

UTPC 2012

東京大学プログラミングコンテスト2012に参加していました(オンラインです) 結果は100+100+50+50でした。野暮用で長時間の参加ができなかったとはいえ、部分点があるコンテストなのですから、もっと貪欲に点数を取って行きたいですね。 A: 2012年12月02日 yy…

Haskell 入門ハンズオン in 明石 #AkashiHaskell 参加記

Haskell 入門ハンズオン in 明石 #AkashiHaskell 明石 Haskell 第1回 - Togetter 主催者の記事 「Haskell 入門ハンズオン in 明石」を主催したよ #AkashiHaskell - 趣味はデバッグ…… 逆ポーランド記法計算機を作ってきました。分からないことをすぐに質問で…

神戸ITフェスティバル2012 参加記

神戸ITフェスティバル 2012 Kobe IT Festival | 第2回 神戸ITフェスティバル 2012年10月5日(金)、6日(土) 入場無料 会場:神戸市産業振興センター 行って来ました。 僕が参加したプログラムは、次のとおりです。 1. 「Web アプリから Windows 8 アプリへ…

AOJ 0571 JJOOII (正規表現解法)

JOI本選の問題です。GCCのバージョンによっては、もしかすると本番でも使えるかも?? 問題文 解法 J, O, I の3種類の文字から成る文字列Sは、どんな文字列であっても (J*)(O*)(I*) の繰り返しによって表されます。 正規表現を利用し、文字列Sをこのパターン…

競技プログラミング用Python最速マスター

LLを使ってプログラミングするときに普段はRubyを使っているのですが,いろいろあってPythonも使い始めました。 何問かAOJでも提出してみたので、手元のメモ書きをリファレンス的に残しておこうと思います。 基本演算 -3 / 2 #=> -2 -4 % 3 #=> 2 入力 raw_i…

TopCoder 12時間マラソンマッチ練習会 Marathon Match 61 Planarity

マラソンマッチ初挑戦でした。結果は案の定6/6位でした。 問題 順位表 提出した後、ちょっと修正したソース問題の概要は次の通り 辺の長さの決まっていないグラフが与えられる。頂点を700*700の平面上の整数座標の任意の点に配置し、辺の交差の数を減らせ 頂…