HTTF2020参戦記
HTTF2020に参加しました
全然ダメだったけど反省のために書きます。325/834位でした。
最小全域木(シュタイナー木)の構築みたいのをして4901556点でした。最短経路問題ってなんですか？
まともに最小全域木作ろうとすると実装ができなかったので、最初に塗り絵をしてから無駄な部分を消して、消しすぎてゴールできなくなったら方向案内を追加するみたいな解法になった。
時系列
開始直後
まだ家についてなくてスマホで問題を読みつつprint(0)を出した。36位だかだった。
48047点
~2時間
とりあえずJavaで書き始めた。
ゴールマスの隣にマスを置くだけのやつを出そうとするがREを連発する。(x-1)%nを(x-1+n)%nにしたら直った。そういやそうだった。
50403点
~2時間30分
うねうねと触手みたいのを伸ばして回収していく作戦にした。ゴールから連続した誘導路を伸ばしていって触手に触れたロボットは全部吸い込む感じ。
触手を伸ばす方向が謎なこととそもそも全部のロボットをゴールさせることが必須なことにようやく気づいたので方針転換した。
~3時間
ゴールから到達可能なマスに全て置くやつをやっと実装する。ゴールに向かって歩くような向きを求めるのは触手の時に作っておいたので方向案内を敷き詰めるだけだった。
4392988点(解説放送でこれだけで480満点くらいって言ってたような気もするが気のせいか？)
~5時間20分
バグり散らかしたり方針が迷走したりが一旦実装が完了し改善する。ロボットが一度でも通る場所全てに方向案内を置いた。それだけだと連結にならないのでゴールからBFS(操作単位でなくマス単位)して連結にした。
4773586点
~6時間
連続して→→→みたいのを置くのが無駄なので消した。曲がり角を間違って消すとゴールできなくなるのでバグと闘った。
4884346点
~7時間
ほとんどのロボットの上には方向路があるのでそれの削除と方向を変えて他の方向路を削除する山登りを考える。
山登り時の方向路の選択はランダムなので時間目一杯回るようにタイマーを実装、TLEしないか確認のために一旦提出する。連続した方向路できちんと消せてない部分を多少修正したのでスコアが伸びる。(本番中はなぜかスコアが伸びたと思ってた)
4901556点
~8時間(終了時刻)
バグらせて終わる
反省
多くの人が実装していたゴールあるいはロボットからのダイクストラでの構築がやはり筋がよかったと思う。一瞬考えたような気がしたけど計算が間に合わないような気がして止めてしまった。(ロボットからダイクストラするやつは100msくらいだったらしい)
筋がよかったところ悪かったところが種々あるのだけれど大きいのは三つ。
- 開始90分ほどまで気づかなかったやつで、ロボットを全部ゴールさせなければならないという点。計算式を見たら明らかなので最初に気づけるはずだった。
- 最後までダイクストラを試さなかった点。連結にするためにBFS(ダイクストラ)はしてはいたが、１マスしか進まないやつだったのでダメだった。直進と方向転換でやるとよかったらしい。これ実装うまいな。
- 方向案内を消すのは計算のコストが大きいが、ゴールへ向かう方向案内の追加は注目していないロボットへの影響はなく再計算の必要が無いという本質を見逃していた点。焼きなましやビームサーチを考えると方向案内の削除は悪手だと思う。
490万点にぎりぎり乗せるくらいしかできなかったかなしい(´･_･`)
詰まった時に参照するリスト
考察で詰まった時用確認リスト
考察詰まった時ようにまとめる。デバッグのアイデアとかも含む。
実装・デバッグ
- スモールケースで特殊化していないか or する必要がないか
- バグを埋めこみやすいのでうまく使い分ける
- dpで前回の状態をただ下ろせば良いやつを忘れていないか
発想
- 逆順から考えたか
- ゲーム系・構築系
- 自由度別に独立に計算できないか
- 例) マンハッタン距離の最小化でxy独立に最小化を考えられないか
- (二部)グラフに落ちないか
- グラフに落とせることがある。完全(二部)グラフや木になったりも
- オフラインクエリはソートすると計算量が落ちないか
- 状態数を数え上げる時、構築手順を一意にすることができないか？構築手順を考えるとDPが生えるかも
- 実は計算量が小さかったりしないか？ならし計算量が小さい？最後は状態が変わらなかったり？
STLで二分探索
動機
二度と悲劇を繰り返さないために
lower_boundとupper_bound
STLに含まれる両関数、文字通り上界と下界を与える。
例によって左閉半開区間だなと理解したけど、えびちゃんみたいな理解もあるみたい。これもわかる。
えびちゃんの解釈では、lower_bound(x) は x と等価な要素（a <= x かつ x <= a、C++ 的にはたぶん !(x < a) && !(a < x)）の下側の境界で、upper_bound(x) はその上側の境界だと思ってます
— えびちゃん (@rsk0315_h4x) August 15, 2019
equal_range(x) でそのペアが返ってくるので、そんなような気持ちになりました
signed main() { ios::sync_with_stdio(false); ll n = 10; vector<ll> a(n); REP(i, n) a[i] = i; a[2] = 3; REP(i, n) cout << i << " ";cout << endl; # index REP(i, n) cout << a[i] << " ";cout << endl; auto lower = lower_bound(all(a), 3); auto upper = upper_bound(all(a), 3); cout << lower - a.begin() << endl; cout << upper - a.begin() << endl; return 0; } /* output 0 1 2 3 4 5 6 7 8 9 0 1 3 3 4 5 6 7 8 9 2 4 */
g++のデバッグモード
配列外参照はつらい
のでデバッグオプション-D_GLIBCXX_DEBUGでエラーを吐くようにする。
g++ -O2 -std=c++14 -D_GLIBCXX_DEBUG
実行例
$ g++ -O2 -std=c++14 -D_GLIBCXX_DEBUG Main.cpp && ./a.out
3 2
3 5 8
/usr/local/Cellar/gcc/8.2.0/include/c++/8.2.0/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index -1, but
container only holds 3 elements.
Objects involved in the operation:
sequence "this" @ 0x0x7ffee3916830 {
type = std::__debug::vector<long long, std::allocator<long long> >;
}
Abort trap: 6
参照
"One day" or "Someday"
"One day" or "Someday"
ふとどっちがどっちかわからなくなったのでまとめる。
One day
「いつか必ず」というニュアンスがあり意思を持って達成する場合や具体的なイメージがある場合に用いる。 One of these daysも同じ意味。
Someday
「そのうち」というニャアンスがありOne dayと比べると受け身な姿勢がある。
Someday in the rain、なぜかやたらと覚えているタイトル。
参考
「One day」と「Someday」の違いと使い分け | 英語学習サイト：Hapa 英会話
「いつか」を表す英語「One day」と「Someday」のニュアンスの違い | 英語の効率的な勉強法を追求するサイト-English Plus-
