第二回日本最強プログラマー学生選手権の感想
第二回日本最強プログラマー学生選手権に参加しました!結果はA,B問題の2完で見事レートを下げました!勉強代と思えば-25なんて安いものです(泣)以下簡単にコメントしていきます。
A - Competition
初見:A問題だしちゃちゃっと片付けちゃおう
与えられるお肉の価格設定より少しだけ安い値段設定をしろという問題。与えられるお肉の価格設定を元に自分が価格設定するパックの価格を計算して、
- その値が小数だったら切り捨て
- 整数だったら「その値 - 1」
を出力しました。小数怖いなぁと思いつつ工夫せずに通ってくれました。A問題にしては若干考えることが多い問題でしたが、8分は少し手間取りすぎましたね。
B - Xor of Sequences
初見:Xor!?うっ、頭が・・・!
2つの数列が与えられるので、どちらか一方のみに含まれる数字(対称差集合というらしい)を出力する問題。集合の計算はpythonのsetを使えば簡単にできることを知っていたので秒殺できました。
C - Max GCD 2
初見:最大公約数の問題はここ↓でたくさんやったし今回も3完は堅いな!()
AtCoder 版!マスター・オブ・整数 (最大公約数編) - Qiita
A以上B以下の数字から選んだ2つの数字の最大公約数のうち最大なものを求める問題。まず初めに考えたのは考えたのはBから1に向かって答えを決め打ちして、その数で割り切れる数が2つ以上いればその値を出力するというもの。しかし、ここの実装でA以上B以下のすべての数に対して割り切れるかのチェックをしてTLE。ここで、答えを決め打つ方針は間違ってると思い、愚直に問題文通りに素直に実装してみた。つまり、2数の組み合わせを全パターン調べて最大公約数を更新していく方法。でもこれってO(N^2)なので今回の制約では間に合うはずがないですね;;
結局決め打ちの方法で工夫する発想には至らず、用事のため1時間強で撤退しました。一回切り捨てた解法に戻れなかったのは頭が固すぎましたね。きちんと計算量に則った解法の選択を心掛けます!
D - Nowhere P
初見:C解けないけどわんちゃんある?
問題文もあまり読み込めていませんでした。入力が10^9と大きいこと、同じ倍数、約数系の問題ならCを先に解くべきだと思いC問題に戻りました。
全体の感想
順位表を見る限り、ABCまでは大半が解かれていたので、せめてここまではおさえておきたかったな~というのが正直な気持ちです。解けない問題は格好の成長材料なのでありがたく復習させていただきます!