AtCoder Beginner Contest 164に出ました - プログラミングを上達させたい

久々に出ました。出ました達郎。レーティッドとか含めて、本当にお久しぶり。

結果は8:26で3完(A,B,C)、D問題は全く分からず、E問題が解けそうだったけども時間切れ・・・！
解き方考えて→こんがらがってしっかりノートに手書きしてみて→書きながらも何回も書き直して・・・で時間がかかってしまった。
実装力が足りてないと実感。最近Project Eulerで、しかも短いコードで解けそうな問題ばかり解いているからこうなるんだ。反省。

A問題

(define s (read))
(define w (read))
(display (if (<= s w) "unsafe" "safe"))
(newline)

大好きscheme。

B問題

メインの部分だけコード書きます

    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
 
    while(a > 0 && c > 0){
      c -= b;
      if(c <= 0){
        System.out.println("Yes");
        break;
      }
      a -= d;
      if(a <= 0){
        System.out.println("No");
        break;
      }
    }

C問題

同じくメインのとこだけ。

    int n = sc.nextInt();
    String[] strs = new String[n];
    for(int i = 0; i < n; i++){
      strs[i] = sc.nextStr();
    }
    Arrays.sort(strs);
 
    int ans = 1;
    for(int i = 0; i < n - 1; i++){
      if(!strs[i].equals(strs[i+1])){ans++;}
    } 
    
    System.out.println(ans);

ここまでで8分半。そして、D問題が全く分からず・・・20分くらい考えるも諦める。
離脱しようとする前にE問題を覗いてみると、可能性があるか・・・・？みたいな感じになり、取り組んでみた。

E問題

方針は

まず、各都市に「最短時間、またその場合の最大残銀貨」の配列を作る。最初は都市1のみ0分、他はinf時間で0銀貨。

[今いる都市、経過時間、残銀貨、これまで通った都市の両替所の情報]を保持(キューに入れる)

→今いる都市から行ける全ての都市について、現段階より最短or同タイムでコイン保持数がより多い でいけるか判定し、
　可能ならそこへ行った後の情報をキューに入れる。また、その都市への最短時間を更新する
→キューがなくなるまでそれをやる

そこで大事なのが、残銀貨が鉄道代に足りてない場合。そのときは

これまで通ってきた都市の両替所を振り返って、残銀貨を補うのに最短時間の両替をやっていたことにする

という方針。鉄道代金が <= 50 だということから、まともな時間で求められる。

ただ、色々書いてみると、例えばこういうところでアタフタした。

・一部、intでおさまらない可能性がある変数があり、longにしなきゃいけない
・両替所を振り返るときに、各両替所で得られる銀貨枚数が不足枚数に比べて圧倒的に多い場合の処理をどう書くか
・最短時間の両替にかかった時間だけじゃなく、それで何枚の銀貨を余分に得たかも考えなければいけない

ちゃんとこういう大きな問題を書き切れる力がないとダメだなーと感じるコンテストでした。
上記の解き方が合っているかはさておき、この方針で書こうとしてから20分以上かかっても全然書き切れないまま時間切れだった。悔しい。

解説とともに、解いた方々のコードを見て勉強せねば。どうせ絶対キレイに書いてるんでしょ。知ってるんだからな。

以上です。やっぱ定期的に出ないとダメだわ。頑張るぞい

追記(同日23:08)

E問題の解説・・・分からないので、1回自分の方針で書き切ってみよう。
ちなみにパフォーマンスは978、レーティングは1251にダウン・・・
やっぱり今の実力だとDは解けなきゃダメか。Dをまず解き直してみる。