競プロ強者が沢山やってるので

  1. 前置き
  2. 模擬国内
  3. 事前計画(ICPC
  4. 本番
  5. 結果
  6. 感想

1.前置き

チームky0sh1nとして参加したtomatoです。

 

何か競プロ強者が大体やってるので勢い任せて始めました。

当然ながら不定期更新です。

 

今回の内容は、ICPCの(主に)当日の現場(tomato目線)を。

ただただ時系列順の思い出書きとなります。

 

2.模擬国内:

とりあえず、ICPCでは改行コードがUNIX系であることを、バイナリエディターから目で確認。

多分なんですけど0完の人たちって、Windowsで参加してる人が多いのではないでしょうか。

運営に報告すれば良いのかなぁって思いながら、こういう面の報告既に沢山されてそうで、言う気にならず本番へ。

Windowsでは、受け取ったデータの改行コードを認識できず、そもそも入力が失敗する。)

詳しくはこちらの、「改行の数値表現」の項にあります。

改行コード - Wikipedia

 

 

 

 

3.事前計画(ICPC):

模擬国内には出ましたが本番ははじめての参加のため、

とりあえずコーダー1名、アイデアマン2名で行動。

僕はアイデアマンです。

 

4.本番:

沢山あるので分割

  1. 事前準備
  2. A問題
  3. B問題
  4. C問題
  5. D問題
  6. E問題
  7. F問題
  8. G問題
  9. H問題
  10. G問題(リトライ)
  11. 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.感想

AtCoder初めて半年でICPCは難しかったです。

プログラミング歴もやっと1年3か月を超えたくらいですので、知識が全然乏しいです。

今後精進していきたいです(小並感)

 

早くAtcoderで青になりたい!