Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 146

ABCDFの5完、2WA。

EはTLEが解決できなかったです・・・。

各問題

A - Can't Wait for Holiday

if-elseをを7つ並べましょう。

B - ROT N

'A'から'Z'までの文字コードが連続していることを利用して、演算していきます。 Nを足して'Z'を超えてしまったときは剰余を取って範囲内に収める必要があります。(別に無条件に剰余をとってもよいです。26未満の数に26で剰余をとっても変化しないため)

自分の提出 https://atcoder.jp/contests/abc146/submissions/8606821

C - Buy an Integer

どうやら与えられた数式は単調増加のような気がする(証明はできませんでした・・・)ので、求めたいNは典型的な二分法で求めることができます。

ただし、「買うことのできる整数が1つもない場合は0を出力」という条件と、 「1以上109以下の整数が売られていて」という条件には注意します。

私は後者を見落としていて、最初Dより難しいのではと感じていました・・・。

あと、デバッグコードを消すのを忘れて1WAを出すという大失敗をしてしまいました。

D - Coloring Edges on Tree

入次数1の頂点から始めて(多分どこからはじめてもいけそうな気もします)、DFSなりなんなりで、ぶら下がっている辺に、1から順かつ上位の辺に割り当てられた数はスキップして、番号を振っていけばよいです。

入力で与えられた順番に出力する必要があるので、入力の頂点のペアを配列で順番に保持し、辺に振った番号は頂点のペアをキーとした連想配列に保存するなど工夫する必要があります。

私はその工夫に失敗して1WA出してしまいました。

E - Rem of Sum is Num

累積剰余を取って、単純にループを回しましたがTLEでした・・・。

もうひと工夫必要だったようです。

F - Sugoroku

うしろから貪欲に取っていくだけです。貪欲に取らなかった場合、手数が増えてしまうか、最初の一手のステップが増えてしまう(辞書順最小の条件に反する)ので。

まとめ

Fのおかげで?なんとか青パフォ一歩手前までいけて、Highestも大幅更新できました。 ただ、デバッグコードつきで提出してしまうという失敗はちょっといただけませんね。cerrを使ったデバッグ関数をちゃんと用意すべきでしょうか。

初めて水色になったときは、一回で緑に落ちてしまい変色記事が書けなかったのですが、今回安定して伸びてきているので、今のうちに書いちゃおうかと思っています。

f:id:mdstoy:20191124231454p:plain