【No.028】「ICPC2016 つくば大会 H問題 Animal Companion Maze」
・簡単な問題概要
AIZU ONLINE JUDGE ←問題文へのリンク
n個のノードと、m個のエッジで構成されたグラフが入力で与えられます。
ただし、エッジには双方向のエッジと単方向のエッジの2種類があります。
そのグラフに閉路があるならば"Infinite"を出力してください。
閉路がないならば、そのグラフで作ることのできるパスの中で最長のものを見つけ、その長さを出力してください。
※自己ループは存在しないが、多重辺は存在し得る。
2≦n≦100000 , 1≦m≦100000
自分が考えた解法
Infiniteの判定パート と 最長のパスを見つけるパート の2つに分けます。
続きを読む
【No.027】「AOJ 0537 Bingo」
この記事は、大昔に書いたけれど、なぜか公開されていなかった記事です。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1085385#1
僕のコードが他の人よりもずっと速かったので、解説したいと思います。
dp[ i ][ j ] = 1からMまでの整数の中で i 種類の数字を選び、合計を j にする場合の数
というdp配列を用意し、答えとしてdp[ N*N ][ S ]を出力するのが方針です。
僕なりに考えた漸化式はこうです。
dp[ i ][ j ] = dp[ i ][ j - i ] + dp[ i - 1 ][ j - i ] - dp[ i - 1][ j - M - 1 ]
具体例を挙げると、
(1から9までの整数で、3種類の数字を選んで合計を15にする場合の数)
=(1から9までの整数で、3種類の数字を選んで合計を12にする場合の数)
+(1から9までの整数で、2種類の数字を選んで合計を12にする場合の数)
-(1から9までの整数で、2種類の数字を選んで合計を5にする場合の数)
となります。
とりあえず確認してみましょう。
(1から9までの整数で、3種類の数字を選んで合計を15にする場合の数)
(3+4+8) (3+5+7) (4+5+6)
(2+4+9) (2+5+8) (2+6+7)
(1+5+9) (1+6+8)
合計8種類
(1から9までの整数で、3種類の数字を選んで合計を12にする場合の数)
(2+3+7) (2+4+6) (3+4+5)
(1+2+9) (1+3+8) (1+4+7) (1+5+6)
合計7種類
(1から9までの整数で、2種類の数字を選んで合計を12にする場合の数)
(3+9) (4+8) (5+7)
合計3種類
(1から9までの整数で、2種類の数字を選んで合計を5にする場合の数)
(1+4) (2+3)
合計2種類
8 = 7 + 3 - 2
となり、一致しています。
より詳しい解説
(1から9までの整数で、3種類の数字を選んで合計を15にする場合の数)
というものは、
1を含まないグループ
(4+5+6) (3+4+8) (3+5+7) (2+4+9) (2+5+8) (2+6+7)
1を含むグループ
(1+5+9) (1+6+8)
の2つに分類できます。
１を含まないグループの数は、
(1から9までの整数で、3種類の数字を選んで合計を12にする場合の数)
に対応しています。例えば、
( 3 + 4 + 8 )の場合、
( 2 + 3 + 7 )に対応しています。
（各数字が1小さくなっている）
1を含むグループの数は、
(1から9までの整数で、2種類の数字を選んで合計を12にする場合の数)
に対応しています。例えば、
( 1 + 5 + 9 ) の場合、
( 0 + 4 + 8 ) すなわち ( 4 + 8 ) に対応しています。
（各数字が１小さくなり、1だったものが0となって消える）
しかし、このままだと9種類になってしまいます。
消えた2種類というのは(1+2+9)と(3+9)です。
この2つは、
(1から9までの整数で、2種類の数字を選んで合計を5にする場合の数)
に対応しています。
(1+2+9) の各数字を1大きくすると、
(2+3+10) となり、数字の10が生まれます。
ここで数字の10を取り除くと、
(2+3)になります。
同様に、
(3+9) の各数字を1大きくしたあと、数字の1を追加すると、
(1+4+10) となり、さらに数字の10を取り除くと、
(1+4)になります。
【No.026】「ACM-ICPC2016アジア地区つくば大会の参加記」
順位表 ( 凍結解除済み )
http://icpc.logic.cs.tsukuba.ac.jp/standings/
僕たち 575.cpp 結果は8完で4位でした。(大学順とチーム順の両方とも)
0日目 10月14日(金) コンテスト2日前
朝8時に起床。午前中は3時間ぐらい友達の家でゲームをやりました。
午後はライブラリの確認をしたあとに、AOJで1問解きました。
Modern Announce Network | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
およそ1年前の模擬地区予選に解法を考えただけの問題だったのですが、完全に記憶から抜け落ちていました。途中で一気に当時の記憶が蘇ってきたような感覚になってすっきりしました。
( そのときの模擬地区予選の記事→dohatsutsu.hatenablog.com )
1日目 10月15日(土) コンテスト前日
朝6時に起きてから準備をして大学に向かってライブラリの追加印刷を行いました。
そのときチームメイトの後輩と出会ったのですがその後輩の髪が・・・
会場に到着すると、黄色いTシャツを着た会津大学OBの方々と再会して懐かしい気持ちになりました。
(OBの方々と話しているときにYazaten君と遭遇したので、忘れないうちに会津合宿のときに置き忘れていってしまった充電器を返しました)
懇親会ではいろいろな人と交流しました。(大阪大学の人とか埼玉大学の人とか)
チーム紹介のスライド発表もなんとか無事にやり過ごし、後輩の車でホテルへ戻りました。( このとき道に迷って大変だった )
自分のiPhoneのマップに従い、さて君の車でホテルに移動。
— kzyKT (@kzyKT_M) 2016年10月15日
マップに騙され何もないところに連れて行かれたので、ARCに間に合わなかった。
ホテルに到着した時点で9時を少し過ぎており、ARCはあきらめて、すぐに眠ることにしました。
2日目 10月16日(日) コンテスト当日
朝6時に起きてシャワーを浴びて朝食を食べてコンテスト会場まで移動して・・・
とても朝は忙しかったです。
8時45分、いよいよコンテストが開始。
コンテスト開始と同時に封筒を破ったら封筒の中にある紙も破いてしまって自分でも笑ってしまった。
まずは自分がマシンにログインして環境設定を行いました。
まず、 CapsLockキーをCtrlキーに変えてくれるコマンドをターミナルで打ちます。
次に、僕たちのチームは全員がemacsを使ってコードを書くので、 init.el というファイルを作って flymake の設定を書き込みます。 ( flymake はプログラムの文法を自動チェックしてくれます )
最後、.bashsrc ファイルに
alias g++='g++ -O2 -std=gnu++11'と書くはずが
alias g++='-O2 -std=gnu++11'と書いてしまい1分ぐらいロスしました。
(kzyKT先輩に指摘されて気づきました。)
環境設定が終わった時点で8分ぐらい経過していました。
環境設定が終わったら、手筈通りすぐにkzyKT先輩に交代し、A問題を実装してもらいました。また、交代するとき、C問題のとてもざっくりした概要を聞きました。
C問題は図があるおかげですぐに概要が把握できました。
ある地点に到着するために選べばよいスタート地点のIDの集合は{1,2,3}とか{3,4,5,6}というふうに連続した整数の集合になっていて、{1,3} とか {2,3,6} というように整数が飛んでいることは無い、ということに2分ぐらいで気づいて、それに気づいたら一気に考察が進みました。
後輩がまだB問題の読解に詰まっていたので、先輩がAを解いた後は僕がC問題を書きました。
C問題が解き終わったあとはB問題を担当している後輩に交代しました。
そして先輩からD問題の概要を聞いて、4000C2個の部分文字列のハッシュを列挙できれば解けることが分かり、僕が実装することになりました。
後輩がB問題の実装で詰まったので、交代してもらい、D問題の実装をして提出するもTLEになってしまいました。すぐにD問題を印刷して後輩に交代しました。そして後輩がB問題を書いている間にコードを見直しました。
高速化の方法がハッシュを map に詰めるのではなく、unordered_mapに詰めるようにするしか思いかず、後輩がBを書いている途中に1分だけマシンを交代してもらい、mapをunorderedmapに変えて提出したらACしました。
その後すぐに後輩がBを通してくれて、その時点ではなんと1位になりました。
後輩にF問題を読んでもらい、自分は先輩からE問題の概要を教えてもらうことに。
どうやらE問題は
Lost Number | Aizu Online Judge
とほとんど同じ問題だったので、この問題を解いたことがある僕が実装することになりました。( AOJ-ICPC 埋めをしていて本当に良かったと思いました。 )
E問題を実装している途中で後輩がF問題の解法を思いついたようなので、実装に詰まるたびにマシンを交代しながら実装していきました。
E問題は1回WAを出してしまいました。バグの内容はすぐに見つけることができて、
3文字書き換えるだけでした。
(致命的なバグであることにもかかわらず偶然にもサンプルが一致してしまったようです。)
Eを解いた後、後輩がFのTLEで苦しんでいたので少し相談することに。
コードを読んで高速化のアイディアを出して再び実装してもらい、その間に先輩からG問題の概要を聞きました。
考察をしていくと、「○○ができれば解ける」という閃きから、「○○をやるためには、□□ができなければならない。」→「□□をやるためには、△△ができればよい」というふうに徐々に前に進んでいって最終的な解法にたどり着くことができて面白かったです。
(とはいえ、もっといい方法がある可能性が高いです・・・)
F問題を担当している後輩とときどきマシンを交代しながらG問題を実装していきました。
コンテスト開始から2時間19分経過した時点でG問題がACしました。
G問題がACした後はF問題を完全に後輩に任せたまま、先輩と一緒にI問題の考察をしたり、J問題を読んだりしました。
J問題は、円と凸多角形の共通面積を求めるライブラリを持っていたので、「これは解くしかない」となりました。
会津大学OBのzukkyさんとNCAstarさんが作ってくださった円と凸多角形の共通面積を求めるライブラリを頑張って書き写して、それを印刷して先輩に書き写しのミスがないかチェックしてもらって、2重の、 3分探索を書いてACしました。
書き写しのミスが2,3箇所あったので、見つけてくれたkzyKT先輩には本当に感謝しています。
zukkyさんとNCAstarさんにも感謝です。
俺が後輩チームに残したライブラリの中で、NCA君が作った問題のテストのために必死こいて作った円と多角形の共通面積を求めるライブラリが本番で大活躍したみたいで、最高に熱い展開だ
— zukky (@zukky162) 2016年10月16日
J問題がACした時点ですでに残り時間は74分でした。
順位表を見るとF問題とI問題が解かれていて、僕は後輩のサポートをすることにしました。
後輩が実装している方針をもう一度聞いて、コードを読み直すと、すぐに駄目なケースが思いつきました。解法の基本的な方針はあっていそうだったので、解法の詰めの部分を一から考察しなおすことにしました。
なんとか時間内に正しい解法にたどり着き、後輩に実装してもらって1回WAを出しながらもACしました。F問題を解き終えた時点ですでに順位表は凍結されており、残り時間は18分になっていました。
残り時間では、I問題に先輩や僕が直感で考えた解法で挑戦したもののダメでした。
表彰式では1,2,3,5位のチームが壇上に立って商品を貰っていて、悲しかったです。
コンテスト終了後、懇親会へ。
懇親会では企業ブースで出題されたクイズを解くことに夢中で、あまり食べることができませんでした。
表彰式で景品をもらえなかったチームの中で最も上位だったためKlab社からモバイルバッテリーをもらうことができました。とてもうれしかったです。
チームの名前がアナウンスされても後輩がなかなか姿を壇上に表さず、何枚かは後輩がいないまま写真を撮ったりしました。
あと、その場の勢いでそのとき近くにいた会津大学OBの方とも一緒に写真を撮りました。
懇親会のあと、いったんホテルの部屋に戻って荷物を置いたあと、
一部のコンテスト参加者たちとの2次会に参加しました。
(ホテルの部屋に戻ったとき、筆箱を置き忘れてしまったことが発覚して、ちょっと大変でした。)
こういうときにしかできないい話をいろいろ聞いたりできて楽しかったです。
2次会が終わってホテルの部屋に戻るとき、 kyuridenamidaさんに突然「頭がいい」と言われました。
3日目 10月17日(月) コンテスト翌日
後輩が2次会のあとカラオケに行ったらしく、寝不足でしたが無事に会津に到着できました。会津に着いてからはニコニコのタイムシフトでつくば大会の生放送を見ました。
おまけ ニコニコのタイムシフトの感想
結構会津大学の話が出ていて驚きました。
生放送で僕らのチームのページが表示されたときのことを考えて、順位表の自己紹介欄にAtCoderのIDを載せていたので、良かったです。
( chokudai さんが、topcoderのidはあるのにatcoderのidがないことを嘆く→僕がidを書いていることに気づく という流れがまさか本当に実現するとは思わなかった。)
怒髪という名前から、青い髪の毛の人だと勘違いされそうになったり、コメントで何度も青髪DQNのチームとよばれていたりして悲しかった。
【No.025】「 会津合宿 2016 参加記」
1日目 立命館セット
ryohatsuxx というチームで参加しました。(オンライン6位)
http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=ACPC2016Day1
.@dohatsutsuさん .@mot_xxさんと 出ます．よろしくお願いします！！
— Ry0u_ (@ry0u_yd) 2016年9月17日
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
F問題です。 pic.twitter.com/vQgd6TmXZ8
— ぴゃ (@snuke_) 2016年9月18日
コンテスト終了後、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_1213 さんとで energy_star というチームで参加していました。オンラインで2位という好成績。
— 怒髪 (@dohatsutsu) 2016年9月19日
Yazaten君とtookunnさんにAとBを書いてもらい、自分はC問題とF問題を担当しました。
F問題でもバグを埋め込んで4WAしてしまいました。Ford Fullkerson法で通しましたが1.85secもかかっていて、 制限時間ギリギリで危なかったです・・・。
GはYazaten君と一緒に考察した結果、凸法をして頂点数を少なくしたあと、どの辺を長方形の辺と重ねるか全部試す方針で実装することになりました。
INFの値が小さくて1WAしましたが無事ACしました。
【No.024】「 JAG 夏合宿 2016 参加記」
今年もJAG夏合宿に参加しました。これで3回目の参加です。
（ちなみに過去のJAG夏合宿の参加記は書いてないです）
1日目
朝早起きして会津から電車で郡山へ。そこからさらに新幹線で東京へと移動します。
（いつものやつです）
参宮橋駅で横浜国立大学の人たちに遭遇し、一緒に歩いてオリンピックセンターへ移動しました。
会場が開くよりも前に到着してしまったので、1階のソファーで会話をしながら待つことに。（ダンガンロンパの話とか今日泊まる部屋についてとか）
ガイダンスとシーツの受け渡しが終わったあとはトランプをして寿司を食べてアルゴリズムの話をしたりしました。
気が付くと深夜2時くらいになっていました。同じ部屋だった人に申し訳ない・・・。
2日目
寝不足でコンディションは良くないけど、頑張って起きて朝食を食べてコンテストに挑む。
http://jag2016summer-day2.contest.atcoder.jp/standings#page_1
L問題のFirstACができたのでうれしい。
I問題のデバッグに時間がかかったことは反省。
3日目
きちんと睡眠をとって、LINE社の会場で模擬地区予選に参加。
とにかくC問題のデバッグに時間をかけすぎたことが最大の反省点。
あとでH問題は解いておきたい。
4日目
アメリカに行かなければならないため、Klab社の会場に行って少し挨拶だけして離脱しました。
まとめ
全体的にデバッグに時間を掛けすぎていて、実装する前に方針を固める作業を多めにとるようにしないといけないなと思いました。
【No.023】「参加記」
書こうと思っていたけど結局書いていないプログラミングコンテスト参加記
・2016年5月のICPC世界大会
・2016年6月のICPC模擬国内予選
・2016年6月のICPC国内予選
どうしよう・・・
とりあえず2016年9月のJAG夏合宿の参加記を書いてから考えよう・・・
【No.022】「AOJ 2181 Neko's Treasure 」
AOJ-ICPC 難易度550の問題です。
Neko's Treasure | Aizu Online Judge
問題概要
二次元平面のなかに、2つの点と、nつの円の候補がある。
nつの円の候補の中から任意の数だけ実際に設置する円をえらび、
2点の間を移動するとき（回り道をしてもかまわない）に横切らなければならない円の数の最小値
を最大化しなさい。
ただし、実際に設置する円のなかで、互いに触れ合っているか交差している円があってはいけない。
完全に内包しているか内包されている円はあっても問題ない。
考察
2つの点両方を内包している円は設置する必要はない。
同様に、2つの点両方が外側にある円も設置する必要はない。
よって、設置するのは、どちらか片方の点のみを内包している円だけで十分である。
設置する意味の無い円の例
2つの点を内包している
どちらの点も内包していない
解法
選ぶ円の組み合わせは全部で3つのパターンがある。
・「点Sのみを内包している円」しか選んでいないパターン
・「点Tのみを内包している円」しか選んでいないパターン
・「点Sのみを内包している円」と「点Tのみを内包している円」の両方が選ばれているパターン
最初の2つのパターンについては、動的計画法で簡単に求めることができる。
ノードの数が円の数と等しく、円iが円jを内包している場合にノードiからノードjにエッジが伸びている有向グラフを考えると、答えはそのグラフでに最も長いパスの長さになるからである。
（ちなみに半径の長さでソートすることがトポロジカルソートになる）
最後のパターンについては、「点Sのみを内包している円」の中で最も外側にある円と「点Tのみを内包している円」の中で最も外側にある円を二重ループで決めうちすれば最初の2つのパターンと同じになり、動的計画法に使用した配列を参照すればそれぞれの決め打ちした円のペアについて、O(1)で最大値を求めることができる。
ACしたソースコード
AIZU ONLINE JUDGE: Code Review
