AOJ 1194 : Vampire
トラウマ問題
問題概要
- N個の長方形が与えられます。
各長方形の下底は必ずX軸に接している。 - 半径Rの円が(0,-R)が秒速1で上に上がっていきます。
- 円が長方形に覆われなくなった瞬間の時間を答えて下さい。
- 長方形同士で重なったりもあるので注意。
解法
続きを読むACM ICPC 2015 アジア地区予選 つくば大会 参加記
We are 
ということ、2015/11/28~11/30 のICPCアジア地区予選つくば大会にFinalZukkyというチームで出ました。
ちなみに、Team Introductionのときに使ったこの画像はこの時に作られていた。
久々に良い絵描いたぞ～
— さて (@public_sate) 2015, 11月 11
初日
- 4:00
起床：昨日作った肉なし焼きそばを朝食に食べる。 - 6:20
出発：バス停についた怒髪さんがいなくて少し焦るが無事間に合う - 13:00頃
ICPCっぽい４人組をちらほら見かける。
みんなで合流してつくばカピオへ - 14:00~
受付→開会式的なの - 15:00~
練習セッション
トイレが一人しか入れないという制約に危機感を覚える
俺がトイレに５分こもるだけで何人かqueueにたまっていて申し訳ないきもちになる。 - 16:00~
Compile Challenge
Java Challenge
ほぼWaiting、端で待って両端をうちまくるのを一応出した。
端に行くプログラムを書いたのになぜか端からちょっとずれていたのでこれr,c 1-baseで与えられるのでは？という疑惑が浮上。 - 19:00~
懇親会
焼きそば食う
Team Introductionがわりと受けてよかった。
CodeFesのときのあまり良くない評判が何故か少しひろまっていた。 - 21:00~
宿泊施設に着く（までに結構迷う）
つくば勢が当日に宿泊ができないことを嘆いていた最高だと言っていた。
明日はコンテストなので、風呂入って歯を磨いて早く寝よう - ~1:30
この時間まで自分の部屋でみんなで騒いでいた。
cubicがスミノフを飲み干すに飽きたらず僕のレッドブルまで奪って飲んでいた。
就寝
当日
- 7:00
起床
「さて、昨日俺の部屋にいたやつらの様子を見に行くか」と部屋を覗きに行ったらcubicだけ死んでいた。 - 8:00頃
僕と高校の同級生で部屋で集まっていたら、突如ドアがバタンと開く。
cubic「おまえ、レッドブル許さんからな」
どうやら昨日飲んだレッドブルのせいで寝れなかったらしい。いや、自分から飲んでたじゃないか。 - 9:00頃
会場について、しばし待った。 - 9:20~
ACM ICPC 2015 アジア地区予選 つくば大会
- A問題
どはつさん - B問題
読んだ、やりたくない頼んだZukky - C問題
説明された、回数決めてDPやろう
ステップによる遷移を求める時にメモ化してなくてTLE（あほ）
直してAC - D問題
どはつさんがCを解くよりさきにいつの間にか通していた。
この時点で２位でテンションがやばかった。
- E問題
どはつさん - F問題
俺 - G問題
Zukkyさん
G問題が解けた時が最高潮だった。
- H問題
図を見るだけでやばそう、読んでない - I問題
実は愚直でとおる？？とか思ったけど結局実装しきれず - J問題
強連結成分分解すると頂点数10以下のDAGになるという記述でうぇいかとおもったが全然そんなことはなかった。 - K問題
アリスが最後に置く時の結果までは全探索コードと一致して考察あたってたけど、ボブが最後に置く時がわからん。
コンテスト中の詳しい内容は怒髪さんかZukkyさんのブログでしてくれてるはず。
僕が担当した問題は CとFでした。
強い二人が難しい問題を考えたり解いたりするのを邪魔しないように僕が簡単な問題を解いていたらなんか凄い順位になっていた。
先輩方に圧倒的感謝！！
- 14:20~
時が止まる - 14:40(?)~
そして時が動き出す。 - 15:00~
解説とか
JavaChallengeの結果とか
うちのチームのAIは相手が目の前にいると動けなくなるの忘れててそもそも端に行けずに死亡。 - 17:00~
閉会式＆結果発表
FinalZukky 6th
やったああああああ！！！！
かなり調子良かったので発表まで期待と緊張でいっぱいだった。壇上でなんか話すとは思わなくて意味不明なことを言った気がする。
- 19:00~
懇親会
企業ブースあさりじゃあああ
フェイスブックニット帽がGETできたの最高
会津では必需品なので冬場は毎日つけます。
焼きそばも食う。 - 21:30~
飲み会うぇーい - 24:30~
作問うぇーい - 28:00頃
つい消しうぇーい
就寝
後日
- まじで眠い
- シャワーを浴びる
- お湯が出ない。温水プールみたいなめっちゃぬるい水が出る。
- クソ寒い、死ぬ、助けて
- 介護を助けるパワードスーツによって訪れる素晴らしい未来を予想するビデオが見れると思ったら
エロ親父が作ったB級ヒーローアクションを見た。 - 加速する眠さ
- 15:00
解散
お疲れ様でした。
初めての国内のアジア地区予選でこんないい成績がとれるとは思いませんでした。WorldFinal期待して良いと思うので精進してチームに貢献できるようにならなくては！！！あと英語
最終結果
6 / 42 (Team) 位
大学別 5位 (国内2位)
(※6位の景品のけんだまです)
JAG2015模擬地区予選K：Optimal Tournament
問題↓
jag2015autumn.contest.atcoder.jp
問題概要
- N人でトーナメントを行います。
- 各人には強さAiが与えられていて、iとjが戦った時コスト|Ai - Aj|が発生し、必ず強さの大きいほうが勝ちます。
- トーナメント表の深さをK以下にしたいときコストの総和の最小値を出力して下さい。
- N<=1000
- K<=50
解法
続きを読むCODE FESTIVAL 2015 参加記
行ってきました！前泊勢です。
金曜日
- 11:30頃
品川着
ポルンガが財布無くたせいでなかなか来ないので髪切って待つ - 14:00頃
合流、"怠惰の魔神"もいた。
腹が減ったので焼き肉
- ～19:00頃
秋葉原散策 - 19:00頃
迷いながら居酒屋に到着、すぐ酔う - 23:00頃
ホテルに戻って爆睡
土曜日
- 10:00頃
起床
余裕 - 10:30頃
バス待ち集合に到着。
うなさんに30分も早いことを褒められる。
高校の後輩を発見 - 11:00頃
元同校のroxionとfuruwwを発見、荷物を預ける場所を案内してたら１つめのバスが行ってしまった。結局遅刻勢とともにバス乗ることに - 12:00
コンテスト開始！！！
-
12:45
コンテスト開始！！
CODE FESTIVAL 2015 決勝 12:45 ~ 15:45
- 12:47:12
A AC
- 12:52:10
B WA - 12:59:49
B AC
7 + (N-2) * 3とかいうてきとーすぎる式を書いてダメだったので
考察してハマりたくないので即DPに移行
- 13:13:56
C AC
これも貪欲でハマりたくないのでDP
-
13:25:22
D AC
思考停止セグツリーペタペタマン - 13:45:12
E RE
決め打ちしたコード以外に答えがある場合の assert にひっかかった、パターン増やそう - 13:47:51
E AC
増やした
パーカーGETが確定してとりあいず安堵
- 15:32:42, 15:34:50, 15:37:38
G TLE
dp[今みてる頂点][付け加える予定の子][子がこれだったらrerurn]->遷移次の子の候補数
でDP
どう考えてもO(N^4)なんだけど奇跡起こって通らないかなぁとか計算量削れないかなぁずっと思ってたが奇跡は起こらず計算量も削れなかった
ち～ん - 15:45
コンテスト終了！！！
解説聞いて、Gが区間DPと聞いてショック。
木のDP見るとまず、いま見てる頂点は絶対欲しいよなとか思ってしまうのホント良くない
っていうか、これ解けないのは明らかに練習不足のせい
Fは苦手そう、Hは思いつかねぇなぁという感じあとは見てないので知らない。 - ～19:30
Hの個別聞いたり、ICFPCの話きいたり作問の話きいたり飯くったり、話したり - 19:30～
エキシビジョンマッチ！！
めちゃめちゃ面白かった！！よすぽっと 俺はね天才 だめやんけ #csenryu
— きゅうり (@kyuridenamida) 2015, 11月 15 - 22:00頃
りょーくんから飲みイカない？と来た
やったぜ - 23:30頃
７人くらい人集めてぶっちぎり酒場へ
安くてうまかった！
- 25:30頃
帰宅
最高に気分がいい - 26:00頃
川柳を投稿
就寝
日曜日
- 6:40頃
起床 - 7:00頃
何か大変なことをしてしまった気がする
川柳を削除 -
9:10
朝プロスタート！！
CODE FESTIVAL 2015 MIDDLE 09:10 ～ 10:40
-
09:16:20
A AC
-
09:24:48
B AC
-
09:41:08
C AC
あれ、これめっちゃ調子良くない？
順位表見たら5位だし、そういや昨日全完するとか言ったけど
これまじ全完いけるでしょｗｗｗ
-
10:40
コンテスト終了
ち～ん
D難しかったです。 -
～13:30
飯食べてる途中、kagamizが恐るべき事実を俺に伝える。
「さて君の消したtweetスクリーンに流れてない？」
！？
大謝罪川柳祭開催
-
13:30～
チームリレーコンテスト！！！！
開始前にとなりのチームのasiさんに川柳をいじられる
-
14:15
チームリレーコンテスト開始！！
Gを解き バグらせました すいません
-
15:07:14
omeometoさんが、「実験する」と言ってAcceptしてくれた
4位！プロ！
-
16:00～
ハッピーアワー
きゅうりさんにも川柳をいじられながら、コンテンツ受賞者を鑑賞。
普通にこれ授賞式じゃない？
-
18:00頃
解散！！！
CODE FESTIVAL お疲れ様でした！！！！！
最終結果：決勝 : 68 / 198
朝プロ: 7 / 118
リレー: 4 / 20
決勝は毎回解けなくてはいけない一問が解けてなくて辛い…
GとHは帰りの新幹線で書いたがすぐに通ってなおさら悔しい
- G
-
H
Hは解法を思いつくまでがムリだったけど、Gはなぁ～～…
ということで精進して、来年は賞金orツアーをゲットしたい！！！
CODE FESTIVAL 2015 の運営ありがとうございました！
来年も是非参加したいです！
２日でできる！JavaScriptトレーニング！やってみた前編(1~4)
やってみました。上記サイトのgithubのリンクからたどれます。
解法のネタバレありです。
序章:
lint 入らないので諦める
stage1:
cssわかんねぇええと思いながらぐぐりながらやった。
やってるうちに割と分かってくるので楽しい。
12 番の紫色の要素を、属性セレクタと :nth-child(N) セレクタを使わずに1つ取得できる
に苦戦、ul:last-child 使えねぇとなっていたところ属性セレクタ使ったら何故か通る。
正解法は
'.js-training + .js-training > :last-child'
らしい。 + で結合 > でまとめてる？っぽい
stage2:
css の position relative の仕様が謎だった
よくみたらtopを使ってとか書いてあるしヒントたくさんあった。
あとはひたすらcss調べる。
stage3:
特に苦労するところなし。だいたい参考に載ってるリファレンス通り。
最後のprepend()だけはちょっと調べた。
JQuery版書きやすいなぁ
stage4:
4 番の要素を入力された角度に回転できる
がエスパー問題。
入力された角度が反映されるタイミングが 'blur'なのか'input'なのか'change'なのか謎。
はじめ'input'でできて明らかにできてるじゃねーか！！となってどうしようもなかったので答えみました。
正解は'change'でした。
最後の問題はちょっと感動。
HTMLも上から読み込んでいくから、まだ記述されていない場所は読み込めないの window.onload を使ってその中の function に処理を書く。
感想
ここまでしかやってないけどJavascriptわかってきたぞ〜
今まで謎すぎて手を付けたくなったJSを使ってみたくなりました。
割とCSSぐぐりゲー。
ICPC国内予選2015 参加記
FinalZukkyというチームで出ました。
全体８位でした。
いつもの常勝セリフを言いたいところだが、あまりにも空気だったのでやめよう。
- 開始前
- とん八で勝利のカツを食う。
- 12:15 集合
- 練習セッションで全完
- 13:00 ~ 15:00 マッサージチェアで惰眠をむさぼる
- 15:00 勝利のレッドブルとアルフォートを購入
- twitterを鑑賞しながら予選開始を待つ
- 開始 16:30~
- 印刷フェイズ
- とりあいずB担当なのでBを読む、やるだけ例年より簡単そう
- Aが瞬殺されたので、Bをやる。通った。一安心。
- Cをdohatsuさんが実装している間にDの解法について考える。
- dpなんだけど状態多くない？
各コインの枚数を5枚持てばOKという路線でとりあいずZukkyさんが実装スタート。 - いつの間にかCが通っていた。
dohatsuプロの【いつの間にAC（バック・グラウンド・アクセプト)】が発動。 - Eを読んで問題文をdohatsuさんに伝える。
怒髪「ちょっと、考えてみる…」 - F問題を伝えられるもとりあいず保留。
- D問題WA,やっぱ、コイン５枚だけ持つのまずくない？ってことで再考察、よくないケースが存在していた。
- この辺りの考察でかなり時間かかった。3ACのまま残り１時間切っててかなり焦る。
- 実はよくないケースは気のせいっぽくて結局100円玉だけいっぱいもてばよくね？という結論に至った。（この時点で自由に上に両替可能=総和持てばよいというのに気づけばよかった）
- dp[100][5][2][5][2][511] + 遷移はコインを使う枚数を全探索でオーダーがすごいことに、5分くらいぶん回して答えが出たので出したら通った。
- いつの間にかEも通されていた。
怒髪プロの【バックグラウンド・アクセプト】発動２回目。 - 一気に5ACになって、一安心する。
- F問題を考察。辺をノードとして考える最小費用流では？と思いついてみたがサイクルで死ぬ大嘘解法で無駄に時間を浪費してしまい終了。
- 打ち上げ 20:15 ~
- 恒例のBigBoyで打ち上げ。
- Yutaka大先生に感謝して飯を食う。
- 二次会11:00 くらい
- あおやまでラーメンを食うという約束をしていたのに来たのは俺含めたった二人。
- 二玉食って胃に限界を感じる。
- 飯屋→飯屋はやばい
- 睡眠 04:30
先輩方のおかげで国内予選通過しました。お会い出来る方は筑波で会いましょう。
僕はそれまでに正戦力になれるよう頑張りたいです。
JOI春合宿day4 : Spaceships
問題文↓
http://imoz.jp/data/joi/2013-sp-d4-spaceships.pdf
ジャッジ↓
3: 宇宙船 (Spaceships) - 2013年 日本情報オリンピック春合宿 4日目 | AtCoder
問題概要
- N個の頂点とQ個のクエリがきます。
- 頂点を結ぶ辺の関係は森か木であることが保証されています。
- クエリは次の三種類です。
- 頂点a の親を頂点b とする。
- 頂点a とその親を結ぶ辺を削除する
- 頂点a と 頂点b のLCAを出力する。
