問A ◯ 10:43

問B ◯ 26:51

問C ◯ 42:15

問D ☓

128th / 597

R372 -> R570

問A Expired?

賞味期限からB-A日後に食べたことになるので

B-Aが0以下なら賞味期限前に

正なら賞味期限後になり

B-AがXを超えるとdengerousになる

ということをノートに書かないとわからないレベルで理解が難しかった

A問題としては難しめ

5分遅れで参加したこともあり

10:43に提出

 

問B Trained?

各ボタンを押したかどうかのフラグを用意する

無限ループを回し

押したことのあるボタンにたどり着いた場合無限ループするため

そこでbreakするというのを基本方針として

ボタン2に触れてもbreakするという条件を追加し

ボタン2に触れて終了した場合は回数を表示し

無限ループに到達して終了した場合は-1を出す

ボタンのインデックスと配列のインデックスが1ずれるというミスと

ボタン2に触れた場合終了するという条件を追加し忘れて時間を食ってしまい時間がかかるが提出

26:51に提出

 

問C Reconciled?

犬と猿がほぼ同数でないと隣り合わない順列を作れないということに気づくのが味噌か

厳密には前後1匹以内でないと隣り合わない順列を作れない

同数の場合は片方の順列の数がn!あり

n-1個の間にM!の順列を並べ、最後の1匹を左右どちらかに入れるので

2*N!*M!が答え

1匹違いの場合は同数の場合の最後1匹の場合がないので

N!*M!でよい

 

10^9+7で割る場合の演算方法を調べながら実装を行ったが

足し算と掛け算はその都度割ればいいっぽい

 

問D  Built?

全ての街の組についてのコストを計算して

最小全域木を作ればいいっぽいが

題意を全ての街の組について最小の移動コストを求める問題と勘違いし

ワーシャルフロイド法を使ってしまった・・・

 

実装が遅いこともあり題意の勘違いに気づいたときには

残り10分程度でダメ元で作ってはいたが

もう10分は必要という感じだった

 

 

この手の基本的なアルゴリズムは一度再実装したほうが良さそうだ

学部、大学院で勉強したので概要は知っているが

実装となると話は別で

ワーシャルフロイド法もググって入出力を問題に合わせる感じという

無残な感じのものなので

何度も挫折した蟻本にもう一度挑戦しようかな・・・

今なら理解できる気もするし

 

とりあえず茶色コーダーになったが

ARCの結果を見る感じだとR1200を超えてもD問題を解けていない人もいたので

ABCのD問題を確実に仕留められるようになるのがしばらくの目標か

 

　

人気ブログランキング

にほんブログ村へ