TopCoder SRM468 Div 1

参加記録

演習の成果はまだ出始めない……ようだ……orz
コード書くの遅すぎだし、500は通らない……もっと演習を……

結果

ox- 167.05点 314位 1574->1601


反省文書いた。


ほんとに論理的思考の才能がねえなあ。

Easy T9

問題

携帯電話のメールのような入力を考える。各キーにはアルファベットがいくつか対応しているが、
この入力装置は辞書にある言葉しか入力できない。
また、同じキー入力で複数の辞書の言葉が該当する場合がある。その場合その単語がアルファベット順で何番目かを#の個数（*は#５個分）により指定する。
辞書とキー入力が与えられたとき、出力される文字列を返せ。入力は正しいものと仮定して良い。

試行錯誤

上の概要がいつもに増して、あまりにもひどい超訳だが元の問題文がバカみたいに長いので勘弁。
というかこれ問題文わかりにくすぎで英語の試験やってるんだかプログラミングコンテストやってるんだかわかんないよ。ふざけやがって。


キーワードを辞書順にソートしてから文字を数字キーに置きかえる。
入力文字を単語ごとに区切り、数字化した辞書から線形探索して単語を出力するような実装をすればよい。


読解に10分を要したorzその後returnを書き忘れてしばしはまる。何やってんだか。

Medium RoadOrFlightHard

問題

n個の区間を陸路または空路でこえたい。（n≤40万）
それぞれの区間を陸路、空路で超えるためにかかる時間は与えられている。
空路には制限があり、離陸の回数が合計でK回以内でなければならない。（ただし一度の離陸で何区間進んでもよい）
このとき、合計の所要時間の最小値を求めよ。

試行錯誤

ん、nは4万以下？じゃあDijkstraでいいかな！


がりがり。 なんかハマる。なおす。テストケース通った！
Submit.


二重に間違っていて救いようがない。
nは40万以下であるし、n<4万としてもDijkstraではメモリも時間も明らかに足りない。
完全に頭が沸いていたとしか思えない。というか時間・空間計算量のオーダーをよく確かめずにコード書き始めるアホな癖なんとかしろよ！！進歩ねえな！！

Hard

あけてない

Challenge phase

コーディングフェイズ終了数分前にMediumがMLEになることに気づき、自分で自分のコードを撃墜しようと試みたwww
"You cannot Challenge yourself"って言われた。ですよね。


例の用事が終わったんで、今週からまた問題がんばって解きたい。