当時(2014/12/7)に書いたまま下書きに残っていたので、今更&未完成気味ですが一応公開しておきます。
---------------------------
2014/12/7のCODE THANKS FESTIVAL 2014 A日程に参加してきました。
問題の感想
A カメツル算
4 * a + 2 * b。 やるだけ。
B バッジ
機械A, B, Cを生産能力の高い順に並べ替えて順番に使うだけ…なんですが、割と「並べ替える」ところではまる人がいた印象があります。
自前で条件分岐を使いまくって並べ替えを行うと時間がかかりまくってバグの原因にもなるので、必ず標準ライブラリのソートを使いましょう。
(C++なら<algorithm>をインクルードして
int a[3];
/*a に値を入れる */
std::sort(a, a+3); /* a[0]から小さい順になる */
std::reverse(a, a+3); /* a[0]から大きい順になる */
でできます。
)
C コンテスト
やるだけ。1-indexedであることに注意しましょう。
D 定期券
やるだけですが普通にやると条件分岐が面倒です。解説でもあったように共通部分を引くと良いでしょう。
E 儀式
i番目だけをやり忘れた時の結果を計算することを考えます。いちいち(n-1)回シミュレーションをやると時間がかかるので、操作が可換(どの順でやっても結果が同じ)であることを利用して、最終結果にi番目の操作の逆の操作を行いましょう。
F 順位表
参加者を頂点としたグラフに「順位の低い方から高い方へ向く辺を設ける」ということをすべての大小関係に対して行います。そのようにしてできた有向グラフにおいて、1から辺をたどって到達できる頂点数を数えればよいです。詳しくは解説を参照。
G 通勤電車と気分
部分点解法(n <= 10)は各乗客に対して2パターンをどちらも試せばできます(O(2^n)-時間)。この部分点解法を狙うときは、例えばn>=15のときにexit(1);などを行うと良いでしょう。
満点解法を書くには空き座席のパターンをつかむ必要があります。席に誰かが座っている状態を1、そうでない状態を0をするときに、余中の状態は
111...11101010101...0100000
というようになることを利用します。
H 模様替え
感想
本選2日目に予定が入ってしまい参加できなくて残念だったのですが、今回この様な機会をいただくことができてありがたく思っています。
B日程には(すでに予定が入っているので)参加しません。
