セグ木を木構造のまま出力する

そのまま配列を出力しても見難いので作った

struct K {
  int l, r, h, k;
};

void SegTree::out() {
  int t = 0, kn = 1;
  while(n > kn) {
    kn *= 2;
    t++;
  }
  int h[t + 1] = {0, 1};
  rep(i, 2, t + 1) h[i] = h[i - 1] * 2 + 1;
  queue<K> q;
  K k = {0, n, 1, 0};
  q.push(k);
  while(!q.empty()) {
    queue<K> nq;
    K pp = q.front();
    if(pp.k > n) break;
    rep(i, 0, h[t]) cout << " ";
    while(!q.empty()) {
      K p = q.front();
      q.pop();
      cout << dat[p.k];
      if(t > 0) rep(i, 0, h[t + 1]) cout << " ";
      else cout << " ";
      K lk = {p.l, (p.l + p.r) / 2, p.h * 2, p.k * 2 + 1};
      K rk = {(p.l + p.r) / 2, p.r, p.h * 2, p.k * 2 + 2};
      nq.push(lk);
      nq.push(rk);
    }
    t--;
    cout << endl;
    q = nq;
  }
}

f:id:deletend:20180117160141p:plain


こんな感じに出力できる

テストケース程度なら問題なさそう?

学校生活振り返り

この記事は N高等学校 Advent Calendar 2017 21日目の記事です


ネタがないので過去を振り返ることになったのですが記憶が曖昧なので時系列順箇条書きで大雑把に書いていきます
競プロ関連のみにする予定だったけど1ページも埋まらなかったので学校生活全体を振り返ります
本当はポエムを書きたかったけど文章力の無さに驚いた


4月

N高提携スクール?のPHHに通い始める
あまり記憶は無いがPCが届かなかったことは覚えている
プログラミングはあまりやらなかった印象

5月

恐らく基礎文法を学んだ
HTML + CSS + JavaScript でスライドショー的なやつを作った気がする
jQuery も扱っていたが僕は何故使うかよく分からなかったので使っていなかった記憶
遅刻に緩い学校だと気づいてしまう

6月

Node.js を使ってサーバーサイドに関する知識を学んだ気がする
ここらへんでインフラ周りが出てきたと思うが当時はよく分からなかった印象
DBとか聞いてもメモ帳に書いておけば良いやんけ!!!とか思っていたので覚えようとしていなかったが正解かもしれない
午前の授業に30分遅れがち

7月

チーム開発が開始する
ゲームを開発するグループとwebサービスを開発するグループがあったがどっちも入った
ゲームはHTML5canvasでの作成だった
webサービスはてブっぽいのを制作
イスを活用し始める

8月

ゲーム開発の一回目の発表があった
作ったやつ
一応製作期間は1ヶ月あったが諸事情により2日で仕上げたものを発表した
上記の理由により[要出典]他のゲーム班の作品よりも圧倒的低クオリティかつ未完成品という良くない結果だった
メソッド名、変数名の重要さを知る
ここらへんから家でゲームをする時間を割いてプログラミングをする日がでてきた
運動をしなくなったせいか体の至る所に不調が出始める

9月

パソコン甲子園というものに出場する
結果は10問中4問正解で予選突破とかなり遠かった
学内ISUCONなるものが開催され1位を取れたが、アプリケーションが簡潔すぎてインフラはあまり関係なかったのでISUCONっぽくなかった
ついでに本当のISUCONにも出たが何もできずに死亡
都内の焼肉はコスパが最悪な事に気づく

10月

ここで webサービス + ゲームの制作発表
webサービスではスクレイピングと検索機能を担当して重みを付けたりしてみた
ゲームは未完成のまま発表の日を迎えたのですごく反省した
ISUCONで何もできなかったのが悔しかったのでインフラ関連を少しずつ勉強し始めた
授業ではあまり理解していないと思っていたインフラだったが、全体の流れをあまり把握できていなかっただけでそれなりに知識は付いていた


11月

ここでTwitter上の声優へのリプライをひたすら垂れ流すアプリケーションを作成したのですがいろいろあれなので公開しません
このアプリケーションが"まともな"webアプリを一人で作り終えた最初のアプリケーションだったと思います
意外と大半のオタクはマナーが良く、本当に一部だけが目立ってるんだなと思った
あとherokuはとても素敵だと思います

12月

