ACM/ICPC

ACM-ICPC OB/OGの会主催 模擬国内予選 A〜D解説

先日行われたACM-ICPC OB/OGの会主催の模擬国内予選のA, B, C, D問題の解説を国内予選突破の手引きにアップしました。OB/OGの会の解説をベースに,冗長に,その分ちょっと分かりやすく書いています。国内予選突破を確実にするには,この問題セットではA, B, …

今年度のACM/ICPCの日程

ACM-ICPC OB/OGの会主催 2007年度 模擬国内予選 - 6月24日(日) 2007年度 日本国内予選 - 7月6日(金) アジア地区予選東京大会 - 11月2日(金)〜3日(土) 国内予選まで後1ヶ月を切りましたね。選手の皆さんはがんばってください!

単純なSPF問題はいずこ?

「ACM/ICPC国内予選突破の手引き」を大幅に更新しました。ここ3年間ほどの国内予選などで出題された問題を,簡単な問題から順次解説を載せていっています。ただいま23問。2週間前は20問くらいしか載せないとか言っていましたが,意外と揃ってきてしまいまし…

LCS (Longest Common Subsequence)

現実逃避的にACM/ICPC国内予選突破の手引きのコンテンツを更新しました。とりあえず簡単な問題をいくつか載せたのと,少し分かってきた人向けにDP系の問題を少し載せてみました。LCS (Longest Common Subsequence: 最長共通部分列) の解説が目玉です。ここら…

ACM/ICPC国内予選対策サイト

学内でやっている勉強会のためにACM/ICPC国内予選突破の手引きというコンテンツを書き始めました。学内だけに公開するのももったいないなのでオープンにします。といっても,とりあえず今のところは体裁を整えただけです。勉強会が進むにつれて少しずつコン…

Power Calculusのダイクストラ解法のダメ出し

http://d.hatena.ne.jp/deq/20061108/1162956585あたりで取り上げた2006年度のアジア地区予選横浜大会の問題F Power Calculus*1ですが,echizen.comのoxyさんから「そのノードへの最短ステップ数が最小でないパスは排除しているけれども,そういうような排除…

問題F Power Calculus を枝刈り

おお,この問題って全探索+枝刈りで解けたんだ。びっくり。

ACM/ICPC 2006 アジア地区予選 横浜大会 結果

ACM/ICPC 横浜大会 に参加して帰ってきました。結果(速報)はこちら。僕らのチーム Hanafuda Shuffle GIVEUP orz は意外と健闘できて10位でした(まともな成績が残せてしまった)。日本チームでは8位。日本の私立大学では1位なのかな。アジア地区予選初進出…

ACM/ICPC 2006 アジア地区予選 横浜大会

明日から ACM-ICPC 横浜大会に行ってきます。まともな成績を残せるとは思っておりませんが。まぁ,精一杯楽しんできます。:-)それから帰ってきたら「人類の情報革命史」と題した文章をまとめていきたいと思います。

全宇宙生命ゲノムデータベース (Problem E, 2006 Japan Domestic)

ICPC国内予選が終わりました。順位表と問題セットが公開されています。この順位表によると,4問以上解けたチームは210チーム中たったの12チーム。これらのチームが解いた問題はおそらくABDEでしょう(5問解けた2チームがCとFのどちらを解いたのかは気になり…

平面幾何 [ソースコード]

平面幾何の第2回から第4回で出てきたプログラムのまとめです。ICPCではWebは参照できないので印刷しておきましょう。:-)

平面幾何 [4/4]

前回に引き続き平面幾何の第4回です。今回扱っている話題は 直線と点の距離 線分と点の距離 線分の交差判定 線分の交点計算 直線の交点計算 です。

平面幾何 [3/4]

前回に引き続き平面幾何の第3回です。今回扱っている話題は, 内積・外積 2直線の直交判定・平行判定 点が線上にあるかないかの判定 です。

平面幾何 [2/4]

さて,前回の平面幾何の続きです。今回扱っている話題は complex型の導入 絶対値,2点間の距離,単位ベクトル 法線ベクトル,単位法線ベクトル です。

平面幾何 [1/4]

ACM/ICPC国内予選の直前になりましたが,今回はICPC頻出の平面幾何について基本的なベクトル演算を押さえておきます。今回扱っている話題は デカルト座標系とユークリッド空間 スカラーとベクトル 点とベクトル ベクトルの和と差 です。

模擬国内予選の結果

OB/OGの会の模擬国内予選が終了しまして,その結果(順位)および講評・問題セットが掲載されました。うちのチームは4問(A, B, C, D)解いて18位でした。常連3大学以外では健闘してる方でしょう。選手層の厚さの違いは拭いようがないけれども。それを考える…

ACM/ICPC国内予選参加者

横浜大会に向けてのACM/ICPC国内予選の参加登録が終了しました。今年はこの210チームが参加するようです*1。東京大学などの上位を複数占める一部の大学を除けば,だいたい210チーム中50位以内に入れば国内予選は突破できるでしょう(おそらく3問解答が境界線…

The Secret Number (Problem C, 2003 Japan Domestic) [3/3]

2003年度国内予選の "http://www.acm-japan.org/past-icpc/domestic2003/C.htm" 問題の解説の第3回目です。第1回目はこれをDP(動的計画法)で解き,第2回目はmemoize(メモ化)の説明を行いました。今回はmeomizeを用いたメモ化探索で本問題を解いてみまし…

模擬国内予選(ACM-ICPC OB/OGの会)

今年もやって参りました。ACM-ICPC OB/OGの会の模擬国内予選です。ACM-ICPCの本大会(国内予選)と同じ問題形式で,ほぼ同程度の内容(難しさ)の問題が出ます。国内予選を勝ち抜きたい方は参加必須でしょう。開催日時は6月18日の日曜日。スケジュールは: 1…

The Secret Number (Problem C, 2003 Japan Domestic) [2/3]

前回はDP(動的計画法)で "http://www.acm-japan.org/past-icpc/domestic2003/C.htm" を解きました。今回と次回ではこれをmemoize(メモ化)で解いてみることにします。さて,前回は全探索時の計算量を(組み合わせ論の知識を用いて)解析的に求めました。…

The Secret Number (Problem C, 2003 Japan Domestic) [1/3]

大阪工業大学情報科学部内の学生向けにACM/ICPCの勉強会を最近開いています。目標は国内予選突破(まずはね)。その勉強会では主に過去の国内予選の問題を解かせてますが,それらの問題の(僕なりの)解答や解き方をここに載せていこうと思います。ちなみに…