---
# System prepended metadata

title: ICPC2023国内予選参加記(coconut milk)
tags: [ICPC, CP]

---

## メンバー
TongariAtamago,nisshy_280,komite（僕）のcoconut milkで出場しました


## 問題
https://icpc.iisf.or.jp/past-icpc/domestic2023/contest/all_ja.html


## A
TongariAtamago
2023に近い数字を探す問題　線形探索

## B
nisshy_280+TongariAtamago

完全に2人に任せてた

あみだくじに＋１本足せるときに目的のところにつなげることができるか

ノーペナで通したのえらい

## C

席替え後のマンハッタン距離がfloor(n/2)以上になるような席替えを構築する問題

市松模様で上下に分けて適当にならべたのがいけそうってなって、チェッカーを書くとOKだったので提出したらAC

チェッカーを書いたのえらかった

## D

少し考えて2べき＋余りで7個以下で構築できることに気づく

7個程度なら全探索すれば良いと思って、nを分け方の全探索(6個,(n-和)の1個),その分け方でうまく構築できるかのbit全探索を書いて、テストすると全然実行が終わらなくて焦る

計算回数を考えると分け方の列挙に100^6から枝狩りで削った分くらいの計算がかかってるのでやばいとなり、7個は絶対できるからnの分け方は(5+1)個にするのと、判定の部分をdpにしたり、枝狩りを増やしたりしたが1ケース1分くらいかかって間に合わんとなってたらコンテストが終わった

---
コンテスト中にどこを改善したのかうまく整理できてないのと、計算回数がどれくらい改善できるか考える前に実装しているのは反省点でもっとメモを取ったり、考えてから実装するのを意識したい

解説を読んで、広義単調増加になるように列挙＋bitset高速化を入れると、1ケース1秒もかからないくらいになって無茶苦茶早くなった、実行時間考えるときは、最高次数だけで良いから係数もしっかり考えようと思う。

## 結果、感想

![](https://hackmd.io/_uploads/B15MnarYh.png)


改善点はたくさんあったが、AからＣノーペナだったし、初手の発想等は悪くなかったのかなという感じでした
最初の4問しか考えられてないし、全部の問題楽しめるくらい強くなりたい

ギリギリ予選通過してそうなので、地区予選も頑張ります！