JOIと言うものに参加して三完
順位的には中間くらいだったと思う
その後にたまたまAtCoderのABCで30位くらいを取れたので競プロモチベが上がる
N高のレポート提出締め切りがあったが、仲間との *\.✝絆✝./* により見事やり遂げる
某ゲームのイベントで時間と資産を大量に消費するが世紀の大爆死を遂げこの世の真理に辿り着く

1月

ゲームやったりアニメ見たり人生を満喫する
この時期はまたチーム制作が始まっていた(既に終わった?)気がするが何か流れた

2月

記憶喪失

3月

卒業制作でSNSを作成した(未完成
というのも企画から発表まで確か1ヶ月程しか無かったので僕程度がSNSを完成させられるはずもなく死亡
主にフロントが面倒くさかった間に合わなかった
提携スクール卒業😭
webアプリで一発当てて余生を優雅に過ごそうと決意
再び競プロを休んでいたがAtCoderのABCでたまたま一桁順位を取れてしまったのでモチベがまた上がる

4月

家の近くにプログラミングのバイトがないのでマクドナルドでバイトを始める
これは最悪の決断だったので時を戻せるなら園児に戻り英才教育を受けて天才になってた
人がいないと言われるがままにシフトを入れてしまってプログラミングがかなり疎かになる

5月

週一のAtCoder以外プログラミングをしなくなる
アルバイトの業務自体は楽だけど人種が完全に別世界のあれなので色々あれになって自分が社会不適合者だと自覚する

6月

SuperConなるものの予選に応募する
N高の強い人のおかげで難なく突破

7月

競プロを頑張り始める
競プロを頑張るにあたって基礎教養の無さに絶望する
主に英語と数学が必要に感じたがどちらも3以上の評定を取った記憶がない

8月

SuperConの本戦で座る役を務める
そのおかげ[要出典]で4位という結果を残す
カラオケ楽しい

9月

パソコン甲子園の予選に出る
2人組で出場するのだがペアがプロなので難なく突破
ただ、僕一人でも地域枠という形で予選を突破可能だったということだけは書き残しておきたい
ISUCONに向けて再びweb関連に触れ始める

10月

ISUCON予選に出る
メンバーは学生向けのISUCON勉強会に参加していた人で(学生)組んだ
学生枠で本戦出場した
終了30分前までfail(実は勘違い)からの5万点獲得という大波乱?が起こったのでかなり嬉しかった
アプリケーションは少ししか弄っていなかったので苦手だと思われたインフラの知識でどうにかできたのが良かった

11月

パソコン甲子園の本戦に出て9位
ペアの実力的に良い結果ではなかったがこちらも言い訳すると7問目は考察が完了して5問目は実装まで終わってたので実質3位(は?
終盤で解けた問題が積み上がっていくという事故が起きたので来年は実装速度を上げたいと思った
あとお互いに体の状態も良くなかったので来年は前泊したい気持ちがある(僕は単なる風邪明け
どうもプロの方が一人のほうがパフォーマンスが出るとの事なので来年は2チームに分かれて本戦に出る(予定)

ISUCONの本戦があった
結果はfailで終わってしまった
Node.js で出たのだがDBに入る予定のデータをメモリに乗っけた際に toString を抜いてしまい、バリデーション(恐らく型チェック)で落ちてしまったのだが型ガバガバ言語あるあるなのか挙動は至って正常なので原因特定に非常に時間がかかり3時間くらい使ってしまった
合計500行程度のコードを理解するのに2時間かかってしまったのも人のコードを読むのを嫌っていたからだと反省
アプリケーション重視で勝つなら今年が狙い目だっただけに非常に残念

12月

JOIの予選に出た
結果は386点で予選突破
しかしあまり良いスコアではないので本戦はもっと頑張りたい
クラウドソーシングサイトでお金を稼げたが成長を全く感じないので選択肢としては無しかなという印象

総括

最初はN高の入学を考えている方向けに書く予定だったけど、ただただ事象を箇条書きするだけの無意味なものになってしまった
しかし過去を振り返ると将来へのモチベが上がってきたので誰にも読まれない技術ブログくらいの価値はあったかと思います

JOIやISUCONの結果を踏まえて自分が入学当初想像していたレベルは大きく上回っているかなと思います

しかしプロダクトを開発する能力は著しく欠けてると思うし、一般的な学生がプログラミングをやるとしたらそこを頑張るという印象があるので数値として出ない部分でも頑張っていきたい所存です

あとこの記事は主にN高生の方が見ると思うので宣伝ですが #club_computer で一緒に競技プログラミングをする方を募集しています
if文 for文 が書ける方なら始められるので気軽に参加してみてください
パソコン甲子園は年齢制限がないのでどなたでも出れます
現役?高校生の本戦出場枠を潰していきましょう!!!

もうひとつ最後に来年の ISUCON に一緒に出てくれる方を募集しています
目標は本戦出場くらいなので気軽に声をかけてください
ISUCON学生枠は非常に緩いのでwebアプリ応用くらいを終えていれば後は過去記事を読み漁るだけで勝てます(多分