microbeのブログ

意識を高めるために書いてるだけ

POJ1036 : Gangsters

1036 -- Gangsters

動的計画法の練習

 

問題概要

時間Tiに価値Piのギャングiがレストランにきて,レストランのドアの状態がSiであればレストランに入る.
レストランのドアは1単位時間ごとに状態を1上げるか下げる,もしくはそのままにすることができるので,レストランに入ったギャングの価値を最大化する.

(英語が絶望的に出来ないので正しい翻訳ではなく自己解釈です.悲しいね.)

 

方針

最初に書いちゃってるけど動的計画法

あらかじめ時間でソートしておく.
dp[i] : =i人目を見たときの最大値
Ti,Tjの差<Si,Sjの差の絶対値 の場合は入れることが不可能なので除外.

 

ソース

gistdc32dcf8dba7c8f44e66bb2f89a4f57d

 

英語が読めないというのもあるんだけどPOJの問題なんか苦手だなあ
JOI非公式難易度表を優先的に埋めようと思います.

ABC065参加

数か月ぶりにコンテストに参加したので

abc065.contest.atcoder.jp

結果はA,B,Cの3完.

Dの方針が分かっていただけに全完できずに悔しい.

 

A問題


 A ≥ B, A < B ≤ A + X, B > A + X に場合分けをするだけ

gist4107b21428c385afac5680c4d916f39f

 

B問題


シュミレーションをしていきカウント.ボタン2が光ったらそれまでの回数を出力して,同じボタンが2回以上押された場合はボタン2が光ることはないので-1を出力

gistf3d83ee288dff9511f06b5efdba0fb0d

 

C問題


組合せっぽいなにか
|N - M| > 1のときはどうやっても並び替えることが出来ないので0
|N - M| = 0のときはN! * M! * 2,|N - M| = 1のときはN! * M!

gist9f349f69752880ac0279afa731d1fb9b

 

D問題


最小全域木問題なのは分かったものの最小全域木を書いたことがなく具体的にどう書けばいいのかわからずに敗北.悔しい.

解説をみて後からkruskal法で解いた.

gistbb88ba37a2841a258c7811376c8afcce

 

 

全体としてC問題まで早解きに感じれるようになったのはうれしい.次は全完を目指すぞい.

基本情報技術者試験

 

今年の4月にIPA基本情報技術者試験(FE)を受験し,無事合格証書が届いたので勉強時間とかの記録を書いておきます.

 f:id:microbe8888:20170618141515j:plain

そもそもなぜFEを受けたかというと,単位が欲しかった.それだけ.

 

使用した参考書はこち

 過去問題集はともかく参考書は何を選べばいいのか全然わからなかったので本屋でざっと見て見やすそうなもの選んだ.

午後対策にこちらも一応買ったが一切読まなかった...

 競技プログラミングをやりましょう.そうすれば午後のアルゴリズム対策はいりません.多分.

というのも受験したH27年春期試験の午後アルゴリズムでの出題はなんとO(V^2)ダイクストラだった.なんとも言えない.

 

次に成績

f:id:microbe8888:20170618141524j:plain

何とも言えない非常に微妙な点数である.むしろ悪い点数なのかもしれない.午後のデータベースとかでボロボロだった気がしたので60点台だと思っていたがそれよりはよかった.午前も若干難化していた気がする.

 

最後に勉強時間

勉強時間といっても全く記録をとっていないので大まかにだが

 

基本情報技術者教科書 : 11時間

過去問題集 : 19時間

合計 : 30時間程度

 

勉強時間が少ない気もするが,もともと1年ほどCを触っているので午後に関しては過去問を解くぐらいしか対策をしていない.午前の知識も短時間で詰め込んだわけではなく,空いた時間に参考書を読んで地道に知識を入れていった感じ.しかしもっと勉強してれば合格発表までひやひやすることもなかったのかもしれない.

 

秋に応用情報技術者試験(AP)を受けるつもりなのでそれはもっと頑張りたい.

 

AOJ0189 : Convenient Location

問題 : Convenient Location | Aizu Online Judge

最短経路問題の練習.

問題概要

ある頂点から別の頂点までのコストが与えられるので,どれか頂点を基準にした時のコストの合計の最小値を求める.

解法みたいなの

コストの総和を全点それぞれ求めなきゃいけないのでワーシャルフロイドで解いた.頂点数は与えられないので,入力a,bから頂点数を求めておく.

 

かなり冗長なコードになってしまった気がする…

gist2ff2c95c4eb2c9c3bc09d66f9ac3ae1b

AOJ0012 : A Point in a Triangle

幾何問題に強くならなければと思い,最近幾何問題を解き始めました.

ベクトルとか使ったのでメモ.

三角形の中の点 | Aizu Online Judge

概要は三角形の各頂点の座標と,ある点P(x, y)が与えられるので,その点Pがその三角形の内外どちらにあるかを判定するという問題.

 

方針

点Pが三角形の中にある場合,外積によるベクトルは3つすべて同じ向きを持つはずなのでそれを判定する.

 

ソース

gist9405f9fbeba3242c2182d3f48317583e

 

もっと問題解いて競プロ強くならなきゃなあ

A,B問題埋め終了

ABCのA,B問題埋めが終了しましたーーーーー!!!!(ドンドンドンパフパフ)

何の話だってことなんですけどね.この通りです.f:id:microbe8888:20170219005525p:plain

最近AtCoder様のAtCoder Beginner Contest,通称ABCの問題を埋めていってます.最初に簡単なA,B問題を埋めていこうかなと思い,それがようやく終わりました.学校の試験期間とかと重なってあんまり時間割けなかったから20日くらいかかってしまった...

A,B問題は典型アルゴリズムはあまり絡んでこないのでかなり簡単なので1問10分もかからず解けはするのですが,それ以上時間がかかってしまった問題が数問あったので悔しい限りです.この手の問題には時間を食われないようにもっと鍛えなきゃダメですね....

A,B問題埋めが終了したということで次はC,D問題を埋めていきます.D問題はかなり難しい印象があるのでとりあえずC問題だけ全部埋めようかな?とか考えてたり.

進捗が出たらまた書きます.

幅優先探索のお話

今回からはアルゴリズムの勉強をちょくちょく挟んでいきます.

 

概要

今回やったのは幅優先探索.

幅優先探索は全探索アルゴリズムの一種で, 深さ優先探索は簡単に理解できたんだけど幅優先探索がなかなかうまく実装できなかったので今回頑張ってやってみた.

解いたのはこの問題.

Mysterious Worm | Aizu Online Judge

赤青緑の3色のうち, 隣り合った2つの色が異なるとき, その2色以外に変化する. すべての色が1色になるまでの最短回数を求める問題. 典型的な幅優先探索の問題らしい. 

 

解法

アルゴリズムは前述のとおり幅優先探索なんだけど大まかにまとめると

1. 初期の状態をキューに入れる.

2. キューから取り出し, 隣り合う異なる色をそれら以外の色に変える.

3. 変えた状態を新たにキューに入れる.

4. 全てが同じ色, またはキューが空になるまで2~3の繰り返し.

ただ,どうやっても1色にならない場合, メモリリミットエラーだったり, いつまでも繰り返しちゃうから, 重複するようならばループを終わらせなきゃいけない.

 

ソースコード

Algorithm

 

結果

f:id:microbe8888:20170110222502p:plain

 

 

いろいろ調べながらではあったけどちゃんと解けたので良し. 深さ優先探索幅優先探索は簡単に実装できるくらいを目標に.

 

こんな感じでアルゴリズムを勉強していきます.