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を出力する。
解法
続きを読むAOJ 2454 : Repairing
問題↓
問題概要
- 線分が与えられます。
- source と sink となる点が与えれます。
- sorce から sink 線分に沿って水を流します。
- 途中に stopper という点がいくつか存在します。
- stopperを〆ることでそこで水の流れを止めることができます。
- 止まる水の流れる最小の距離を求めて下さい。
解法
続きを読むAOJ 1289 : Spherical Mirrors
問題↓
Spherical Mirrors | Aizu Online Judge
三次元の球体と直線の交点、反射のライブラリが出来たので乗っけます。
問題概要
- 三次元空間上にN個の球体があります。
- 原点(0,0,0)からレーザーが方向(u,v,w)に発射されます。
- 球体に当たるとレーザーが反射されるので
最後に反射する場所の座標を出力して下さい。
