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

dohatsutsu’s diary

日記を書いています。

【No.025】「 会津合宿 2016 参加記」

 

1日目 立命館セット

 

ryohatsuxx というチームで参加しました。(オンライン6位)

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=ACPC2016Day1

 

C問題とE問題は僕が担当しました。

C問題はいろいろバグを埋め込んでしまって3WA。なかでもaとbを逆にしてしまうバグはひどかった・・・。

E問題ではグラフが完全に構築されるまでクエリを投げ続ける解法を試した後、グラフを完全に構築する必要がないことに気づいて「なるほど」と思いました。

( flushするのを忘れていてWAを出してしまい申し訳なかった )

 

D問題はry0u_ydさんと相談して解法を考えてもらい、僕が実装して解きました。

ry0u_ydさん、ありがとうございました。

 

 

 

2日目 会津大学セット

 

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2016Day2

寝坊してしまい13時ごろに大学に到着しました。

到着してすぐに自分の作った問題のClarを確認し、重要なものがなかったので一安心。

 

僕が作ったのはDとFとJとM問題でした。

ここで少し作問側の感想を書きたいと思います。

 

D問題 

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=D

思っていたより正答率が低かったです。

 

「ほんの少しだけ変わったダイクストラの問題を出したい」と思っていろいろなグラフを書いていたら、「エッジに使用できる時刻が限定されたグラフ」というのを思いついたことがきっかけでこの問題が生まれました。

 

(ストーリーはコンテスト前日の夜になってから急遽付け足したものなので、橋が一方通行になってしまうという違和感が生まれてしまいました)

 

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=F

 

 

コンテスト終了後、snukeさんがツイッターGIFアニメーションを投稿してくれました。

そのときちょうどFの解説を書いている途中だった僕はほんの少しやる気を失いました。

 

もともとは石(ストーン)が2個以下しか存在しないという制約で出題しようと思っていたけれど簡単すぎるなぁと思ってボツにしていました。

しかし数日後、石が3個以上あればクリアできることに気づいて出題できるようになりました。

( 問題の概要をジャッジのメンバーに説明しているときにH=1またはW=1のときに石が3個以上あってもクリアできない可能性があることに気づきました。)

 

HとWの制約をどちらも1以上16以下に設定したのは。 H=1またはW=1 のときに全探索ができるからです。とはいえO( 石の数 )でも解けますが・・・。

 

 

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=J

面白い問題ができたと思っていましたが、既出だったらしくて残念でした。

 

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=M

最初は回数だけを出力させるつもりでしたが、ある日辞書順最小の最小カットを求める方法が分かったのでより難しい問題を作ることできました。

 

 

 

3日目 北海道大学セット

 

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2016Day3

 

 

Yazaten君とtookunnさんにAとBを書いてもらい、自分はC問題とF問題を担当しました。

F問題でもバグを埋め込んで4WAしてしまいました。Ford Fullkerson法で通しましたが1.85secもかかっていて、  制限時間ギリギリで危なかったです・・・。

 

GはYazaten君と一緒に考察した結果、凸法をして頂点数を少なくしたあと、どの辺を長方形の辺と重ねるか全部試す方針で実装することになりました。

 

INFの値が小さくて1WAしましたが無事ACしました。