雑記

魔法少女になりたい

ICPC2020 模擬国内予選 参加記

ラクティス

システムが初めてだったのでプラクティスをした ./l ではなく l < in > out としたらlsのエイリアスに反応してoutにファイル一覧が出ていて1WAした 国内予選ではほぼおそらくlはないけど罠を踏めてよかった 他にwでも死ぬらしいが、wまでは出ないのでセーフ

コンテスト前

家を出る前に持ち物チェックをしたのに充電器とハンドクリームを忘れた バッテリーは駄目になってて3時間持つか怪しかったので他チームの人に貸してもらった(本当にありがとうございます)チェックリストを作りましょう

コンテスト中

Aを見る こういうのは0に注意するんですよね~とか言っていたんですが、1<=a_i,b_i だったので残念(?) 書いて出す 6分弱 6位とか

Bが書かれ始めていたのでCを見る 今年も続投廻小宮ファミリー 生で見たのが初めてだったので笑ってしまった そうこうしてるうちにBが通って順位表を見たらFAだった(すげえ)

続けてCを読む n<=20とかであってくれとおもったけど10^5でした 普通にわからん… 思考が止まって眺めているだけに一瞬なっていて、これはまずいとしっかりと考える マス視点で何らかを埋めるんだろうなという気持ちにはなるが、わからん とりあえずわからんのでstartを(0,0)に、goalを(+,+)に補正する入力コードだけ書く マス視点だったら今までに消した範囲の数しかありえないよな→今いるところで全て消えているという仮定を置くと何を消したかの情報を持たなくていいじゃん 横に動いた場合と縦に動いた場合についてどこを消すべきかを配列に入れればいいね! 書き始める(考察15分くらい? 実装に15分くらい)

書き上がる 試す 境界外参照でエラー デバッグをするんですが、スタックトレースがないしブレークポイントがうまく打てないしで焦りまくって、結局printfデバッグする チームメイトにあと5分くらいで書けると伝えてから10分くらい経っていたので現状を聞かれ、せぐふぉってると伝える そうこうしていると原因を見つけた 配列のサイズをh+1,w+1にしていなかったとこがあった(10分くらいかかった)

直したので試す 最後の一ケースだけ合わん…… ここでブレークポイントが打てなかった原因が試しに追加した -O2 オプションのせいだったと判明 環境を直前にいじらない! さすがにハマりすぎているのでトイレに行って頭を冷やしてこいと言われるが、もうちょっとデバッグをする とりあえずいろいろな情報をダンプして見てみて、何がおかしいのかは判明 でもどうしてそういうことになっているかは分からない トイレ勧告2回目 流石に行く

帰ってきて少し見てみると分かる 原因は y+r, x+rを x+r, x+rにしていたことだった 後から思えば最初にダンプした情報でも値がおかしかったし、明らかに疑う場所は一つだった 頭が全く動いていなかった 本当に反省ポイント 動かすとサンプルは合う 出す 通る 70分弱 カス

この時点でEはとっくの昔に通っていたので一旦状況確認 可能性のあるDとFをどう解くかを話していた 聞こえてくる感じだとFはサイコロっぽい 読んでみると、ちょっとめんどくさいだけで解けそうじゃんと思ったが、入力がヤバすぎることが判明 Dを読む限り考察偏重っぽくてレート高いほうに任せたほうが良さそう&立体の回転/展開とかの空間把握と実装は少し自信があったのでFをやることに

とりあえずサイコロライブラリは写経してあったが、当然向きには対応していなかったので参考にはするが基本的には投げ捨てる方針でいく 写経担当の手が空いていたので分業して書くことにした 設計をとりあえず決める † みたいな展開図(標準展開図とか呼ぶ)で↑のときに0、→で1…みたいにする 回転自体は縦回転と横回転が一種ずつあれば全ての回転を網羅できることは分かったので、とりあえずDie構造体だけ書いて共有し、縦回転と横回転を書いてもらうことに

僕はとりあえず入力を書くことにした 方針自体は一瞬で立って、どこかからDFSをして頑張ればいい 持つべき情報は(与えられる展開図の(y,x), 標準展開図においてどこか, 標準展開図においてどっち向きか)

DFSをするために上下左右においてどう隣接してるかのリスト、今自分が上で、隣にあった場合の上の方向のリストが欲しいと分かる ここがこわれてるとデバッグが大変なことになる&最悪サンプルは合ってしまう可能性が大いにあるので、かなり丁寧にダブルチェックしつつリスト24個を埋める 結果的にここを丁寧にやったのはとても良かった ここらへんでDが通った

そうこうしている内に縦回転と横回転が終わったので、遅くてごめんと言いながらsolveの中身も書いてもらうことに 探索の内側については具体例と照らし合わせながら埋めた 扱うべき向きが三個くらい出てきて頭が壊れそうだったけどなんとかなった なんとかしたらsolveも書き終わったらしい とりあえず全部↑になるようなケースを手打ちで作って試す assertで死んだ 冷や汗が出たが、原因はすぐに突き止められて直したら合うので合体させた サンプルを試したら合体ミスでむちゃくちゃな値が出てきたけど、ちゃんと合体したらそれっぽい値は出た(30分前)

でもdiffを見ると違ったので、まずinputを疑う サンプル1のサイコロは3つだったので、手作業で標準展開図に補正してDieの中身をダンプしたのと比較 合ってる 15分前

なのでsolveから全探索を呼んでいる関数を確認して、少し怪しかったので書き換えると答えが変わるも合わない rotateが怪しい説が出てきたので、お人形さんになっていた写経担当を借りてきてrotateの説明をしてもらう 回転が一箇所間違っていたので修正する 合う 出す 通る 10分前 大口叩いて通せなかったらカスなのでヒヤヒヤしていた

GHは目を通してしかいなくて何も分からなかったので後は順位表を見ながらニコニコしていた なんでニコニコしてるんですかと言われたんですが、嬉しいからなんだよな

終了 全体9位

 

ふりかえり・反省

練習通りのステップを踏めなかった。Cは焦りがあったのもあるが、頭を使えていなかった。Fの実装をしているタイミングでようやく頭のギアが入った感覚があったが遅すぎる。ただ、Fをしっかりと詰めた上で書ききれたのは偉い。詰める練習をしていなければできなかったはず。

練習は本番のように、本番は練習のようにとか百万回聞いているが、本当に意識するべき。実装練習ばかりで頭を止めないでしっかりと考察を最近していないため、AOJの500-550の少し考察が必要なレベルを重点的に埋めるべき。本番も大きなミスなくやれるようにあと2週間気合を入れていく。

あとチェックリストを作りましょう(作りました)

 

コード

a.cpp · GitHub

c.cpp · GitHub

f.cpp · GitHub