microbeのブログ

進捗ダメです

全列挙 : POJ2718,POJ3187,POJ3050,AOJ0525

蟻本に掲載されている問題

2718 -- Smallest Difference
3187 -- Backward Digit Sums
3050 -- Hopscotch
おせんべい | Aizu Online Judge

POJ2718

数を組み合わせて2つの整数をつくり,その差の絶対値の最小値を求める
std::next_permutationを使うと幸せになれる

gista2d834daff05f9c5c2e8181542d9b59c

 

POJ3187

パスカルの三角形的なもので最終的な和がsumになるような1~Nの並びを求める.
std::next_permutationなら辞書順に生成されるので幸せになれる

gist43f11673ba894460accdc05e188ceee3

 

POJ3050

BFS

gista17b044b1a0e70d86410c6f68290a3bb

 

AOJ0525

行と列を全列挙してると時間が足りないのでひっくり返す行さえ決まればあとは1がr/2より多いものをひっくり返せばいい.行だけの全列挙なら多くてもパターンは2^{10}程度で済む.

gist77ba324305ea5711bc61df08410e3d27

 

やっぱり実装力がないので悲しい

幅優先探索 : AOJ0558,POJ3009,POJ3669,AOJ0121

 蟻本に掲載されてる問題

チーズ | Aizu Online Judge
3009 -- Curling 2.0
3669 -- Meteor Shower

7 パズル | Aizu Online Judge

 

AOJ0558

今の地点から次の地点までをそれぞれBFS

gista68c9a4a9079e3fcb551c5396b4abff7

 

POJ3009

蟻本にはBFSって載ってるけどDFSのほうが楽そう

gist95359f3f435df4cdb2e4a5654bd9b316

 

POJ3669

現時点から行けるところへBFS

gistfbee62bee1c46c63732904490a7aded7

 

AOJ0121

01234567からいける最小回数をあらかじめ計算しておく

gist8cf6341ef52f40278177fcd94d059322

 

 

実装力皆無なのでかなしい
書き方に統一性がないけど昔のコードもあるので許して

 

深さ優先探索 : POJ1979,AOJ0118,AOJ0033

蟻本に掲載されてる問題

1979 -- Red and Black
財産分配 | Aizu Online Judge
玉 | Aizu Online Judge

 

POJ1979

w * hの赤いブロック('#')と黒いブロック('.'),始めの位置('@')の情報が与えられるので初め位置から赤いブロックを通らずに行くことが可能なブロックの数を求める
すでに行った場所を記録しながら探索

gist1b26b641b414b5d7ad4e3b7b75dee0a0

 

AOJ0118

すべての場所から探索を初めて探索した箇所が1箇所以上であればカウント
すでに行った場所は記録

gist7e91cefa0949a8d7a5d389759bdec287

 

AOJ0033

脳死

giste57fcf9d68c75f757fd3841c7dd1b67a

 

POJはいい加減C++11以上を使えるようにしてくれ

Typical DP Contest : C - トーナメント

C: トーナメント - Typical DP Contest | AtCoder

 

問題概要

2^{k} 人でトーナメントが行われるのでそれぞれが優勝する確率を求める.
ただし,PとQが対戦してPが勝つ確率は1/(1+10^{(RQ-RP)/400})とする.

 

方針

確率DP
dp[i][j] := i回戦目でjが勝つ確率
PとQが対戦するかどうかの判定が難しかった...

 

ソース

gist19a47ee2cc462ea31dac94d13fe0f2cb

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)を受けるつもりなのでそれはもっと頑張りたい.