JOI予選 - タクシー
ビンゴを飛ばしています (2回目)
明日テストらしいので今日は競プロしません
今日解いた問題です
問題は読んでください
方針としては、それぞれの街からいける街を幅をしながら新たな有向グラフとして構築、その上でダイクストラをするといった感じ
ぱっと見やるだけだったので何も考えずに書いたらWAが出た(このとき関数名がbfsなのにdfsを書いています)
WAが出た理由がよくわからなかったので、もう少し慎重にコーディングすることにして、グラフの構築・ダイクストラを分けてやったらそれでもWAが出た(このとき関数名がbfsなのにdfsを書いています)
眠かったので寝たらbfsになる夢を見て自分がdfsを書いていることに気がついたので帰宅後書いたらMLEになった(このとき枝を刈らずに再帰しているため重複しまくり芸人しています)
さすがに気がついたので今度は無駄な再帰せずにくえうえでやったら通った(完)
解法はすぐに思いついくけど意味不明なバグを生成してしまうみたいなことが最近多いので筋肉つけたいと思いました。
はい
JOI予選 - 魚の生息範囲
母上「そういえばさ、あれに変えたいんだけど。なんだっけ、バカチョンだっけ」
母上「そうそうそれ」(そうそれではない)
帰省してました
確か土曜に解いた問題です
ここだけの話、ビンゴがACできなくて飛ばした
魚の生息範囲 | Aizu Online Judge (AOJ 0580)
(問題は読んで)
最初、下手なdfsなどで被った範囲を全探索してK以上になったら値を加算するなどしようとしたのですが、それだと同じ範囲を何度も数えてしまうことになるので死んでしまった(一般に、人はこういったことをすると死んでしまいます)。
与えられる座標だけを使えばいいことはわかっていたので、X, Y, Z座標それぞれをマージしてソートしておいて細かい範囲に区分、全探索して (ここまでO(n ^ 3) )、その区間がK個以上の範囲に含まれているかをO(n)で判定するといいことに気がついたのでやった
一応想定解を見たらその通りみたいなことが書かれていて、はい。(その通りとは書かれていない)
こういうのも座標圧縮っていうんですね
はい
JOI本選 - JOI紋章 電飾 IOI饅頭 ケーキの切り分け2
11/23 に解いた問題
難易度6の本選問はこれで全て通しました。
各位がテストに拘束されている間に競プロして精進する一般的なテクを使って競プロをしていたら今年初めて90点を割りました。悲しいなあ。
眠たいので簡単に書きます
JOI 2013 本選1問目
JOI 紋章 | Aizu Online Judge (AOJ0598)
最初の紋章の数を数えておいて、あとは全探索しながら差分の最大をもっておくだけ
この問題を本番で見たら絶望すると思います。激やらなくてもいい問題。
JOI紋章なんて問題を考えた人は一度反省すべきだと思います。
やらなくていい度 : ★★★★★
JOI 2014 本選1問目
いい問題すぎて涙が溢れました。
{1, 0, 1, 0, 1, 0 ...} みたいなマスクをもっておいて排他的論理和をもつといい感じになります。
あとはしゃくとりするだけ
JOI 2014 本選2問目
見た瞬間DPを始める問題
脳死して実装したのでバグまくりだった(バグ！w バグすぎてbugになった！w)
よくやる脳死DPだったので、はい(説明をしろ)
JOI 2015 本選2問目
ケーキの切り分け "2" ってあるから "1" はどこにあるんやと思って探したらありました、難易度表最下部難易度12+
1の方は一生解けなさそう
こっちも脳死DPをしてしまった
最初にとるピースを全探索してえいっ！wみたいな解法でやりました
スポーツ実技などという謎科目で疲れたので今日は問題を解いていませんが寝ます
明日から難易度7に取り掛かりたいと思います
JOI紋章のうまい実装とかあればぜひ教えてください
JOI本選 - つらら 古本屋 夜店
11-22 に解いた問題
古本屋は自分にとってちょうどいい難易度で良問でした。
本選の難易度6はあと4問になりましたのでね、
JOI 2010 本選3問目
つらら | Aizu Online Judge (AOJ0551)
問題
N本のつららがあり、i 本目のつららが i - 1本目のつららと i + 1本目のつららより長い時に i 本目のつららは1時間のに1cm伸びる。L cmに達したつららは折れ、0cmのつららとみなされる。全てのつららが折れるのは何時間後か。
最初のつららの長さ a_i cm (1 <= i <= N)
解法
もっとも長いつらら i が折れるのは L - a_i、2番目に長いつらら j が折れるのはもっとも長いつららが隣にあった場合は L - a_i + L - a_j、そうでなければ L - a_j となるので、もっとも長いつららから折れる時間を計算していけば解が求まる。
大きい値を順に取り出すのでpriority_queueを使う
コード
AIZU ONLINE JUDGE: Code Review
JOI 2011 本選2問目
古本屋 | Aizu Online Judge (AOJ0561)
問題
本をN冊持っており、そのうちK冊を売りたい。JOI古本屋では本を10種類のジャンルに分けており、同じジャンルの本をT冊まとめて売ると、そのジャンルの本1冊あたりT - 1円安くなる。
本のジャンルともとの買い取り価格が与えられた時、最大の売値はいくらか。
解法
考察として、同じジャンルの本が4冊あり、それぞれの買い取り価格が 100, 200, 400, 500だった時にそこから3冊売るのであれば、どの組み合わせでも(3 - 1) * 3で6円高くなる。
売る冊数が同じであれば増える金額は同じなので、(100, 200, 400)を売るよりも、 (500, 400, 200)の本を売った方が買い取り価格は当然高くなる。
ジャンル i の本の j 冊目を v[ i ][ j ]として、それぞれのジャンルでソート、j冊目までの買い取り価格のテーブルを作っておいてからあとは単純なDP
コード
AIZU ONLINE JUDGE: Code Review
JOI 2012 本選3問目
夜店 | Aizu Online Judge (AOJ0573)
問題
祭りに夜店が N 個あり、それぞれ楽しさが a_i で遊ぶのにかかる時間は b_i である。祭りは時刻 T に終わるのでその時間を過ぎて夜店で遊ぶことはできない。また、時刻 S には一番大きな花火が打ち上がるのでその時刻に夜店であそんでいてはいけない。夜店で遊んだ合計の楽しさの最大を求めよ。
解法
夜店の数 N 、終了時刻 T ともに3000以下と小さいのでテーブルを更新していくだけで求まる。O(NT)。
コード
AIZU ONLINE JUDGE: Code Review
JOI本選 - ピザ
JOI 2009 本選2問目
ピザ | Aizu Online Judge (AOJ-0539)
問題概要
長さ d の円周上に n個 の店舗と m個 の宅配先があり、配達先にはそれぞれもっとも近い店舗から配達する。そのときの合計の移動距離は何か。
・1 < d <= 10 ^9
・1 < n <= 10 ^5
・1 < m <= 10 ^4
解法
円周上のままだと考えにくいので最初の店舗が両端にあるような線分上で考える。
配達先の両隣であるような店舗を二分探索で求め、配達先から近いほうの距離を加算していく。(店舗の与えられる順番はランダムなのであらかじめソートしておく)
提出したコード
AIZU ONLINE JUDGE: Code Review
感想
微妙に遅いコードを書いてしまった(0.04sec)
問題自体はやるだけだったので数分でAC
非公式難易度表の難易度5からはブログに書いていこうと思っていたのにすでに難易度5と6の予選問題を埋めていて悲しかったです
