【No.035】「KUPC2017オンサイト参加記」
9/30
朝5時のバスに乗るため早めに寝ようと思っていたのだが、21~23時の間にAtCoderで天下一プログラマコンテスト*1が開かれていた上に、自転車が突然故障*2したので仕方なく大学でずっと起きていることに。
10/1 AM
徒歩で駅前まで移動してそこからバスに乗り、朝10時ごろにやっと東京駅に到着。秋葉原で少し時間をつぶした後で会場に向かった。
10/1 PM
コンテスト会場で知っているTwitterのフォロワーや大学OBの先輩に軽く挨拶をした。
肝心のコンテストの結果は・・・
最初の1時間で序盤の問題を解ききった後、残りの4時間は苦手な構築要素とリアクティブ要素を持っているG問題にボコボコにされて順位が40下がりました。(ジャッジ結果にREが存在せず、assertを使ってもWAになってしまうトラップにかかったのは僕だけじゃないはず)
ちなみにH問題(ポーションのやつ)の1WAは適当な貪欲解によるものです。解説を聞いて面白いと思ったので後で通したくなりました。
懇親会ではマネーというボードゲームで遊んで完敗しました。もう少し考えてプレイすればよかったなぁ。
(まだ2ゲームしかプレイしていないのでよく分かりませんが、誰が上位でどの種類を集めているのかが分からないと妨害ができないというかあまり面白くないので他プレイヤーの手札を記憶する力が欲しいなと思いました。)
【No.034】「 AOJ 2376 Disconnected Game」
AOJ 2376 Disconnected Game
問題文
http://judge.u-aizu.ac.jp/onlinejudge/IMAGE/winter-camp-2011-day3.pdf#page=15
AOJ-ICPC 難易度600にあった問題です。
今回は解説記事ではなくて、自分の考察の過程のメモという感じになります。
( 問題のネタバレを含みます )
続きを読む
【No.033】「過去に作った問題の解説を書きながら振り返ってみる」
この記事はCompetitive Programming Advent Calendarr 2016 の12月19日の記事のはずでしたが、公開日が12月21日の夜になってしまった記事です。
(遅れてしまい本当に申し訳ありません)
簡単な自己紹介
ハンドルネーム : 怒髪
プログラミング歴 : 高校1年~大学4年の7年間
競技プログラミング歴 : 高校3年~大学4年の5年間
AOJ:
http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=dohatsu
https://atcoder.jp/user/dohatsutsu
https://twitter.com/dohatsutsu
長くなるのでそれぞれの問題ごとに記事を分けることにしました。
1つ目はDraw Puzzle (2014年9月の会津合宿で出題した問題です)
2つ目はSum of Numbers (2015年3月の立命館合宿で出題した問題です)
3つ目はMonochrome Tile(2016年3月の立命館合宿で出題した問題です)
【No.032】「AdventCalendar用の記事(3つ目)立命館合宿2016 2日目 会津大学セット M問題 Monochrome Tile (RUPC2016 Day2 M)」
自分が過去に合宿で出題した問題の中から3つ選び、簡単な解説と当時の感想などを書いていきます。(この記事はその3つ目です)
立命館合宿2016 2日目 会津大学セット M問題 Monochrome Tile (RUPC2016 Day2 M)
問題URL
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=M
簡単にまとめると、次のクエリを高速に処理する問題です。
・x軸、y軸に平行な辺を持つ長方形の左上の座標と右下の座標が与えられる。すでに追加されてある長方形のいずれかと重なってしまうかどうかを判定し、もし重ならないのならばその長方形追加する。重なってしまうのならば追加しない。
この問題の想定解法はセグメントツリーです。
それぞれのノードには、set< pair<int,int> > を2つ持たせます。
片方には、そのノードに対応する区間を完全に覆っている長方形の上端のy座標と下端のy座標をpairにして入れるようにします。
もう片方には、そのノードに対応する区間の一部を覆っている長方形の上端のy座標と下端のy座標をpairにして入れるようにします。
このとき同じsetの中でpairどうしの重なりが生まれたら必ずマージするようにします。
・長方形を追加するのではなく、区間に一様に線分を追加するイメージです。
イメージ用のスライドを用意しました。
・区間を完全に覆っているものと、一部を覆っているもので分けるテクニックは、蟻本のp163,164 からヒントを得ました。
問題文が書いてあるページを見るとわかりますが、この問題文には致命的なミスがありました。( H と W が逆になっている )
しかしなぜかClarがコンテスト中に来ることはなく、コンテスト終了後にzerokugiさんのツイートでミスが発覚しました。
MのWAの原因が分かった 問題文の入力の欄のHとWが逆になっていてそれに従って書いたせいでセグ木の長さが足りてなかった WとHを逆にしたら通った
— zerokugi (@zerokugi) 2016年3月7日
その日は深夜まで起きてリジャッジの作業を行いました。
修正前の問題文に合わせ、1行目の2つの整数、HとWの値を入れ替えたテストケースにより、リジャッジを行いました。
— 怒髪 (@dohatsutsu) 2016年3月7日
現在リジャッジは終了しており、順位表もそれに応じて更新しました。
順位表のURLhttps://t.co/G7CqyNFo39#rupc2016
その結果、polinkyチームがM問題をACし、2位から1位になるという逆転が起きてしまいました。
本当に申し訳ありませんでした・・・。
【No.031】「AdventCalendar用の記事 (2つ目) 」
自分が過去に過去に合宿で出題した問題の中から3つ選び、簡単な解説と当時の感想などを書いていきます。(この記事はその2つ目です)
立命館合宿2015 2日目 会津大学セット F問題 Sum of Numbers (RUPC2015 Day2 F)
問題URL
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp15Day2&pid=F
a以上b以下の整数が書かれたカードがc枚ずつあります。
これら c ( b - a + 1 ) 枚のカードの中からちょうどd枚のカードを選択したとき、それらのカードに書かれてある整数の合計がちょうどeになる場合の数を1,000,000,007 で割った余りを求めてください。
1≦a≦b≦1000
1≦c≦100
1≦d≦1000
c≦d≦c(b-a+1)
1≦e≦20000
a=2,b=5,c=3,d=3,e=11の場合
{2,2,2,3,3,3,4,4,4,5,5,5}の中から3枚選び合計が11になるのは、 {2,4,5},{3,3,5},{3,4,4}の3通り。
この問題にはすでに解説スライドがあります。
このスライドの途中で
{2,2,3,3,4,4,5,5,6,6} の12枚の中から
という表現が何度か出てきますが、それらはすべて
{2,2,3,3,4,4,5,5,6,6} の10枚の中から
の間違いです。 ( 2016年の忘年会のときに気づきました )
----------
この問題が出題されたのは2015年3月ですが、実は問題の核となる部分を思いついたのは2013年の11月(当時学部1年)でした。
以下のURLは、スライドの最後に書いてあるように、Sum of Numbers の元になった問題のリンクと、その問題を解いたときの提出へのリンクです。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=802876#1
2011年の11月のある日、蟻本のp66を読んで「すべての数字を1小さくする遷移」に感動した僕はAOJで似たような問題があることを思い出し、この問題をO(ns)で解くことに挑戦しました。
このときはまだ動的計画法を勉強し始めたばかりだったので、この遷移が典型なのかそうでないのかなど分かるはずもなく、これが作問のきっかけになるとは思ってもいませんでした。
それから1年ぐらいが経過した2014年9月、
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1085385#1
ビンゴという問題をO(N^2 S)で解きました。解いたあとにほかの人の提出を見るとO(N^2 MS)で解かれていて、不思議に思って公式の解説のページを見に行きました。するとそこでも想定解がO(N^2 MS)になっていました。
このときはじめて「すべての数字を1小さくする遷移」を使った問題を作ろうと思うようになり、2015年3月にSum of Numbersが出来上がりました。
【No.030】「AdventCalendar用の記事 (1つ目) 」
自分が過去に合宿で出題した問題の中から3つ選び、簡単な解説と当時の感想などを書いていきます。 (この記事はその1つ目です)
2014/9/24 会津合宿2014 1日目 D問題 DrawPuzzle (ACPC2014 Day1 D)
問題URL
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day1&pid=D
長方形のフィールドと持っているパネルについての情報が入力で与えられるので、フィールドの右側から左側への道を作れるかを判定する問題です。
フィールドはグリッド状になっており横に何マス並んでいるのかは入力で与えられますが、縦に並んでいるマスの数は必ず3マスで固定されているところがこの問題の最大の特徴です。
この問題には次のようなコーナーケース(?)が存在しており、たくさんのWAが出ていました。
この問題の想定解法は動的計画法です。
今いる座標と、どのパネルを何枚持っているかを状態に持ちます。
一列に3枚のパネルを置かなければならないケースがあるので、遷移は全部で12種類あります。
パネルを1枚だけ置く4種類の遷移と、まとめて1列に3枚置く8種類の遷移です。
・この問題が出題された会津合宿2014では会津大学だけで2セット作った年で、かなり大変だった思い出があります。
・一列に3枚置かなければクリアできないケースをサンプルに入れるべきだったかどうかは当時とても悩みましたが結局入れませんでした。
以下は当時学部2年生だった僕が書いたコードです。( 幅優先探索で解いています )
【No.029】「ICPC 2016 韓国 Deajeon 参加記 ( 書きかけ ) 」
2016/11/6/1:25 この記事はまだ書きかけです。
0日目
・集合時刻を勘違いをしていて、本来乗る予定だった電車が出発した数分後に会津若松駅に到着。
・チームメイトは本来予定していた電車に乗って先に移動していたけれど、先生は僕のために駅に残ってくれていたので、先生と一緒に成田まで移動してチームメイトと合流。
・飛行機で成田空港から仁川国際空港へ移動した後、そこからさらにバスで大田まで数時間の移動。
・バスの中でツイッターをしていたら、実は飛行機に乗っている間にchokudaiコンテストが開かれていたことに気づく。参加できなくて残念。
・東横インに着いたときにはすでに午前1時ぐらいになっていた。
・近くのセブンイレブンに行ってアイスとぶどうジュースを購入した。
・テレビのチャンネルを適当に変えていたらムーミンが放送されていた。
1日目
・午前中はほとんどホテルの部屋で眠っていた。
・タクシーで会場まで移動してKAISTの食堂で昼食を食べた。
・練習セッションの問題はつくば大会のときよりもずっと難しかった。
・sate君にコンパイルエラー(というよりはwarning)の原因を相談されたのでコードを見てみると、return 文を書き忘れていた。
double dot(P a,P b){ a.real()*b.real() + a.imag()*b.imag(); }
・練習セッションが終わった後は京都大学の人たちと一緒に夕飯を食べに行きました。
— kzyKT (@kzyKT_M) 2016年11月4日
・そのあとはホテルの部屋に戻ってTypingWarを15回ぐらいプレイして就寝。
2日目
・無事に起床して会場へ向かう。
・A問題はkzykt先輩から概要を聞いて少し考えても全く分からなかった。
・B問題はsate君がTLEを出していて大変そうだったので相談して解くことに。
・考察しても全然分からないけれど順位表を見ると結構解かれているので、仕方なく自信がそんなに無い解法を提出した。
・ACしたものの、すぐに思い浮かんだけれど実装する勇気が出なかった解法だったのでACして辛かった。
・C問題は nの最大値が1,000,000で、O ( n * log n * log n ) の解法がすぐに思い浮かび書いてみるがTLEしてしまい辛かった。
序盤( B問題とC 問題 ) のミスで時間と体力をかなり消耗してしまった・・・
— 怒髪 (@dohatsutsu) 2016年11月5日
・定数倍の高速化を行っても TLE が消えなかったので、チームメイトに高速化の案を出してもらうことに。
・sate君が sort関数によって発生する計算量を消す方法を実装してくれてACしました。
・D問題はkzykt先輩から概要を聞いたとき、与えられるグラフが2部グラフかどうかが分からなかった。
・2部グラフじゃないと解ける気がしなかったので、問題文を読んでみることに。
・入力で与えられるグラフは2部グラフであることが保証されていたので、ライブラリのbipartite_matchingを写す。
・bipartite_matching 2回分の計算量なのにもかかわらずTLEがでて辛かった。
・定数倍改善をしたらTLEがとれてACしました。
・E問題はコンテスト終了2時間前に実装し始めた問題で、すでに体力がかなり消耗していたので辛かった。
・' ) 'の構文チェックを忘れていることにkzykt先輩が教えてくれました。
・何度か見直してもバグっているところがなさそうだったので、ハッシュが衝突している可能性に賭けてみることに。
・ハッシュ値のmod を 2の64乗から 1,000,000,009にするとACしました。
・その他の問題は完全にチームメイトに任せていました。
最後の15分間はsate君がH問題のデバッグをしていました。コンテスト終了まで残り4分ぐらいになったところでpcの電源が突如落ちる事故が発生して・・・・
— 怒髪 (@dohatsutsu) 2016年11月5日
・最後の5分間が精神的に一番辛かったです。