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

dohatsutsu’s diary

日記を書いています。

【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日の夜になってしまった記事です。

 (遅れてしまい本当に申し訳ありません)

 

www.adventar.org

 

 簡単な自己紹介

ハンドルネーム : 怒髪
プログラミング歴 : 高校1年~大学4年の7年間
競技プログラミング歴 : 高校3年~大学4年の5年間

 AOJ:

http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=dohatsu

AtCoder:

https://atcoder.jp/user/dohatsutsu

 

Twitter:

f:id:dohatsutsu:20161222001328j:plainhttps://twitter.com/dohatsutsu

 

 

 

長くなるのでそれぞれの問題ごとに記事を分けることにしました。

 

1つ目はDraw Puzzle (2014年9月の会津合宿で出題した問題です)

dohatsutsu.hatenablog.com

 

 

2つ目はSum of Numbers (2015年3月の立命館合宿で出題した問題です)

dohatsutsu.hatenablog.com

 

 

3つ目はMonochrome Tile(2016年3月の立命館合宿で出題した問題です)

dohatsutsu.hatenablog.com

【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どうしの重なりが生まれたら必ずマージするようにします。

 

・長方形を追加するのではなく、区間に一様に線分を追加するイメージです。

 

イメージ用のスライドを用意しました。

www.slideshare.net

区間を完全に覆っているものと、一部を覆っているもので分けるテクニックは、蟻本のp163,164 からヒントを得ました。

 

 

問題文が書いてあるページを見るとわかりますが、この問題文には致命的なミスがありました。( H と W が逆になっている )

 

しかしなぜかClarがコンテスト中に来ることはなく、コンテスト終了後にzerokugiさんのツイートでミスが発覚しました。

 

 

その日は深夜まで起きてリジャッジの作業を行いました。

 

その結果、polinkyチームがM問題をACし、2位から1位になるという逆転が起きてしまいました。

 

本当に申し訳ありませんでした・・・。

 

gist.github.com

 

【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通り。

 

この問題にはすでに解説スライドがあります。

www.slideshare.net

 

このスライドの途中で

 {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 の元になった問題のリンクと、その問題を解いたときの提出へのリンクです。

整数の和 | Aizu Online Judge

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=802876#1

 

2011年の11月のある日、蟻本のp66を読んで「すべての数字を1小さくする遷移」に感動した僕はAOJで似たような問題があることを思い出し、この問題をO(ns)で解くことに挑戦しました。

 

このときはまだ動的計画法を勉強し始めたばかりだったので、この遷移が典型なのかそうでないのかなど分かるはずもなく、これが作問のきっかけになるとは思ってもいませんでした。

 

 

それから1年ぐらいが経過した2014年9月、

ビンゴ | Aizu Online Judge

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マスで固定されているところがこの問題の最大の特徴です。

f:id:dohatsutsu:20161220151636p:plain

 

 

 

この問題には次のようなコーナーケース(?)が存在しており、たくさんのWAが出ていました。

f:id:dohatsutsu:20161220152239p:plain

 

この問題の想定解法は動的計画法です。

今いる座標と、どのパネルを何枚持っているかを状態に持ちます。

 

一列に3枚のパネルを置かなければならないケースがあるので、遷移は全部で12種類あります。

パネルを1枚だけ置く4種類の遷移と、まとめて1列に3枚置く8種類の遷移です。

f:id:dohatsutsu:20161220153452p:plain

 

・この問題が出題された会津合宿2014では会津大学だけで2セット作った年で、かなり大変だった思い出があります。

 

・一列に3枚置かなければクリアできないケースをサンプルに入れるべきだったかどうかは当時とても悩みましたが結局入れませんでした。

 

以下は当時学部2年生だった僕が書いたコードです。( 幅優先探索で解いています )

gist.github.com

【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(); }

 

・練習セッションが終わった後は京都大学の人たちと一緒に夕飯を食べに行きました。

・そのあとはホテルの部屋に戻ってTypingWarを15回ぐらいプレイして就寝。

 

2日目

・無事に起床して会場へ向かう。

・A問題はkzykt先輩から概要を聞いて少し考えても全く分からなかった。

・B問題はsate君がTLEを出していて大変そうだったので相談して解くことに。

・考察しても全然分からないけれど順位表を見ると結構解かれているので、仕方なく自信がそんなに無い解法を提出した。

・ACしたものの、すぐに思い浮かんだけれど実装する勇気が出なかった解法だったのでACして辛かった。

・C問題は nの最大値が1,000,000で、O ( n  *  log n   *    log  n ) の解法がすぐに思い浮かび書いてみるがTLEしてしまい辛かった。

・定数倍の高速化を行っても 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しました。

 

・その他の問題は完全にチームメイトに任せていました。

 

 

・最後の5分間が精神的に一番辛かったです。

 

 

【No.028】「ICPC2016 つくば大会 H問題 Animal Companion Maze」

・簡単な問題概要

AIZU ONLINE JUDGE ←問題文へのリンク

 

n個のノードと、m個のエッジで構成されたグラフが入力で与えられます。

ただし、エッジには双方向のエッジと単方向のエッジの2種類があります。

 

そのグラフに閉路があるならば"Infinite"を出力してください。

閉路がないならば、そのグラフで作ることのできるパスの中で最長のものを見つけ、その長さを出力してください。

※自己ループは存在しないが、多重辺は存在し得る。

2≦n≦100000 ,  1≦m≦100000

 

自分が考えた解法

Infiniteの判定パート と 最長のパスを見つけるパート の2つに分けます。

 

続きを読む