競プロ強者が沢山やってるので
- 前置き
- 模擬国内
- 事前計画(ICPC)
- 本番
- 結果
- 感想
1.前置き
チームky0sh1nとして参加したtomatoです。
何か競プロ強者が大体やってるので勢い任せて始めました。
当然ながら不定期更新です。
今回の内容は、ICPCの(主に)当日の現場(tomato目線)を。
ただただ時系列順の思い出書きとなります。
2.模擬国内:
とりあえず、ICPCでは改行コードがUNIX系であることを、バイナリエディターから目で確認。
多分なんですけど0完の人たちって、Windowsで参加してる人が多いのではないでしょうか。
運営に報告すれば良いのかなぁって思いながら、こういう面の報告既に沢山されてそうで、言う気にならず本番へ。
(Windowsでは、受け取ったデータの改行コードを認識できず、そもそも入力が失敗する。)
詳しくはこちらの、「改行の数値表現」の項にあります。
3.事前計画(ICPC):
模擬国内には出ましたが本番ははじめての参加のため、
とりあえずコーダー1名、アイデアマン2名で行動。
僕はアイデアマンです。
4.本番:
沢山あるので分割
- 事前準備
- A問題
- B問題
- C問題
- D問題
- E問題
- F問題
- G問題
- H問題
- G問題(リトライ)
- D問題(リトライ)
1.事前準備:
プリンターがものすごく遅い!やばい!
借りた側が言うのもなんだけど、日頃支障でてそう!
結果、約1名がプリンターの前で10分ほどお茶の代わりに紙を汲んでました。
(感想:機材は一番良いのを頼む)
2.A問題:
N=1000から、全列挙で良いよな~ってことで、
①全ての2つの組み合わせの結果を全部vectorにぶち込んでやるぜぇぇぇ!!!
②上から順に見てって、初めてMを下回るまでループしまくる
って提案して次へ(コーダーに丸投げ)
開始10分くらいで終了
3.B問題:
とりあえず " ←これで取得文字列を分割して、文字列配列にする。
あとは
①出来た配列の長さ
②配列のindexの偶奇場合分け⇒同じかどうかの判定をやってく
であとは問題文通り。
Pythonを使う方が楽なので自分がコーダーになるものの、C++のコードを書いてしまってひたすら形式デバッグに追われる。
4.C問題:
B問題で30分も使ってると、他の二人が無事にアルゴリズムを作ってくれた。
それならば!ということで丸投げして自分は問題すら読まなかった。
5.D問題:
①とりあえず2のあまりについてだとは把握
②XOR使えばよくね?に帰着
③結果として0の組み合わせが受理状態だなって感じまでは行く
④その中での組み合わせ個数最大なら行けそう~~~
ここで頭のスタックがオーバーフローして、コーダーに提案だけして一旦撤退。
6.E問題:
もう一人のアイデアマンが凄い出来そうで頑張ってる!頑張って!
7.F問題:
見るからに面倒そう。少なくとも頭が痛そう。放置。
8.G問題:
①シミュレーション問題だ!
②あれ、かならず時計回りか反時計周りで宝物取ってくるよね
③なら、とりあえず反時計回りで考えるか。
④あれ、次の宝物までの最短経路だけ考えればよくね?それでかぶって無ければ?
⑤無理だわ。反例が見つかった。
9.H問題:
①あれ?場合分けじゃね?
②(1)6つの頂点は別々のところにあり重ならない
(2)5回以上の操作はManyで良い
③つまり、最初の状態から一発で重ねられれば3
1頂点を少し動かした後で重ねられれば4
それ以外が5
この辺りでコーダーに提案。受理されたのでぶん投げる。
~~~~ここから、出来そうな問題に時間をかけ始める~~~~
10.G問題:
何かめっちゃ出来そうだったからもう一回やってみる。
①左上⇒左下なら、優先度順「←↓→↑」
左下⇒右下なら、「↓→↑←」…とした、薄氷割りの要領で行けね?
②あ、計算量的に無理だわ。たどり着けなかった場合めっちゃ時間かかりそう。
③枝切りするのか?
この辺りで、計算量が詰んでる気がして終了
11.D問題:
あぁぁぁ!これ、N<=30と30<Nで場合分けすればよくね!?
N<=30なら全探索で終わる。
30<Nなら、全部の組み合わせ考えても2^M<=2^16<6.4万で
メモリも何とかなるじゃん!
ただ、ここで詰まる。2^Mをどう扱うのか。
ここでHをやってたコーダーがDP使えると悟り、実装してもらうことに。
ここで致命的な問題発生。bit演算に必要なライブラリ、bitsetの知識がチーム全員0だった…
結局ここで手詰まりで時間が終わる。
疑似コードで再帰とdpのコードは描いたものの、bitsetについての知識が無ければ多分詰むのだ…(bit演算をvectorでやるには時間がかかり、intでやってるとオーバーフローする)
 ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
5.結果
3完の65位でした… 初めてにしては上々なものの、解けそうなのに解けなかったのが歯がゆい所。
 ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
6.感想
プログラミング歴もやっと1年3か月を超えたくらいですので、知識が全然乏しいです。
今後精進していきたいです(小並感)
早くAtcoderで青になりたい!