読者です 読者をやめる 読者になる 読者になる

dohatsutsu’s diary

日記を書いています。

【No.017】「AOJ-ICPC 500 それぞれの感想 前編」

f:id:dohatsutsu:20160426200644p:plain

 

今回は、AOJ-ICPC 500 にある問題(42問)について、感想をひとつずつ書いていこうと思っています。

 

○カードゲーム

Cards | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

 

学部2年の5月、蟻本のp197にある二部マッチングのコードの使い方を練習するために解いた記憶があります。

68行目に  V=m;  とあるけれど、これはどうなんだろう・・・・。

このエッジの張り方だと、別に問題はない。(そもそも実際にACしている)

だけど、ノードの数を表す変数としてVを用意しているのなら V=n+m が正しいと思う。

(このときはまだ中身をよく理解していなかったからしかたない)

 

 

○Mr. リトー郵便局

Mr. Rito Post Office | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

学部2年の6月に解いた問題。

なぜかすごく印象に残っていて、今でも概要と解法を覚えているくらい。

それだけ解けたときに嬉しかったんだと思う。

 

 

○鉄道乗り継ぎ

Railway Connection | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

学部3年の6月末(チームFinalZukkyとして国内予選に参加する数日前)に解いたっぽい。

この問題を解いたことによって得られた経験がその国内予選での結果につながったかどうかはかなり怪しい。

 

 

○全宇宙生命ゲノムデータベース

The Genome Database of All Space Life | Aizu Online Judge

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1181781#1

学部2年の1月に解いた問題。

再帰関数で素直に最初の文字から1文字ずつ求めていって、i 文字目が分かったら即、再帰関数を終了するようにしました。もっと賢いやり方があるかもしれないけど、この方法はあまり面倒ではないのでこの方法で求めました。

 

 

○天の川

Milky Way | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

学部3年の7月に解いた問題。

線分どうしの距離を求める方法を自力で思いつける人はどのくらいいるのだろうか・・・。(僕は本で知りました。)

 

 

○Never Wait for Weights

Never Wait for Weights | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

部活の練習中にUnionFindを使うというネタバレを受けてしまったため、

完全に自力で挑戦して解いた問題ではないです。

結構バグを取るのに時間がかかった思い出があります。

 

 

○僕の友達は小さい

My friends are small | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

 

学部3年の7月に解いた問題で、結構面白かった。

最初は全く解法が思いつかず、翌日になってもう一度考察してみたらあっさりと解けた思い出があります。

問題文に「なお1,000,000,007 は素数である。」と書いてあるのを初めて見ました。

 

 ○Test Case Tweaking

Test Case Tweaking | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

個人的に解法を考えるのに時間がかかってとても悔しかった問題です・・・。

 

○Beautiful Currency

Beautiful Currency | Aizu Online Judge

AIZU ONLINE JUDGE: Code Review

個人的に計算量がよく分かっていないです。

n/1+n/2+n/3+...+(n-1)/n+n/n  って意外と小さいっぽい?