ICPC2020国内予選参加記
直前
前日に睡眠失敗したので眠て~って言いながらストレッチしてました.(いい加減緊張で死にがちなのをどうにかしたい)
コンテスト開始
更新かけるとトップページが落ちてたので本番は違うページだっけ?とかめちゃくちゃ焦ってメールのコピー読み返してました.
模擬国内で3完できてたので同じ担当にして僕はA担当しました.通したの2番目だったので僕の仕事はここで終わりです.
BもCもチームメイトができそうだったので実装を任せて次へ,Dは構文解析で無理~~ってなったのでEを読みました.
Eを見てコードを書いた後に誤読に気づいたので一旦Fを開きました.(誤読がなかったらEの制約ちゃんと見て通せたかも)
このあたりでCの愚直が終わって3完上位っぽかったので盛り上がってました.
Fを読んで愚直はすぐ書けることに気づいて書いたけど結局これはコンテスト中にテストケース終わりませんでした.
その後Fの高速化メインで検討しましたが3完でコンテスト終了です.
感想
TLがないからといって計算量見積もらずに愚直をするのをやめよう!!
横浜通っててくれ~~
三井住友信託銀行プログラミングコンテスト2019
久々にコンテスト中に500解けた・・
M1とM2が同じなら0そうでないなら1
DPCで見たやつ
(int)(i*1.08)==nのiを探す
買える個数>買う個数なので自由に選べる
買う個数はx/100個でないといけないので
x%100がx/100*5(全てパソコンの場合)に収まれば可能
めっちゃDPっぽくない?という気がしました
パターン数が少ないので各数字の最初と最後の出現箇所を覚えて
真ん中を固定した時に構成可能なものをsetに突っ込む
iの帽子の色の候補はそこより前でA[i]-1個と主張している人数に一致するので
前からかけていく
過去問埋め3
DPのお気持ち.
遷移はそれほど難しくないので,綺麗に書けるようにしておきたい.
重複を除いた部分列の辞書順K番目
一見簡単そうに見えるけどN^2個の部分列をソートしてるので愚直だとTLE(気づかなかった)
辞書順K番目→文字の長さ≦Kであることから調べる部分列を減らしてAC
UnionFindの練習,初めて使ったけどグラフの統合の仕方が天才すぎる.
与えられるm個の組の通りにuniteして,順列のindexとvalueのrootが同じものの数が答え
4桁でxx時yy分が与えられる問題.
12時60分==13時00分のような変換を組む必要がある.n進法に近いものを感じるし一発で通せるようにしたい.
D - Shortest Path on a Line(第二回全国統一プログラミング王決定戦予選)
Dijkstraをやりましょう.
一生バグらせたので反省.
ICPC2019国内予選
2完でしたなんで・・・。
リハーサル
wi-fiの設定がうまくいかなかったので講義に遅刻する。(講義に出てる間に先輩がよしなにしてくれてた。)
プリンターの設定をするために講義を早抜けする(休講にしてくれ)
本番
A,Bがやるだけに見えたので任せて誰も問題読んでなかったDを読む
https://atcoder.jp/contests/abc116/tasks/abc116_cは思い出したけどDPが生えてこないのでCを読む
なんかおき方3^mで全部試せばよくないかになったけど実装で詰まる(なんかやたら複雑に実装しようとしてた)
実装力が足りないのお気持ちになったので来年は横浜行きたい
ABC123
久々の更新
Dやること分かってたのに通せないのはよくなかった
Aにしては変数が多いがよく見ると一番遠いのはAとEなのでそこだけ注目すればいい。
Yay!と:(嫌い
最後の注文だけ次の注文が可能になるまでの待機時間が発生しないので最後にどれを頼むかだけ気にしたい。
注文が10の倍数の時刻にのみ行えるので10で割る余りが0以外で最も小さくなるものを最後にしてあげる。
こういうのは遅い人に合わせるってどっかで聞きました。
一番輸送人数が少ない乗り物でN人運ぶのにかかる時間+4分となります。
xyz<=1e9なのでここを工夫するんだろうなぁという気持ち。
やり方は色々あるみたいなのでpdfから好きなのを選ぶと良さそう。