ICPC2019国内参加記 Tech_ONS編

最近,大学で何を学んだんだろう,何をしてきたんだろう,といろいろ複雑なお気持ちな,四年生の老害,ガナリヤです

今回は,07/12(金)に開催されたICPCプログラミングコンテストのインターネット予選の参加記を適当ながら書いていこうと思います

おそらく,あとでYARUDAKEチームからも参加記が上がると思います(上がるよね(老害))


開始前

午前中,授業だったり研究のお話だったり色々と辛いお気持ちになっていました(かなしいね

かなしくなったので,14:30に会場である部屋に先入りしました(今回,監督員の先生には,この時間帯に部屋を予約してもらうなど,多くのご協力をいただきました.頭が上がりません.あとで感謝の品を持っていこうと思います.)

部屋に入る途中,後輩のkurokuくんに出会いました
覚悟がちげえまろ

早く来すぎたかなと思いながら,持参したUSキーボードの準備やパソコンの立ち上げなどをしていました(大学のキーボードはJISなので)

その後,チームメンバーのsiiiecや三年生のいっちーなども来て,時間を無駄にしていました(集合早すぎた,ごめんなさい)

今回,Tech_ONSは全員が四年生で研究室や,自分の場合入試勉強など非常に忙しく,国内模擬予選しか通し練習が出来ていませんでした.
そのため,自作ライブラリはほとんど去年ので,おそらくバグだらけだったと思います(使わなかったので尚良)

今回持ってった本は

の三冊です(普通だな!)

あと,マスコットとして,ニコニコテレビちゃんと,プロ生ちゃんのアクリルスタンドを持っていきました,かわいいね(かわいいので

だらだらsiiiecと話していると,C_avaも来て,打ち合わせをしながら時間を潰しました
全員研究室が違うので,集まるのは大学でもそうそうないんですよね
四年生って研究するけど,研究できなくないか?

そんなこんなしていると,16:30になり,ICPCが始まりました


ICPCコンテスト

問題リンク

位表リンク

今回のICPCは,去年と同じく最初の方針は同じで

  • C_avaがVisual StudioRTAをする
  • siiiecがA問題を通す
  • ganariyaがB問題を通す
  • CはC_avaのC
  • Dを三人がかりでなんとかする

みたいな感じでした
あと,誰かが解法を書いている間に,エッチなテストケースを書いて嘘を落とす,みたいな方針でした

プリンターの前でganariyaとsiiiecが待機して,C_avaが印刷をしました

B問題を見ると,あ^〜ってなる感じの問題でした
簡単じゃ〜んって思いながら,平気でBFS書いていました(無駄)(戦犯)

コンテスト終了後,kuroku君の解法をきいて,マンハッタン距離でいいじゃんってなりました
今回,自分のミスが響いて結構無駄な計算量を書けてしまいました
次のAtCoderなどのコンテストからは,わかっても,一分追加で考察をしてからコーディングを行おうと思いました

B問題の嘘解法(重すぎ)が生えた時,siiiecがコーディングしてました,はやい

C_avaのエッチなテストケースも通ったので,Aを通すと,そりゃもうAcceptでした,嬉しい

(A問題結局どういう問題だったんだろ)

その後,自分がB問題を解いて,当然遅い実行時間でしたが,Acceptはできました
色々と反省が残るコンテストでした・・・

Bをお通ししたあとは,三人でCをいちゃこら考えていました

C問題は,$3^N$で全探索すればいいな〜ってなって,その後ganariyaとsiiiecで詰めながらコーディングしてました

いま思い返すと,このCも実装をミスっていて,実行時間が肥大化してました
本当に思い返すとなんでそんなコード書いてるんだ?ってぐらいしょうもない実装を書いてて悲しくなりました,ほんとだめだめです

C問題を実行しながら,まあ答えが出れば通るやろ〜〜って,言いながらD問題に移りました

D問題は,カウンタをえいえいする問題で,なんかいやらしい問題だなってなりました(ぱっと見簡単だけど,多分むずい)

三人で考察してると,C問題の出力が出たので,投げるとWA(は?

とりあえず紙出力して,自分がCのデバッグ,
siiiecとC_avaでD問題の考察をしていました

Cは結局,分銅を追加しなくてもよい薬は先に取り出す,という操作でうまく行きました
この処理は,最初に提出する前に一度書きかけて「いらないか!」となって消したのですごい悔しい
すべてが裏目に出ている

Cはその後足りない処理を書き足したら,結局通り,再びD問題で停滞しました

三人で色々と考察を行い,C_avaとsiiiecで実装を始め,サンプル地獄になっていました

その後も色々と考え,セグ木+DP?って思いながら考察してたら非情にも時間になりました

Tech_ONSは今年もまた,3完で幕を閉じたのです


振り返り+老害より

今年のICPCでは,Tech_ONSは
495チーム中,138位で終わりました

お気持ちとしては,悔しいというお気持ちと単純に力不足だったという感覚です

B, Cでガバ考察をしてしまったので,本当に申し訳ないし悔しいです

また,やはり三人がかりでも僕たちだとまだD問題は解けず,これが解けるようにならないと安定してアジアに行けないんだなと思いました(Dの解法は結局DPでした(DはDPのD))

嬉しい点としては,後輩チームが初参加で2完をしていて,頼もしいなと思いました
TNPの競技プログラミングを始めた二年生も合計4人?(自分のおそらくの観測上)になり(最近かなりTNPから増えていて嬉しい),秋田大学もどんどん競技プログラミングや,他のアプリ制作のコンテストに出て,どんどん秋大が強くなればいいなと思いました

このチームTech_ONSで出場するのはおそらく今年で最後なので,アジアに行きたいなぁと思っていました

結果としては駄目でしたが,非常に貴重な経験が出来たので,競技プログラミングを初めて本当に良かったと思います

来年以降もTech_ONSとして自分が出られるかは現状分かりませんが,来年以降も秋田大学で後輩チームがICPCに参加し,アジア大会への切符を掴んでほしいと思いました.


是非,このICPC・競技プログラミングの文化がTNPに続いて,来年以降の後輩チームが国内大会・アジア大会で活躍する姿を老害として見守りたいなと思います.

ガナリヤでした!


YARUDAKE編も見たいなぁ|・`ω・)

ICPC国内模擬戦2019 Tech_ONS参加記

こにゃにゃちは〜〜
ひとまず色々と片付いて,色々と吹っ切れてきたガナリヤです.
将来設計がだいぶ怪しくなってまいりましたねこれは

最近,いろいろとVTuberといい,Twitterといい,ヒリつきすぎていて,嫌な情報社会になってきたなあって感じますね


さて,今回,TNPのメンバーからなる2チーム「Tech_ONS」と「team_YARUDAKE」がICPC国内模擬予選(https://jag-icpc.org/?2019%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8)に参加したので,参加記をまとめておこうと思います(最近投稿も無かったので)


本番一時間前

研究室にこもって面接練習をしていたガナリヤは,ウキウキでTNP部室に向かいました,当たり前ですね
研究室はなんかジメジメしていて,お気持ちが下がるのでア

TNP部室には,すでにsiiiecとkurokuくんがいて,設営が始まってた感じでした

ちなみに僕の所属する四年チームはTech_ONSでganariya, siiiec, C_avaで構成されています.
二年,三年チームはteam_YARUDAKEで2年生二人と3年生d絵構成されています.

設営に取り掛かりましたが,色々な問題が発生してて終始ドタバタしていました.
具体的には

  • siiiecのパソコンが印刷機ようになりそうになり,自分のmacbookが候補になる
  • 自分のmacbookをディスプレイにつなぐケーブルがない
  • C_avaが到着し,Windowsをつけるも,Wifiになぜか繋げない(結局あれはなぜ?)
  • siiiecのパソコンをなんとか持ってくる(印刷機PCを別に用意した)
  • Visual Studioの設定がうんち(僕はよくわからないので,お気持ち担当していました)

多分,本番当日もグダグダになるので,早めに集まろうね!って思いました,反省

僕はこのグダグダというか,ドタバタしながらコーディングしたり考察するのがICPCの楽しいところなのかな?って気がしますね


デュエル開始!(14:00)

14:00からついに模擬戦が始まりました〜〜
長さは三時間で結構長いねって思うかもしれませんが,全然足りないんですよね(11問でるので,無理)

上記の問題文は(https://jag-icpc.org/?2019%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E5%95%8F%E9%A1%8C%E6%96%87%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E3%82%BB%E3%83%83%E3%83%88)

らお借りしました

僕は印刷係だったので,A・B問題を印刷
C_avaはテンプレートの写経地獄
siiiecはA問題の考察をしてました

A・B問題を印刷し終わったところ,siiiecはA問題の解法が生えたらしい 早い 僕いらなくないですか?

そんなこんなで,C_avaが設定してくれた(縁の下の力持ち)テンプレートで,siiiecがコーディング始める

見た感じ大丈夫そうだったので,僕はB問題に行く


B問題は毒の沼地っていうやつでした.

$100{\times}100$マスのうちに,通れるマスと,毒のあるマスがあります.
あなたは最初$(x_i, y_i)$に居ます.
そして,合計100回$(to_{x_i}, to_{y_j})$に順番に移動したいです.
このとき,毒のあるマスを通る回数を最小にしたいです.合計何回ですか?

みたいな問題です.

0-1BFSじゃ〜〜ん(やるだけか?)ってなり,一応考え直してから,僕0-1BFSの書き方知らないってなる(は?)

C_avaが圧縮しようとしていて,それはつらたんではってなる(ぶん回すのが国内戦だと正義なので)

結局仕方がないので,ダイクストラっぽいBFSで誤魔化す実装をすることにする.
なんとなく書いたところ,案の定プログラムが終わらない.

目grepすると,Q.pop()(priority_queueからポップをしてない)をしてない,これ何回目でしょうか

それを外すと,時間はかかるけどうまく動いているっぽいので,現代のCPUとメモリに感謝を捧げて,siiiecとC_avaが考えているC問題に移る

結局,A問題・B問題はAC出来ました


C問題にうつると,C_avaとsiiiecが唸ってた

C問題もグリッドの内容で
上下左右斜め好きな方向に1マス進むと,その1マス先に,廻小宮が生える.
その廻小宮の太刀筋の位置に入らないように繰り返し移動し,目的にまで行く場合最小回数は何回ですか?

みたいな問題.多分よくわからないと思うので問題文を読んでください

C_avaが図示して,説明してくれた.これ答えでは?

サンプルをみると,なんとなくX座標とY座標の絶対値の足し算に,+1か−1かそのまま,みたいな感じがある(優しいね)

僕は考えたくなかったので(こういう問題基本的に僕は解けない),とりあえず偶奇で分ける発想に三人で至る

すると大体の場合は上手くいくが,偶数と奇数のときに例外が発生する感じがある.(偶数が0のときと,0以外の偶数のとき)

とりあえずここで,偶奇以外は自分が実装しておいた

すると,C_avaとSiiiecから片方0ならこれ,そうでないならこの処理!みたいな指示が来たので,実装する,実装汚いね(反省します)

ICPCを信じて,お祈り提出をすると通る
テンション上がりますねこれは,これだからICPCやめらんねえんだよなこれ

二回目の提出も通る,嬉しい,サンプルのおかげ ありがとう全てにありがとう(藤岡弘)

ここで,大体一時間40分経過.ここから地獄のD問題が始まる


D問題は

編集距離のDP問題があるよね!
それに,もう一つの追加で回転(先頭の文字一個を文字列の末尾に持っていくよ)が追加されてるよ!
文字列$X$を文字列$Y$に変形するのにかかるコストを求めてね?

みたいな問題.

ここで発生した問題は,誰一人として編集距離覚えてないことなんですよね(笑い事ではない)

編集距離のアルゴリズムを覚えてないので,その場で自分が編集距離の解法を生やす
半年前の自分が勉強していたので,有能(忘れていたのはぐう無能)

編集距離のアルゴリズムは出たのはいいものの,回転をするDPがよくわからない.

C問題で味をしめた僕たちは,とりあえず回転の回数を全探索しようみたいになって,全探索してみる.

色々試すと,サンプルが合う
これだからICPCはやめらんねえんだよな〜って言いながらSubmitしたら,WAしました

そっからどうしてもD問題の解法が生えない
順位表見ても,また今年もC問題とD問題に大きな崖が出来ていて,やっぱり4完が必須なんだなって思った

C_avaとsiiiecはE問題に行ってしまう(基本的にD解けないときは,Eは絶対に解けないので,今回の国内予選は順位表を見ながらDに専念したい みんながEを解いてたらEに行く戦法を取りたい)

Eは,最大クリークに落とし込む問題だったみたいです,ライブラリ自体持ってないので(こんなん出してええんか?)

結局Dが解けないまま,三時間が経ちました,無情



結局そういうわけでTech_ONSはABCの3完で180チーム中51位でした.
4完が40チームあるのと,本番は500チームぐらいあるので,やはり4完しないと厳しい感じがします

残り時間もだいぶ短くなってきました.
もう一回アジア大会に出れるように,頑張ろうと思います
ガナリヤでした!

TNP競プロ支部の活動結果と今後(春のポエム枠)

あいさつ

114514810
ガナリヤです〜

自己紹介しなくても書いてるの大体ガナリヤなので、要らない気がしてきた・・・

今日はとことんやる気が出ないので、AGCまで時間つぶしに今後のTNP競プロ支部の展望とか書こうかなと思ってます

あと一週間で春休みが終わり、このぐうたらな毎日が終わって、毎日研究と考えると・・・
たぴゃ〜〜〜〜〜〜〜〜〜(一部界隈にしか伝わらないやつ)


競プロ支部って?

競プロ支部って何ぞってなるお気持ちになるので説明します。

我々TNPでは主にゲーム制作やイラストを書いたり、音楽制作などを行うのが主な活動ですが、最近は色々なツール・言語の増加によって、これまでよりも幅が広がった活動内容になってきました。

最近勢力を増しているSiv3D支部や、3Dやクオリティの高い2Dを作るUnity支部。
そして、新しいツールが増える今なお、古のDXライブラリで命を削っている支部もあります。(彼らは特殊な訓練を受けており、精神的ストレスと引き換えに圧倒的デバッグ能力とコーディング能力を身に着けています)

そして、去年の2~4月頃に幾人かで構成された競プロ支部が発足しました。(といっても、ガナリヤが勝手にそう読んでるだけですが・・・

現在は三年生が約3人? と一年生が1人で構成されています?(疑問系なのは、特に競プロ支部集まれ!ってやっていないのとで・・・)


そもそも競プロってなんだよ(哲学)

競プロってなんなんだろう・・・

自分でもたまに迷いますねこれ・・・

競プロは「競技プログラミング」の略で、与えられた問題を制限時間以内に解いてコーディングし、それを提出するやつです。

上のスライドとかが競技プログラミングを物語っている資料でこれを書いた人はすごい人で、競プロ界隈だと知らない人はいません。

例えば、以下の問題を考えてみましょう。


https://yukicoder.me/problems/no/800

問題文(四平方定理)

整数$N$, $D$が与えられる。
以下の2つの条件を満たす正の整数の組$(x, y, z, w)$の個数を求めてください。

1. $x, y, z, w$はそれぞれ$1$以上$N$以下の整数
2. $x^2 + y^2 + z^2 = w^2 + D$


上記の問題の$N$, $D$は問題から与えられます。
例えば、$N=3$, $D=2$のときは

$(x,\ y,\ z,\ w) = (1, 1, 1, 1), (1, 1, 2, 2), (1, 1, 3, 3), (1, 2, 1, 2), (1, 3, 1, 3), (2, 1, 1, 2), (3, 1, 1, 3)$
が条件を満たします。

勘の良い方、またはプログラミングをした人なら
全探索すればいい

と思うと思います。
これは間違っていないです。

但し、この問題は
$N{\leq}2*10^3$
$D{\leq}10^6$
という制限が与えられています。

全探索をすると、これの計算量は$(2*10^3)^4 = 8*10^{12}$です。
実は$10^8$回計算すると$1$秒の実行時間で、上記の全探索をすると、
これは44時間もかかってしまいます。

全探索すると$44$時間かかってしまう計算をするわけにはいきません。
この問題を$2$秒以内に解かないとAC(Accepted)がもらえないからです。

以下、解法です。

$x, y$を全探索することを考えてみます。
するとこれは$2000^2 = 4000000$であり、実行時間は$0.004$秒ぐらいなので間に合います。

$2$つめの式を変形すると
$w^2 = x^2 + y^2 + z^2 – D$で
先程$x, y$を全探索したため、定数とみなせます。
よって、$x^2 + y^2 – D = T$という定数に置くと
$w^2 – z^2 = T$
と表せます。

このようにすると、$w, z$を全探索して、$T$という計算結果になるような個数を保存すれば良さそうとなります。

あとは、この$w, z$の計算を先に前計算しておき、その後、$x, y$を計算しておけば、これは計算量は$O(N^2)$に抑えることができ、ACを貰うことができます。

using LL = long long;
 
 //~~~~~~~~~~~~~~~~~~~~~_(^~^ 」 ∠)_~~~~~~~~~~~~~~~~~~~~~
 
 
 int main() {
 
     int N, D;
     cin >> N >> D;
 
     int base = 100000000 / 2;
     vector<int> cnt(100000000, 0);
 
     for (int w = 1; w <= N; w++) {
         for (int z = 1; z <= N; z++) {
             cnt[base + w * w - z * z]++;
         }
     }
 
     int ans = 0;
 
     for (int x = 1; x <= N; x++) {
         for (int y = 1; y <= N; y++) {
             int d = x * x + y * y - D;
             ans += cnt[base + d];
         }
     }
 
     cout << ans;
 
     return 0;
 }

競技プログラミングは以上のように、まず3つのパートに分かれます。

まず、問題を読むパートです。Writerがどのようなことをさせたいのかを出来るだけ早く読み取ります。

そして、次に考察パートです。ここが苦しいところです。
僕はアタマが悪いので、ここでだいたい解けないです。

そして、もし考察が出て解法が生えたら、それを実装する必要があります。

この、「考察が出来る」と「実装が出来る」が別なのが難しいところで、
「考察が出来た!」ってなっても実装がゴミクソめんどくさいときがあります。
また、「実装は得意!」でも考察が全く出来ないときがあります。

数学オリンピックなどでは、この考察が出来るパートが要求され、さらに競技プログラミングではここに「プログラミング」の要素が追加されるわけです。

先程の問題と、解法を読んでピンと来る人は少ないだろうなと思います。
自分もまだまだ弱いですが、始めたてはプランクトン並でした(さっきの問題の解法なんてINF時間座っても生えません。)

でも練習次第で、ある程度は解けるようになります。


競プロのメリット・デメリットって何?

最近情報業界でかなり人気になってきている競技プログラミングですが何が楽しく、何がメリットなのでしょう・・・

自分もたまに、やっぱつれぇわ・・・ってなりながら競技プログラミングをしています。
それでも一年は続けていられているので、自分の性分にあっているのかな〜〜と思っています。

メリット

競プロを通して得られることは多いです。

まずは、「実装能力」が挙げられると思います。
競プロでは、あらゆるデータ構造とアルゴリズムを使用します。
競プロ以外のアプリ開発やゲーム開発は、競プロの実装と比べると明らかに楽なので、これまでより、楽にコーディング出来たりします。
また、実装できなさそう・・・と感じることがかなり減ると思います。

次に、考察力があがると思います。
競プロではあらゆる問題に対し、
1. 仮説を立てる
2. コードを書く
3. デバッグをする

という課題解決のステップを非常に細かく踏みます。
色々な知識がつくのも競技プログラミング特有のものだと思います。

そして、レートが出て、客観的に自分の実力がわかるがあると思います。

以上は自分のAtCoderでのレート推移です。
グラフの伸びを見る限り、天才型ではないのはひと目で分かります。(くやしい

でも、だからこそ、練習をして色んなアルゴリズムを覚えて、レートがあがり、初めて400点の問題をコンテスト中に解けたときは、人生でかなり楽しかった瞬間に入ります。

やはり楽しい!!!!!!!
っていうのが根幹にある感じです。
(ただ、楽しい!っていうのはコンテストに出てレートがつかないとわからない部分ですね・・・)
承認欲求が満たされる音がします。


デメリット

デメリットも色々とあります。

まず、「アプリ開発やフレームワークの知識はつかない」
という点です。
競プロで学べるのはアルゴリズムや実装・考察力なので、なにかアプリ開発が出来たり、フレームワークが使えるかは別になります。

ただ、アプリ開発出来て競プロ出来ない人は見かけますが、競プロ出来てアプリ開発出来ない人はほとんどいないです。
ただ、競プロもアプリ開発もやらないとアプリ開発の知識はつかないです・・・

2つ目に、競プロで生活をかなり支配されます。
AtCoderは土曜日の夜九時から二時間ぐらいなので良いですが

Codeforcesというサイトはロシアで運営されているコンテストであり、深夜12:35から二時間ぐらいあります。
普通に生活リズムが乱れます。

また、たぴ〜〜〜や、AC、tourist語録など、競プロ用語に支配される日が来ます。
知らないうちに「おきもち」という単語を永遠に使い続けることになります。


競プロに向く人・向かない人

競プロですが、誰しもに向いているものではないです。

競プロが好きな人はいかのようなことが好きな傾向にあります。

  • 人と争うのが好き
  • 承認欲求が強い
  • 数学・アルゴリズムが好き
  • 順位が好き(レートが好き)
  • 考えることが好き(パズルが好き)
  • 快感を欲している
  • 自分が好き
  • アプリ開発などの長期的スパンが続かない
  • ツイッターが好き
  • 音ゲーがすき(音ゲーマーみんな競プロ強いんですがなぜ・・・)

特に、アプリ開発などの長期的スパン開発が続かない人には向いてますね・・・
1問1問が短いので、さらっと解くを何回も繰り返しているうちに強くなります。

競プロが好きでない人は個人的に以下のようなものがある気がします

  • 順位をあまり気にしない
  • 承認欲求が少ない
  • 上昇志向がない
  • 数学・アルゴリズムよりも、開発でプロダクトを作るのが好き
  • 短い努力を繰り返すより、長い努力をしたい
  • アプリ開発が好き

結構、好きな人と好きでない人は正反対の位置にある気がしています。

やりたいことがない人は競プロを始めてみるといいかもしれません。


去年一年の活動について

去年一年、競プロ支部では基本的に個人活動でした。
競プロは基本的には個人競技なので致し方ないところではあります。

ただ、去年7月に行われたICPCというチーム大学対抗競プロ大会で

TNPの三年次かつ、同じバイト先の自分含む計三名でICPCインターネット予選に参加し、色々な奇跡が重なってアジア大会に出られることになり、去年の12月に参加しました。

これまでの人生で一番満たされた3日間だったと思います。
もっと競プロに打ち込んで実力をつけたいと思いました。


4月からの一年の展望

競プロ支部はどのようになっていくのでしょうか・・・
正直ようわからんです・・・

現在、現一年生(新二年生)の一人が昨年から競プロを始めており、競プロが広まって嬉しいなぁというお気持ちになっています。
レートもみるみる上がっているので、将来抜かれそうで怖いなぁとなっています。(特に数学が好きなのが非常に怖いポイント)

これからどんどん、新一年生にも広まって、ゲーム開発もできて、競技プログラミングもできる学生が増えればいいなと思っています。

とりあえず今年の7月のICPCに向けて日々精進して行きたいです。

まずはそこからはじめて、普通の国立の中では、秋田大学が競技プログラミングである程度強い大学と言えるように頑張っていこうと思います。

あと、にじさんじの卯月コウってやつエモいから見てくれよな(後方


追伸

どんどんブログを、新入生歓迎に向けて活性化させていきたいお気持ち

みんな書いて♡俺も書いたんだからさ・・・(いやです・・・)

新入生へ: 生協パソコンを買う前に少し考えてもいいんじゃないだろうかという話(個人差があります)

ここから下の内容は一個人の意見・推論です

来たる新入生へ

合格おめでとうございます。

これから始まる新生活に、新入生の方々は胸踊らせ、日々楽しみ、もしくは多少の不安を感じていることでしょう。

そう、4月は始まりの季節。

楽しいことや不安なことが一気に押し寄せ、この時期はかなり精神的にブレが生じる時期でもあります。

そして、この時期はパソコンを買い換える時期で、大学に入学準備に行くとパソコンを勧められます。

彼らは学生の味方です。しかし、営利団体でもあります。
儲けを出さないといけません。
そこは理解しないといけません。


パソコンの話

合格が決まると、彼らは大学にきて、彼らの一員になることを強いてきます。
これは仕方ありません。彼らの意見を飲みましょう。
ここは気持ちを抑えてスパイになるのです。

ただし、生協パソコンは買う前には色々と考え直してみましょう。
多くのTNP部員が被害にあっています。


彼らはかなり低スペックのPCを高い値段で売ってきます。
おそらく彼らの言い分は

「保険がつく」だの
「パワポがつく」だの
「頑丈」だの

電気店でも言われることを言ってきます。
鵜呑みにしてはいけません。自分で考えて行動しましょう。

同じ値段でどれ位のパソコンが買えるでしょうか?

例えば、「MacBook Pro」が買えます。

ほぼ同じ値段で、保険がつき、Macというかっこいいものが買えます。
Macはプログラミングのおける環境構築がWindowsに比べて遥かにしやすくUIも統一されています。
・・・Linux?そういうのもあるのか

僕はMac派なのでMacを押します。
現在、キャンペーン中なので、割引+二万円キャッシュバックがついてきます。

さらにMacのいいところは、売るときの値段が大体買った値段の半分です。
これが強い

持ち運びじゃない、デスクトップならiMacが買えますね。
そこそこのスペックが買えます。
四年間のプログラミングには有り余る性能があります。

Windowsがいい??
ならば、Surfaceなどの選択肢があります。
薄くて使いやすく性能もいい。
生協パソコンが駄目とはいいませんがなにかと入らないものがついていたり、彼らの懐にはいるお金がおそらく多い。

BTOもありです。

私がいいたいのは、生協パソコンに甘んじてはいけないということです。


最後になりますが、まだ間に合うのなら、他のMac製品や、Windowsパソコン、BTOなどを見てみるといいです。

大学では優しい人もいますが、汚い大人がうじゃうじゃいます。
自分で考えて行動すると良さそうです。

ガナリヤでした


追伸

自分で選んだパソコンでのプログラミングは非常に楽しいです!!!
四年間付き合うと思って大事に選んであげてください!!!
Macはいいぞ!(後方彼氏面)

バージョンが上がってLaTeX出来るようにした話

こんにちえるえる〜〜

なんか久しぶりですね。

ガナリヤです。新しいバージョンにしたせいか、色々と不具合が起きて辛いです・・・なんとかします・・・


WordPressのバージョンが上がった話、使い方とLaTeXの話をします


WordPressのバージョンが上がった話

WordPressというシステムを現在、TNPでは使っています。

WordPressはPHPで構成されているフレームワークであり、拡張しやすく、これまでブログよりも使いやすい点があります。
また、WordPressに移行した理由として

  • 全員が使える。
  • HTMLを知らなくても書ける(ビジュアルで書ける)

という点があります。

現在、そのバージョンが上がり、新しいエディタGutenbergというものが導入されました。

このエディタでは、ブロック構造が採用され、各段落を一つのブロックとして構成します。

上記の段落は、以下の図のようなブロックとしてなっており、ブロックは自由に移動できます。

今回のエディタによって、よりノンプログラミングにブログをかけるようになりました。

ただ、これまでのブログのエディタに慣れていた人には辛いですが(現在辛いです・・・)

使ってみると分かると色々と分かると思います〜


マークダウンを使うときは

プログラマーには、マークダウンというものに慣れている人がいます。
僕もその一人です。
マークダウンを使うとより高速にブログを書くことが出来ます。(ビジュアル操作を気にしなくていいと言うと伝わりやすいでしょうか・・・)

現在のエディタでマークダウンを書くには以下のようにしてください。

自分のパソコンの「Boostnote」などでマークダウンを書き、ブロックにコピペしてください。

すると、自動でマークダウンから、普段どおりの大きさやリスト、水平線に変換されます。

よって、現在は、このWordPressエディタ上でマークダウンはかけません。(一部はかけます。)
これからWordPress上で書けるようにする方法はないか模索します。


改行の仕方

ブロックごとに書きますが普通に改行すると(エンターを押すと)

このように一行多く空きます。

なので、ブロックないで改行しようかな〜〜ていうときは「Shift + Enter」をしてください。
すると、一行多く空けない通常の改行ができます。


コード挿入の仕方

ソースコードを挿入したい時があると思います。
そのようなときは以下のようにしてください。

「フォーマット」に入っている「Highilghing Code Block」というものを選び、ソースコードを挿入してください。

すると、ソースコードを挿入できます。


LaTeXの使い方

プログラミングの記事を書くときは
変数を$x$としたり、
$$ y = 10x + 2$$

のように数式を使いたくなると思います。

これはLaTeXというもので実現できます。(TeXがもとであり、それを拡張したものがLaTeXだと思っていいかと思います。)

LaTeXを書くには半角の「ドルマーク $」でLaTeXしたいものを囲ってください。

つまり、 $x$と言った感じです。(これは、ドルマークを全角で表現しています。ここで半角にしてしまうと、LaTeXになって、どのようになるかが表現できないので・・・)

よって、LaTeXしたいときは、半角のドルマークで数式などを囲ってください。

また、中央に
$$ y = x$$

のように表示したいときは半角のドルマークを
$$ y = x $$

のようにすると、中央寄せができます。


最後に

多分伝わらないと思います・・・(すいません)

今度部室で使い方をきちんと説明したいと思います。
また、実際に触ってみると使い方がわかると思います。

自分もまだこれに慣れてないので、大分読みづらいかと思います。すいません。

改善できるようにいろいろ工夫していこうと思います。

ガナリヤでした〜

AtCoder Beginner Contest 112

こんばんえるえる〜〜〜〜
ガナリヤです
大学の後期がついに始まりましたね
今週一週間は毎日しんどくて未だに体の疲れが取れません。
コミュニケーション能力を付けないとこのままではまずい気がします。

今回は、AtCoderBeginnerContest112に出ました。
結果としては、ABCD4完は出来ましたが、Cで4WAしているのでもうちょっと細かい部分に意識をしないといけませんね・・・
早速内容を振り返っていきましょう!


A 「Programming Education」

問題文

AtCoderはクソデカ年商となり、プログラミング教育をするようになった。
入力から自分の年齢Nが入力される。
N=1なら”Hello, World”と出力せよ。
N=2ならA+Bの答を計算せよ。

解法

やるだけです。
もう20秒ぐらい早くとけるようになりたいです。


B 「Time Limit Exceeded」

問題文

Xさんは、外から家に帰ろうとしています。
現在位置から家に帰るルートは、N個存在しますが、それぞれに係る時間tiと、かかるコストciがあります。
時間T以内に、帰らなければいけない時、最小のコストを求めてください。

解法

時間T以内なので、時間T以内のルートのみを列挙して、さらにその中でも一番コストの低いものを出力してしまえばいいです。
気をつける点としては、ルートが一つもない場合はTLEと出力しないといけないので、最初の変数の初期化で上限いっぱいにしておいて、値が更新されてなければTLEとしないといけません。
実装に2分もかかったので半分ほどにするひつようがあります。

コード


int main() {
 
    LL N, T;
    cin >> N >> T;
 
    LL cost = LONG_LONG_MAX;
    for (int i = 0; i < N; i++) {
        LL c, t;
        cin >> c >> t;
        if (t <= T) {
            S_MIN(cost ,c);
        }
    }
 
    if(cost == LONG_LONG_MAX){
        OUT_L("TLE");
    }else{
        OUT_L(cost);
    }
 
    return 0;
}


Pyramid

問題文

問題文長すぎるのでここを見て→ https://beta.atcoder.jp/contests/abc112/tasks/abc112_c

解法

内容としては簡単だったのですが、3つ特殊ケースがあり、そのケースに気づくまで時間がかかってしまいました。

制約を見るとCxもCyも0~100以内なので、全探索しても余裕で間に合うことが分かります。
中心のCx、Cyを仮に全探索してみます。
すると、中心の高さHを求めたいわけですが、この高さは他の点1つを選んでしまえば逆算することが出来ます。
そうして求めたHと他の点を全て比べて、条件を満たせばそれが答えになります。

しかし、この解法だけだとうまくいかない場合があり、参考にする点が高さ0の場合です。
高さ0の場合、もともと高度は(H -|X – Cx| – |Y – Cy|, 0)のため、マンハッタン距離で0だったのか、最初から0だったのか判断することが出来ません。
よって、関係ない答を出力してしまう可能性があります。
よって、そのケースは省いて計算する必要があります。
体感的にBレベルでしたが、特殊ケースだけはDレベルな感じがしました。

コード

int main() {
 
    int N;
    cin >> N;
 
    VLL x(N), y(N), h(N);
    REP(i, N) cin >> x[i] >> y[i] >> h[i];
 
    for (LL i = 0; i <= 100; i++) {
        for (LL j = 0; j <= 100; j++) {
            LL H = 0;
            for (LL k = 0; k < N; k++) {
                if (h[k] != 0) {
                    H = h[k] + ABS(i - y[k]) + ABS(j - x[k]);
                    break;
                }
            }
            if (H <= 0) continue;
            bool good = true;
            for (int k = 0; k < N; k++) {
                LL _h = C_MAX(H - ABS(i - y[k]) - ABS(j - x[k]), 0LL);
                if (_h != h[k]) good = false;
            }
            if (good) {
                cout << j << " " << i << " " << H << endl;
                return 0;
            }
        }
    }
 
    return 0;
}


D Partition

問題文

整数N, Mが与えられます。
a1 + a2 + ・・・ + aN = Mとなるような長さNの数列aにおいて、a1~aNの最大公約数となる最大値を求めてください。

解法

Mが与えられるので、可能性のあるaの組み合わせを作成し、その最大公約数を求める必要があります。
最大の最大公約数であるため、少し工夫しないといけません。なぜなら、制約でNが10万のため、計算量的にNlogNが最大であるためです。

そこで、最大公約数について一度考え直して見ます。
最大公約数は、a全てにおいて、共通の約数を持っており、共通の約数ということは同じ倍数を持っているということに等しいです。
共通の倍数をKとすると
Kb1 + Kb2 + ・・・ + KbN = Mということになります。
つまりM = K * (b1 + b2 + ・・・ + bN)というわけで、Mは因数としてKを持つことが分かります。
よって、Mに対して、約数を列挙し、その約数の中で、NをかけてもMを超えないものが答となります。
約数をTとして、T
N < Mのとき、数が余らないか?というう話になりますが、Mも因数Kを持つため、うまく配分すれば全ての変数がKを因数に持つことが分かります。

素因数分解はO(√N)でできるので、計算量的にも間に合うことが出来ます。

今回のDは3分で通せたので、成長を感じます。(なお、C)

コード



//nの約数
template<typename T>
vector<T> DIVISOR(T n) {
    vector<T> v;
    for (LL i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) {
                v.push_back(n / i);
            }
        }
    }
    sort(v.begin(), v.end());
    return v;
}
 

int main() {
 
    LL N, M;
    cin >> N >> M;
 
    auto divisors = DIVISOR(M);
    LL maxV = 1;
 
    for (int i = 0; i < SZ(divisors); i++) {
        if(divisors[i] * N <= M){
            maxV = divisors[i];
        }
    }
    OUT_L(maxV);
 
    return 0;
}
 
 

### 感想

今回の問題は、Cが一番難しかった感じがあります。
4WAは流石に出しすぎなので、もうちょっとミスを減らさないといけませんね・・・

ガナリヤでした!

ICPC2018国内予選参加記 Tech-ONC

こんばんえるえる〜〜
毎度ガナリヤです!
部室行かなくてすいません!活動はしてるんです!集中力の問題で家でやってます・・・(お兄さん許して・・・)
今日は、ICPC国内予選に参加したので、来年のリベンジのために参加記を残しておこうとおもいます。
 
 

チーム Tech-ONC

チームTech-ONCはTNP部員かつ、同じ競技プログラミングバイト先の三人で構成されています。
思考力・実装力担当の我らが部長!こしょう!
C++の魔法使い!サバ!
手広無力おじさん!ガナリヤ!
の三人です。
このチームの特徴として

  • 普段アルバイトで、競技プログラミング問題制作を行っている
  • 得意なことがそれぞれ違い、バランスが取れている
  • 三人共コーディングを担当できる
  • いい意味でも悪い意味でも、そこまで競技プログラミングコーディング力が離れていない(他チームは、一人だけ無茶苦茶強いところが多かったりする)

という点があります。
僕が誘わせていただき、引き受けていただきて本当に嬉しかったです!


参加記

事前準備

統計の授業を三人で抜け出してご飯を食べる。
チョコレートがおいしかった。
その後、コーディング場に移動し、それぞれマクロや本の準備をしていた。
その間、サバがVisualStudio設定RTAしてて面白かったです、来年は僕も設定できるようになりたい

16:10頃、監督の先生が到着(本当に引き受けていただきありがとうございます!)
雑談をしつつ、そわそわしながら開始を待つ。
  

ICPC予選開始

16:30から予選開始。
サバニキが印刷をぶん回しつつ、僕がA問題の紙を読み、こしょうがB問題の紙を読み始めました。
その間、サバがVisualStudioの設定やマクロの準備をしており、縁の下の力持ちでした!(またnext_combinationの実装もしてもらってしまった・・・来年までにはもっと簡単な実装にします・・・)サバありがとう!

A問題 所得格差は、N人の合計の平均を取って、平均より小さい人数を数えるだけの問題で非常に簡単でやるだけでした。年々A問題は簡単になっている気がする・・・
ハラハラしつつ、doubleのガバに気をつけてAC

  

B問題とC問題

A問題を解いた後、こしょうがB問題へ。
僕とサバでC問題に移動。

こしょうにきが解いている間、C問題を二人で話し合う。
C問題 みなとハルカス

C問題は、整数bが与えられ、1~Nまでの中で連続した整数の和がbに一致する中で、最長のものを出力せよという問題でした。
二人で話し合った結果、部分累積和で10^8までぶん回すか、しゃくとり法で実装するかの二択になりました。
ここで壮大なミス。
絶対に部分累積和じゃ通らないのに、部分累積和の案を採用。ふたりともしゃくとり法はあまりお得意なお気持ちではないため、部分累積和に逃げてしまった・・・、このミスが無ければDの実装が間に合ったかもしれない(申し訳ない)

間違った部分累積和の実装が行けそうになったとき、こしょうの実装でエラーが発生していた模様。
コードを印刷してもらって、エディタを空けてもらって入れ替わりで僕が嘘解法を実装。
ちなみに、今回のB問題はCよりずっと難しかったようで、さらっと解いてるこしょうやっぱやばい。

嘘解法のCを実装した僕
「できた!天才か〜〜〜?」←嘘解法で喜んでいるクズの図
10^9の実装のため、テストケースだけ通して、もう一度こしょうと交代。
こしょうがB問題の添字ミスと、問題文の勘違いに気づいたらしく難なくAC。こしょうにきは、問題文読み間違い以外基本的にすべて通している(すごい(すごい))

その後、こしょうに変わってもらって、投げていたテストケースを見ると、数が合っておらず、嘘解法であったことに気づく(当たり前だよなぁ?)
急いで、しゃくとり法で実装してAC。やっぱ最初からしゃくとり法にするべきでした、チキっちゃだめやね・・・
  

D問題

ここから毎回僕たちが苦戦しているD問題以降パートへ。

サバニキがD問題とE問題に目をつけていて、問題概要や、解き方のコツを教えてもらった。
D問題 全チームによるプレーオフは、サッカーの試合をするとき、すべてのチームの勝敗が一致し、全員で仲良しになる総数は何個あるか?という問題だった。

僕とサバでDはやべえな・・・となり、他の問題をいろいろ見ていた。よくよく考えるとこれが悪手だった気がする。最初からずっとDのみに取り組んでいれば、時間が間に合ったかもしれない(悔しい・・・)

その後、こしょうもDに参戦し、こしょうとサバが解き方の方針を教えてくれた。(5人なら、必ず全てのチームが2勝2敗とか、普段の自分一人のコーディングなら絶対に気づけてない・・・)

その後しばらく三人でDにうなり続け、うだうだ言いながら、意見を出しつつ、next_combinationで1と0の組み合わせを求めれば計算量はあまり増えないということに気づく(正直合ってるか分からん)
よくわからないまま、時間が無いため、僕が突発的に考えた多分正攻法ではない、汚いアイディアを実装することに。
僕とこしょうでペアプロしつつ、サバがnext_combinationの実装をしてくれた(来年までにはもっと分かりやすいライブラリつくる許して・・・)
こしょうとサバのこしょうを借りつつ、ガバガバ実装を行い、時間と戦いつつ、コーディングが完成。
奇跡に祈りつつ、実行したところ、添字エラー。添字エラーを解消している中で、時間になってしまった・・・

  


振り返り

ICPCに参戦してみて、すんごい楽しかったです。
他の人と、問題を解くためのアイディア出し合ったり、ふざけながら問題通すのって、学生のうちしかできない気がする(仕事になると、ふざけることはできない・・・)
また、自分の実装の弱さに気付かされた回でもありました・・・。他の二人の実装がすごい綺麗で、僕のコーディングがかなり汚いので、デバッグしづらくて二人がかなり僕のコードを追うの辛かったと思います。もっと簡潔なコーディングできるよう目指していきたいです。

何はともあれ、すごい楽しかった
来年もこの三人でTech-ONCとして出るという話をした。
来年は三人共、競技プログラミングがうまくなり、僕はAtCoder年内中に青色、来年のICPCまでに黄色になっているはずなので(希望的観測)、来年のチーム名はTech-ONS(O(N^2))でしょうか・・・

何も考えず、今日あったことをそのまま書いているだけで、読みづらいと思います。すいません。
それぐらい楽しかったです
明日はSoundHound頑張ろうと思います!

ガナリヤでした!

テンプレートを見ていくだけ

祝!テンプレート肥大化!

   
   
このブログには僕しか住んでいない気が・・・
にじさんじ箱推しガチ勢ガナリヤです。
今回は、自分の使用しているテンプレートが自分でも管理しきれなくなったため、公開しつつ見直していこうと思います。
この記事の一番下にお借りしたサイトなどを記述させていただきます。


まずは全体のソースコードを貼っていこうと思います。

はえ〜すっごい長い
でも、コンパイルは余裕で通るし、コード読みやすくなるしええやろ!(無謀)

   
少しずつパーツごとに見ていこうと思います!
   


include


//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>

using namespace std;

c++では、includeで使用する関数などのヘッダファイルを取り込んで使用します。
中身の実体であるcppファイルはたいてい別にあって、ヘッダファイルは宣言のみを基本的に行うのですが、標準ライブラリはすべてヘッダファイルに実装しているみたいですね。
   
   

typedef

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<int> VI;
typedef vector<bool> VB;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<VI> VVI;
typedef vector<VB> VVB;
typedef vector<string> VS;
typedef vector<VLL> VVLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<int, string> PIS;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;

long longなど、よく使用する型名や、vectorなどはエイリアスをつけています。
正直あまり使用しないもののほうが多いですな・・・
   
   

数値・文字列

//数値・文字列
//------------------------------------------
inline int toInt(string s) {
    int v;
    istringstream sin(s);
    sin >> v;
    return v;
}

inline LL toLongLong(string s) {
    LL v;
    istringstream sin(s);
    sin >> v;
    return v;
}

template<class T>
inline string toString(T x) {
    ostringstream sout;
    sout << x;
    return sout.str();
}

inline VC toVC(string s) {
    VC data(s.begin(), s.end());
    return data;
}

template<typename List>
void SPRIT(const std::string &s, const std::string &delim, List &result) {
    result.clear();
    string::size_type pos = 0;
    while (pos != string::npos) {
        string::size_type p = s.find(delim, pos);
        if (p == string::npos) {
            result.push_back(s.substr(pos));
            break;
        } else {
            result.push_back(s.substr(pos, p - pos));
        }
        pos = p + delim.size();
    }
}

string TRIM(const string &str, const char *trimCharacterList = " \t\v\r\n") {
    string result;
    string::size_type left = str.find_first_not_of(trimCharacterList);
    if (left != string::npos) {
        string::size_type right = str.find_last_not_of(trimCharacterList);
        result = str.substr(left, right - left + 1);
    }
    return result;
}

template<typename T>
bool VECTOR_EXISTS(vector<T> vec, T data) {
    auto itr = std::find(vec.begin(), vec.end(), data);
    size_t index = distance(vec.begin(), itr);
    if (index != vec.size()) {
        return true;
    } else {
        return 0;
    }
}

#define UPPER(s) transform((s).begin(), (s).end(), (s).begin(), ::toupper)
#define LOWER(s) transform((s).begin(), (s).end(), (s).begin(), ::tolower)

数が多いので一つ一つ見ていきます。

  • toIntは文字列を受け取って数字にして返します。こういうの合ったほうが何かと便利ですね。速度は遅いですが・・・
  • toLongLongはtoIntのLL版
  • toStringは引数を受け取ってStringにして返します。ostringstreamってなんなんですかね・・・
  • toVCは文字列を受け取ってvectorのcharを返します。なんだかんだ変換する必要が多々あるので便利です。
  • TRIM関数は文字列をきれいにして返します。ただ、普通の場合入力は整理されているためあまり使いませんね・・・
  • VECTOR_EXISTSはテンプレートを使用し、vectorを受け取って特定のdataが存在するかどうかを返します。自分でmain内に書けるレベルですが、読みやすくするためよく使用します。
  • UPPERとLOWERは文字列を受け取ってstd::transformで大文字と小文字に変換します。このレベルは普通string型のメソッドにあるべきだと思うんですけど!!!
       
    SPRIT関数はちょっと癖が強いため以下にコードを書いていこうと思います。

    
    int main() {
    
        string str = "abc def gji";
        VS inputs;
        
        SPRIT(str, " ", inputs);
    
        return 0;
    }
    
    

これはSPRIT関数は3つの引数を受取ります。
第一引数は入力文字
第二引数は文字を分割するためのトークン文字列
第三引数は分割された結果を格納するvectorです。
vectorを使用しているので、何個に分割されるか考える必要がなく、自動で返ってくるので便利ですね・・・

   
 

四捨五入


//四捨五入 nLen=小数点第N位にする
//------------------------------------------

//四捨五入
double ceil_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut + 0.9);
    return dOut * pow(10.0, -nLen);
}

//切り捨て
double floor_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut);
    return dOut * pow(10.0, -nLen);
}

//切り上げ
double round_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut + 0.5);
    return dOut * pow(10.0, -nLen);
}

//n桁目の数の取得
int take_a_n(int num, int n) {
    string str = toString(num);
    return str[str.length() - n] - '0';
}

ceil, floor, round関数の拡張のようです。
自分でもまだ仕組みをよく理解していないため、勉強しようと思います。
標準ライブラリの関数より、小数点以下の桁数を指定できるため細かいです。
take_a_nはそのままです。/=10とかするのが面倒なので文字列にしてから取り出してます。

   
   

進数

//進数
//------------------------------------------

//"1111011" → 123
int strbase_2to10(const std::string &s) {
    int out = 0;
    for (int i = 0, size = s.size(); i < size; ++i) {
        out *= 2;
        out += ((int) s[i] == 49) ? 1 : 0;
    }
    return out;
}

//"123" → 1111011
int strbase_10to2(const std::string &s) {
    int binary = toInt(s);
    int out = 0;
    for (int i = 0; binary > 0; i++) {
        out = out + (binary % 2) * pow(static_cast<int>(10), i);
        binary = binary / 2;
    }
    return out;
}

//"ABC" 2748
int strbase_16to10(const std::string &s) {
    int out = stoi(s, 0, 16);
    return out;
}

//1111011 → 123
int intbase_2to10(int in) {
    string str = toString(in);
    return strbase_2to10(str);
}

//123 → 1111011
int intbase_10to2(int in) {
    string str = toString(in);
    return strbase_10to2(str);
}

int intbase_16to10(int in) {
    string str = toString(in);
    return strbase_16to10(str);
}

//123→ "7B"
string intbase_10to16(unsigned int val, bool lower = true) {
    if (!val)
        return std::string("0");
    std::string str;
    const char hc = lower ? 'a' : 'A';     // 小文字 or 大文字表記
    while (val != 0) {
        int d = val & 15;     // 16進数一桁を取得
        if (d < 10)
            str.insert(str.begin(), d + '0');  //  10未満の場合
        else //  10以上の場合
            str.insert(str.begin(), d - 10 + hc);
        val >>= 4;
    }
    return str;
}

//整数を2進数表記したときの1の個数を返す
LL bitcount64(LL bits) {
    bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);
    bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);
    bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);
    bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);
    bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);
    return (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff);
}


普通の人は用意してないと思うレベルで用意しています。
TechFULの中級編をやり続けるとこうなります。
ハゲるかと思いました。
strbaseは文字列を受け取ってint型を返します。
intbaseはint型を受け取ってint型を返します。
bitcount64の2進数にしたときの1の個数を数える関数のビット演算の仕組みがよくわかっていないので要学習ですね・・・

比較


//comparison
//------------------------------------------
#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define C_MIN(a, b) ((a)<(b)?(a):(b))
#define C_ABS(a, b) ((a)<(b)?(b)-(a):(a)-(b))

c++の標準ライブラリのmin, maxがクソなので使っています。
理由としてはminの片方にlong longなどをぶち込むと反応してくれません。平成アホくさ丸。
ただ、文字列とかぶち込むとC_ABSなどは実行時エラーを吐くので気をつけましょう。

   
   

コンテイナー


//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define EACH(i, c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define REVERSE(c) reverse((c).begin(), (c).end())
#define SUMI(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SUMD(obj) accumulate((obj).begin(), (obj).end(), 0.)
#define SUML(obj) accumulate((obj).begin(), (obj).end(), 0LL)
#define UB(obj, n) upper_bound((obj).begin(), (obj).end(), n)
#define LB(obj, n) lower_bound((obj).begin(), (obj).end(), n)
#define BS(v, n) binary_search(ALL(v), (n))
#define PB push_back
#define MP make_pair

   
ここらへんは他の方のテンプレートでもよく見ますね・・・小文字派の方もいらっしゃいますが・・・
大体は見ての通りマクロで、vectorなどのSTLをいじるものです。
マクロとか利用したほうが速度だけでなく、ソースコードがかなり読みやすくなりました。
使ってみると、結構欠かせないものになる気がします。
   
   

入出力



//input output
//------------------------------------------
#define GL(s) getline(cin, (s))
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define OUT(d) std::cout<<(d);
#define OUT_L(d) std::cout<<(d)<<endl;
#define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<(d);
#define EL() std::cout << "\n";
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}


入出力で使用するものです。

  • GLはgetlineの略で予め宣言してあったstring変数に一行分格納します。大体使用するときはこのあとSPRIT関数に直結ですね・・・
  • INITは入出力がガバガバに多いときは使用します。ただ、これやってギリギリセーフなときは、どこか計算量がガバガバに多い気がします。
  • OUT, OUT_Lはcoutの「<<」が面倒なので使用しています。
  • FOUTはdouble型の小数を表示するときに、指定桁をnで、表示内容をdで指定することで、○○桁に対応することができます。
  • SHOW_VECTORはvector型をぶち込むことでさらっとアサートで表示してくれます。vector型の中身をさらっと確認したいときにデバッグ用で使用してます。
       
       

REP


//repetition
//------------------------------------------
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)å
#define REP(i, n)  FOR(i,0,n)
#define RREP(i, n) for(int i = n;i >= 0;i--)
#define FORLL(i, a, b) for(LL i=LL(a);i<LL(b);++i)
#define RFORLL(i, a, b) for(LL i=LL(b)-1;i>=LL(a);--i)
#define REPLL(i, n) for(LL i=0;i<LL(n);++i)
#define RREPLL(i, n) for(LL i=LL(n)-1;i>=0;--i)
#define FOREACH(x, v) for(auto &(x) : (v))
#define FORITER(x, v) for(auto (x) = (v).begin(); (x) != (v).end(); ++(x))

これも他の方のテンプレートでもよく見かけますね・・・
大体の内容はこれで書くことができます。
ただ、indexが複雑なときは普通にforで書いたり、正直–iなどのときはRREPで合ってるのか怖いので、forで書いちゃいますね・・・
FOREACHや、FORITERは、STLなどのset,mapなど、indexが扱いづらいものに使用することが多いです。

   
   

math


//math
//--------------------------------------------

//min <= aim <= max
template<typename T>
inline bool BETWEEN(const T aim, const T min, const T max) {
    if (min <= aim && aim <= max) {
        return true;
    } else {
        return false;
    }
}


template<class T>
inline T SQR(const T x) { return x * x; }

template<class T1, class T2>
inline T1 POW(const T1 x, const T2 y) {
    if (!y)return 1;
    else if ((y & 1) == 0) {
        return SQR(POW(x, y >> 1));
    } else return POW(x, y ^ 1) * x;
}


template<typename T>
constexpr T ABS(T x) {
    static_assert(is_signed<T>::value, "ABS(): argument must be signed");
    return x < 0 ? -x : x;
}

//partial_permutation nPr 順列
//first・・最初の数
//middle・・r(取り出す数)
//last・・n(全体数)
template<class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) {
    reverse(middle, last);
    return next_permutation(first, last);
}

//combination nCr 組み合わせ
//first1・・最初の数
//last1==first2・・r(取り出す数)
//last2・・n(全体数)
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator first1, BidirectionalIterator last1, BidirectionalIterator first2,
                      BidirectionalIterator last2) {
    if ((first1 == last1) || (first2 == last2)) {
        return false;
    }
    BidirectionalIterator m1 = last1;
    BidirectionalIterator m2 = last2;
    --m2;
    while (--m1 != first1 && !(*m1 < *m2)) {
    }
    bool result = (m1 == first1) && !(*first1 < *m2);
    if (!result) {
        while (first2 != m2 && !(*m1 < *first2)) {
            ++first2;
        }
        first1 = m1;
        std::iter_swap(first1, first2);
        ++first1;
        ++first2;
    }
    if ((first1 != last1) && (first2 != last2)) {
        m1 = last1;
        m2 = first2;
        while ((m1 != first1) && (m2 != last2)) {
            std::iter_swap(--m1, m2);
            ++m2;
        }
        std::reverse(first1, m1);
        std::reverse(first1, last1);
        std::reverse(m2, last2);
        std::reverse(first2, last2);
    }
    return !result;
}

ガナリヤの情弱ポイントがバレちゃいますね・・・
数学が苦手なら予め用意していればいいだけの話だ!!!成長はしないが!

  • BETWEENはminとmaxの間にデータがあるかboolを返します。TechFULのErrorを避けるのが面倒だったので作りました。
  • SQRは二乗です。
  • POWはxをy回累乗したものを返します。こういうのはmain内にあるとコードが汚くなるのでありがたいです。標準ライブラリより、型の対応が多いためよく使用します。
  • ABSも同様の理由でよく使用します。
  • next_partial_permutationはnPrの順列をvector型などで取り出すために使用します。do while(next_permutation())の形で使用するとvector型の要素が自動で変更されていくため便利です。仕組みはよくわかりません
  • next_combinationは、標準ライブラリから落選してしまったようなので海外文献から探して使用しています。組み合わせを実現し、do whileで使用します。国内のブログなどには、利用例がないため、ちょっとまだ完璧に使い方が分かりきってはないです・・・
       
       

数学法則

   


//numeric_law
//--------------------------------------------

template<typename T>
constexpr bool ODD(T x) {
    return x % 2 != 0;
}

template<typename T>
constexpr bool EVEN(T x) {
    return x % 2 == 0;
}

//最大公約数
template<class T>
inline T GCD(const T x, const T y) {
    if (x < 0)return GCD(-x, y);
    if (y < 0)return GCD(x, -y);
    return (!y) ? x : GCD(y, x % y);
}

//最小公倍数
template<class T>
inline T LCM(const T x, const T y) {
    if (x < 0)return LCM(-x, y);
    if (y < 0)return LCM(x, -y);
    return x * (y / GCD(x, y));
}

//ax + by = 1
//x,yが変数に格納される
template<class T>
inline T EXTGCD(const T a, const T b, T &x, T &y) {
    if (a < 0) {
        T d = EXTGCD(-a, b, x, y);
        x = -x;
        return d;
    }
    if (b < 0) {
        T d = EXTGCD(a, -b, x, y);
        y = -y;
        return d;
    }
    if (!b) {
        x = 1;
        y = 0;
        return a;
    } else {
        T d = EXTGCD(b, a % b, x, y);
        T t = x;
        x = y;
        y = t - (a / b) * y;
        return d;
    }
}

//素数
template<class T>
inline bool ISPRIME(const T x) {
    if (x <= 1)return false;
    for (T i = 2; SQR(i) <= x; i++)if (x % i == 0)return false;
    return true;
}

//素数をtrueとして返す
template<class T>
VB ERATOSTHENES(const T n) {
    VB arr(n, true);
    for (int i = 2; i < SQR(n); i++) {
        if (arr[i]) {
            for (int j = 0; i * (j + 2) < n; j++) {
                arr[i * (j + 2)] = false;
            }
        }
    }
    return arr;
}

// a <= x < b の素数を返す
template<typename T>
VB ERATOSTHENES(const T a, const T b) {
    VB small = ERATOSTHENES(b);
    VB prime(b - a, true);

    for (int i = 2; (T) (SQR(i)) < b; i++) {
        if (small[i]) {
            for (T j = max(2, (a + i - 1) / i) * i; j < b; j += i) {
                prime[j - a] = false;
            }
        }
    }

    return prime;
}

//約数
template<class T>
vector<T> DIVISOR(T n) {
    vector<T> v;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) {
                v.push_back(n / i);
            }
        }
    }
    sort(v.begin(), v.end());
    return v;
}

//組み合わせ個数
template<typename T>
T NCR(T n, T r) {
    T ans = 1;
    for (T i = n; i > n - r; --i) {
        ans = ans * i;
    }
    for (T i = 1; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}

//行列
int MATRIZ_CHAIN(VI &p, VVI &s) {
    const static int INF = 1 << 20;
    const int n = p.size() - 1;
    VVI X(n, VI(n, INF));
    s.resize(n, VI(n));
    for (int i = 0; i < n; ++i) X[i][i] = 0;
    for (int w = 1; w < n; ++w)
        for (int i = 0, j; j = i + w, j < n; ++i)
            for (int k = i; k < j; ++k) {
                int f = p[i] * p[k + 1] * p[j + 1];
                if (X[i][k] + X[k + 1][j] + f < X[i][j]) {
                    X[i][j] = X[i][k] + X[k + 1][j] + f;
                    s[i][j] = k;
                }
            }
    return X[0][n - 1];
}

//最長増加部分列
VI LIS(const VI &a) {
    const static int INF = 99999999;
    const int n = a.size();
    VI A(n, INF);
    VI id(n);
    for (int i = 0; i < n; ++i) {
        id[i] = distance(A.begin(), lower_bound(A.begin(), A.end(), a[i]));
        A[id[i]] = a[i];
    }
    int m = *max_element(id.begin(), id.end());
    VI b(m + 1);
    for (int i = n - 1; i >= 0; --i)
        if (id[i] == m) b[m--] = a[i];
    return b;
}

//最長共通部分列 string->toVC
template<typename T>
vector<T> LCS(const vector<T> &a, const vector<T> &b) {
    const int n = a.size(), m = b.size();
    vector<VI> X(n + 1, VI(m + 1));
    vector<VI> Y(n + 1, VI(m + 1));
    REP(i, n) {
        REP(j, m) {
            if (a[i] == b[j]) {
                X[i + 1][j + 1] = X[i][j] + 1;
                Y[i + 1][j + 1] = 0;
            } else if (X[i + 1][j] < X[i][j + 1]) {
                X[i + 1][j + 1] = X[i][j + 1];
                Y[i + 1][j + 1] = +1;
            } else {
                X[i + 1][j + 1] = X[i + 1][j];
                Y[i + 1][j + 1] = -1;
            }
        }
    }
    vector<T> c;
    for (int i = n, j = m; i > 0 && j > 0;) {
        if (Y[i][j] > 0) --i;
        else if (Y[i][j] < 0) --j;
        else {
            c.PB(a[i - 1]);
            --i;
            --j;
        }
    }
    REVERSE(c);
    return c;
}

//コイン C総額 cs使用できるコインの種類
VI money_change(int C, VI &cs) {
    const int INF = 99999999;
    int n = cs.size();
    VI xs(C + 1, INF);
    VI ys(C + 1);
    xs[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int c = 0; c + cs[i] <= C; ++c) {
            if (xs] > xs + 1) {
                xs] = xs + 1;
                ys] = c;
            }
        }
    }
    VI zs;
    for (int c = C; c > 0; c = ys) {
        zs.push_back(c - ys);
    }
    return zs;
}


   
長すぎぃ!
でも合ったほうが便利だからええやろ(甘え)

  • ODDは奇数かどうか判定します。inlineをつけてないのでつけようかと思います。
  • GCDは引数x, yの最大公約数を算出します。ユークリッドの互除法をしています。
  • LCMは最小公倍数を算出します。ab = GCD(a,b)*LCM(a,b)という法則があるため、GCDで算出した答えを利用してLCMを算出します。
  • EXTGCDはax+by=1となるx,yが格納されます。仕組みがまだ良くわかってないです。
  • ISPRIMEは引数が素数かどうか判定します。一つの数字のみでいいならこちらを使います。
  • ERATOSTHENESは素数のふるいを行います。配列に格納しておいて、素数を見つけるとSQR(n)分まで回すことで素数以外をfalseにすることで早く計算できます。
  • DIVISORは約数を算出してvectorにして返します。n*nのsqrt以内に半分の素数は存在するため、そちらで算出し、i!=n/iで反対側の素数を算出しています。
  • NCRはnCrの意味で組み合わせを算出します。ただいま、先にかけ算を行っており、数がおおきいとオーバーフローしてしまうため、改善が必要かもしれませんね。
  • LISは部分増加列を算出します。ここらへんはよく出るので、どんな仕組みだったからって確認するために記述させていただいてます。
  • LCSは二つの文字列の部分増加列です。もはや辞書的な役割です。
       
       

confirmation

   


//confirmation
//--------------------------------------------

//clear memory
#define CLR(a, b) memset((a), (b),sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


   
メモリーの初期化(配列に限る)や、デバッグで使用するマクロです。
fillをまだマクロで定義してないのでfillも実装しとこうと思います。

   
   
   
  


あ〜すっげぇキツかったぞ〜
自分が以下にライブラリに頼っているかがバレましたね・・・(バレてるんだよなぁ・・・)
マクロを使うと結構楽に、はやく書けますし、よくわからん数学の部分をオーバーラップできます。
自分なりのテンプレートを作って競プロやると、結構楽しいかもしれません。
僕は、結構使えそうなマクロ作ったり探したりする時間が、競プロの中で一番好きです。(こんな人間になってはいけない)

P.S.

かえみと尊い・・・尊くない・・・?