diverta 2019 Programming Contest A~E

コンテストに遅刻したので戒めに解きました。

問題文 Tasks - diverta 2019 Programming Contest

A

N-K+1を出力すればいいです.

B

問題

整数R,G,B,Nが与えられたとき, 以下を満たす(r,g,b)の組はいくつあるか?

R r + G g + B b = N

ただし, R,G,B,Nはそれぞれ1以上3000以下.

解法

rとgが決まると上式よりbが一意に定まる.

このことから, rとgに関して二重forを回すとO(N2)となって間に合う.

C

問題

2文字以上10文字以下の文字列がN個与えられます.

全ての文字列を任意の順番で結合し, 1つの文字列を作ろうとしたとき, 'AB'という部分文字列は最大で何個含まれますか?

解法

与えられる文字列の, 最初の文字と最後の文字のみに着目して, 4つのパターンに分類すると, 貪欲法により解くことが出来ます.

具体的には, 以下のように定めるとうまくいきます.

  • B~A
  • x~A
  • B~x
  • それ以外

この場合分けでうまくいく理屈は, 紙で実験しないと理解し辛いのですが, 以下のように説明できます.

2つの文字列を結合した際に'AB'の数を増やすためには, 1つ目の文字列の最後が'A'で 2つ目の文字列の最初が'B'である必要があります.

そして, それ以外の条件の時で, 'AB'の数が増えることは無いです.

そのため, 最後が'A', 最初が'B'であるパターンを列挙すると答えに寄与するすべての場合を列挙したことになります.

この場合分けが出来れば, 以下の貪欲法で結合することでACがもらえます.

  int ans; //自明な'AB'を既に数え上げているとする
    if(ba != 0){//「B~A」が存在するとき
        ans += (ba-1);//「B~A」は置けるだけ置く
        if(bx!=0){ //その後ろに「B~x」を繋ぐ
            ans++;
            bx--;
        }
        if(xa!=0){//手前に「x~A」を繋ぐ
            ans++;
            xa--;
        }
    }
    ans += min(xa,bx);//好きな位置に「x~AB~x」を置けるだけ置く
    cout << ans << endl;

4つのパターンの優先順位を考えた時, 「B~A」は優先的につないだ方が良さそうなので, 繋ぎます.

このとき, 「B~A」の後ろに「B~x」をつなぐとスコアが1稼げるので, 繋ぎます.

また, 「B~A」の手前に「x~A」をつないでもスコアが1稼げるので, 繋ぎます.

あとは好きな位置に「x~A」と「B~x」を繋いだ文字列を設置します.

以上です.

D

問題

正の整数Nが与えられます.

Nについて以下の条件を満たす全ての正の整数mの総和を求めてください

  • Nをmで割った商とあまりが等しい

解法

N=8の時を実験してみましょう.

商が1の時, 2の時, 3の時を考えると, mに関して以下の方程式が成り立つことが分かります.

  • m_1 \cdot 1 + 1 = 8
  • m_2 \cdot 2 + 2 = 8
  • m_3 \cdot 3 + 3 = 8

以上の観察から, 商がxの時, Nとmに関して以下の方程式が成り立ちます.

  • m_x \cdot x + x = N

上式をmについて解くと, 以下を得ます.

  • m_x = \frac{N}{x} - 1

この結果から, mが整数となるためには, xがNの約数でないといけないことが分かります.

Nの約数列挙はO(\sqrt{N})で出来るので, すべての約数の列挙が時間内に可能です.

E

問題

E - XOR Partitioning

解法

考察1

与えられた数列に対してi番目の要素まで累積XOR和を取ったときの値を, b_iとして定義します.

ここで, b_nがある値Xを取ったとすると, 最適に分割された数列のXOR和はX, 0, X, 0, ... , 0,  Xとなっています.

(そうでないと, 全ての要素のXORの値がXになりません!) (入力例2で試すと良いと思います)

よって, b_iについて, Xを決めたときX, 0, X, 0, ... , 0,  Xと交互に取るような方法が何通りあるか求めれば良いです.

これはDPを使うとO(N)で解けます.

考察2

一方, b_nが0の場合では, Xの決め方が最大でn通りもあるため, 先ほどのDPを適用するとO(n2)となってしまい, うまくいきません.

そこで, Xを決め打った時, 最大でどれだけ高速に計算が行えるか考えます.

今, 以下のようなn=25の数列に対する累積和列bが存在するとします(これは入力例4です).

  • 1 3 6 5 6 0 1 0 8 0 0 3 0 4 2 4 0 0 7 5 0 4 2 0

X=4と決め打って実験していきます.

まず, bに現れる4と0以外の要素には興味が無いため, 除去します.

  • 0 0 0 0 0 4 4 0 0 0 4 0

また, 4や0が連続する部分はDPで計算を省略できるので, 圧縮します.

  • (0,5) (4,2) (0,3) (4,1) (0,1)

以上の操作により, 5要素に圧縮することが出来ました.

また, このような圧縮を行った時の要素数は, b中のXの出現数に依存します.

よって, この5要素に対して先ほどのDPを適用するとXを決め打ったとき, O(b中のXの出現数)で計算が可能です.

さらに, 先ほど示した圧縮は0が出現する位置についての累積和を用いると, 同様にO(b中のXの出現数)で計算が可能です.

あとはXを全ての場合について計算してやると,

  • O(b中のX_1の出現数 + b中のX_2の出現数 + ... ) = O(N)

となり, 解けます.

大学編入して1年経ったので、近況報告とか、就活の話とか

突然ですが、大学に入学してから1年が経ちました('ω')

軽く自己紹介をしておくと、 私は高専編入試験を受験、そして大学に3年次編入した、編入生ってやつです。

なので、今は4年生が始まって1か月経った状態。

1年も経っていろんな経験(良いこと、悪いこと)があったので、今回はその話をしていきます。

(特に、このブログは高専生がよく読んでくれているので、知見共有できたらいいな)

編入から3か月ぐらい

夢と希望にあふれていました。

レベルの高い同期に囲まれて、大学特有の(アナログな)仕様に振り回されながらも、一番楽しい時期です。

「某e-learningシステム」開発のアルバイトを見つけて、フロントとバックエンドを触り始めました。

つまりプログラミングのアルバイトを始めたって訳ですね。
(大学の求人にはこの手のアルバイトがごまんとある。)

私は輪に入れる自信もなくて、サークルには入らなかったんですけど、無理やりにでも入っておくべきだと思います。

編入から半年ぐらい

少ないながらも内部生(編入生でない学生)の友達が何人か出来ました。

話を聞いてみると、どうやら実験以外の授業はほとんど出席していない様子。

私の通う大学はバッチリ工学系なので、遊んでいても進級出来るなんて、と半信半疑でしたが、どうやら可能らしい。

しかも、このように過ごす3年生は非常に多いとのこと。

調べてみると、内部生は1年生と2年生の間に頑張って単位を取ると、3年の時間割がスカスカになる仕様のようだ。

入学当初モチベーションの高い内部生は例にもれず1,2年生で粗方の単位を取っているので、3年生はあたかもボーナスステージであるかのような空気が漂ってしまっているのである。

3年生がこのようになってしまう要因は色々あると思う、けど大部分は上記した内容。

編入生は、入学直後のモチベーションが最も高いので、これは致命的。

大学に「意識高い何か」を求めて編入する場合は、この内部生と編入生のモチベーションのギャップには特に注意する必要があります。
(人によっては、モチベーションが際限なく落ちていく)


前期が終了し、初めての成績開示があります。

この時の成績が研究室の配属に重要な指標になるので、頑張っておくと良いと思います。

私はこのあとすぐ堕落していくので後期は散々でしたが、前期の成績が良かったので第一志望の研究室に行けました。
(これは本当に良かったことで、1個か2個上の代には希望の研究室に行けていない先輩が何人かいた。)

編入生の研究室選びは確実に人生を左右するので慎重に!

始まる就活

研究室の配属も落ち着いた11月頃、突然就活が始まりました。

きっかけは夏休みにふと思い立って参加したハッカソン「JPHacks」、そこで企業から声がかかって、という流れでした。
(ハッカソンとは、短期間で集中的にプロダクトを開発してその出来を競うコンテスト)

その企業の会社見学をするついでに、ちょっと早いけど就活を始めてしまおうと思ったわけです。

ちなみに、編入生の就活事情どんな感じなのーと気になったら、某なっさまのブログを読むと早いです。

marin72.hatenablog.com

そういうわけで色々な企業を見学して、逆求人イベントに出てみたりなんかして就活を進め、なんとか3月で内定にこぎつけました。

特に逆求人イベントは、ある程度知名度のある企業のエンジニアや人事と直接話せるので、自分が描いている理想と現実とのギャップを埋めるのに最適です。

逆求人イベントの実際の様子が気になる方は、私の相方mahitoの体験記を読んでみてください。

mahito6.hatenadiary.com

始まる就活、本当の地獄編

就活中一番大変だったことは、授業への出席です。

私の通っている某UEC固有の問題だと良いのですが、「会社見学や面接を理由に公欠が取得できない問題」について話します。

高専と違って、ここでは就活で公欠を取得できないんです。

これが本当に辛い。

正式な公欠を取得できないということは、授業をサボる必要が出てきます。

真面目に大学に通おう!と思っても、就活を頑張れば頑張るほど、不可避のサボりが発生します。

それでも、単位は基本的に落とすことが無いんですよね、大学は優しいので。

その結果、サボり癖があっという間につく。単位も落とさないし。

就活が終わった後に出来上がるのは、サボり癖がしっかりとしみついた人間。

しみついた癖はどうしようもないので、日々の生活を改善するための努力(ランニングとか、早起きとか)を就活が終わった後にやっています…。

編入生の就活で大事なことは、頑張ってはいけないということ。頑張るなら、短期間で決着をつけると良いのだろう。

難しいことではありますが、大学生活と就活の両立は特に注意してください。
(就活は基本的に長期戦なので!)

今後のこと

研究が始まるので、まずは卒業できるように成果を出す。

そして、今すごく尊敬している人がいるので、その人を見習って貯金すること。

一時期はやめようかとも思っていたけど、趣味の競技プログラミング音ゲーを改めて頑張って行こうかなと思ってます。

目標はatcoder青を目指す!音ゲーポップンミュージック50クリアを目指す!1年以内に!

高専プロコン28競技部門 都立(品川)

第28回高専プロコン(コレ)の競技部門に都立産技高専(品川)から参加しました!
これで高専プロコンの参加は4回目になります。過去の体験記(第26回)はこちらです。
hokekyo1210.hatenablog.jp

結果

今年の結果は優勝でした!
全試合で単独満点を達成することが出来たのは本当に嬉しかったです。
さらに、本校は3年連続で賞を受賞しています(競技部門としては初らしい)。
開発メンバーは以下の4人です。

  • はたの (1年)
  • @w_yasu_w0809 (3年)
  • @Mahito6 (5年)
  • @_hokekyo1210 (5年)

そもそも高専プロコン

全国で55校ほどある高等専門学校(いわゆる高専)から、それぞれ1チームずつが参加するプログラミングの大会です。
高専プロコンは3つの部門に分かれていますが、今回受賞した競技部門は、特定の問題に対する解答用プログラムを事前に用意して、大会当日に競わせる競技形式の大会です。
競技部門を簡単にまとめると以下のようになります。

  • 準備期間は半年
  • チームでの開発が可能
  • 厳密解を求められない問題が多い
  • ハードウェアを工夫しなければいけない問題が多い

今年の問題

今年の競技部門は、バラバラに切断された「木製のピース」と「ピースがぴったりハマる枠」が与えられて、そのパズルを好きな方法で解けという問題でした。

実はこれ、問題の概要は去年とまったく変更されていません(細かい部分は変更されています)。2年連続でまったく似た問題が出題されるのは、過去の高専プロコンには無かったと思います。
このようになってしまった理由は様々な場所で議論されている気がするので、改めて言及はしません。気になる人はぜひ調べてみましょう。
今年の問題の特徴は以下のようになります。

  • パズルが完成しない場合、得点は0点
  • ピースの個数は最大で50個
  • ピースおよび枠の頂点は必ず格子状の点に乗る(つまり整数座標のみでパズルを表現できる)
  • パズルの枠はA4のスキャナに収まる
  • 試合中にはコンセントが使用できる
  • 持ち込むPCの台数に制限はない
  • 減点されるがピースおよび枠の形状情報をヒントとして得ることも出来る

基本方針

今年のパズルは、数十分程度では人力で解くことが出来ないよう工夫されており、プログラムの介入は必要不可欠でした
基本的には、ピースと枠をどうにかしてプログラムが理解できるデータとして表現する必要があります。これには2種類の方法があり、「減点覚悟でヒントを用いる」もしくは「スキャナやカメラを用いてピースと枠の頂点情報を抽出する」となります。前者はQRコードを入力する機構を用意すれば良いだけなのに対して、後者は適切な画像処理を組む必要があるなど、難易度が高いということが言えます。
僕らのチームは、「ヒントを用いないチームはいても2,3チーム程度だろう」という希望的観測と、「前回大会の画像処理ノウハウを用いれば、他チームを上回る精度は出せるだろう」という自信から後者を選択しました。

最終的な方針は以下のようになりました。

  1. A4スキャナを用いてピースと枠をスキャン
  2. 画像処理を用いてデータ化
  3. ビームサーチと呼ばれる探索アルゴリズムでパズルを解く
  4. ソフトウェアのアシスト付きで、2人がかりでピースを埋める

ピースや枠の画像処理は必ずしも正しいデータを求められる保証が無かったため、いくつか誤ったピースがあってもそれっぽい解を出せる探索アルゴリズムとして、ビームサーチを選択しました。決勝の問題などでも、誤って検出したピースがいくつかあったため、この選択は正しかったと思います。

やったことの細かい解説

それぞれでやったことの細かい解説は以下のスライドをじっくりお読みください(80ページ近くあります)。

4年間の総評

競技部門めっちゃ楽しかったです!これからはOBとして大会にちょっかい出すと思います。競技勢がこれを読んでモチベーション上げてくれたら嬉しいなあ。

平成30年度 電気通信大学Ⅰ類 編入学試験

6/22,23にH30電気通信大学Ⅰ類編入学試験を受験しました。 試験の記録だけメモ程度に残します。

受かってました、今年のⅠ類の倍率は4.2倍でした。(7/8追記)

筆記試験

数学 120点/120分

電通大の数学は大抵、線形代数2問、微積に関する問題1問、重積分1問、複素解析1問の計5問構成になっています。
他大学に比べるとひたすらに計算が重いので、問題集で典型を覚えた後は、過去問を周回して重積分や掃き出し法の精度を上げていくことが点数を安定させる一番の近道だと思いました。

1. 写像

3*1の列ベクトルが3つ与えられます。(1)で一次結合を求め、(2)(3)では写像,像,核すべてを求める電通大の好きそうな問題でした。
この問題は3*3の逆行列、行列の積、行基本変形を順番に計算しなければならず、計算難度だけで言えば過去問と比較しても最高難度だったと思います。
(1)はよく分からずu = c1*v1 + c2*v2 + c3*v3とか書いて放置していて、終わってから参考書を見るとどうやら典型問題らしく、知識の浅さを思い知りました。
点数: 20/30

2. 固有値,固有ベクトル

(1)(2)は3*3行列の固有値固有ベクトルをそれぞれ求めるだけの問題で、(3)は少し頭をひねる必要のある問題。
(3)は固有値が重解を持ち自明な対角化は使えない問題だったので、ちゃんと固有値固有ベクトルの定義と、それらを用いた対角化の導出方法を知っているか見たかったのだと思います。ぼくは(3)どころか(2)の行基本変形を計算ミスするというどうしようもない感じでした。
点数: 15/30

3. 2変数関数の極値

(1)偏導関数 (2)停留点 (3)極値
選択しませんでした。(2)(3)の難易度は高いと思います。
噂ではこの問題とほぼ同じ問題が東工大の過去問に出ていたと聞いたので、東工大に向けて対策をしていた受験者はガッツポーズでしょう。

4. 重積分

(1)二重積分 (2)三重積分
例年通りの問題でした。(1)(2)共に変数変換を行う必要があり、積分範囲が少々複雑ですが、過去問でしっかり対策していた受験者は問題無く解けたはずです。
(1)の計算過程でx^2/(1+x^2)の積分が必要になるため、計算方法を知っているかどうかでかなり難易度が変わったと思います。
点数: 30/30

5. 複素解析

(1)極値 (2)留数 (3)複素積分を用いた複雑な実積分の計算
これも例年通りの出題でした。過去問をしっかり対策していれば確実に解ける問題です。
点数: 30/30

合計 95/120
計算ミスで5点落とした事が悔やまれますが、実力は出し切れたと思います。
例年の難易度と比較すると全体的に易化気味であることは間違いないので、合格者の平均点は100点近くありそうです。

物理 90点/90分

電通大の物理は力学、電磁気学、熱力学の計3問構成になっています。10年ほど前には波動の出題もあったそうですが、最近ではまったく出る気配は無いです。
全体的な難易度は年により大きく変動しますが、基本的には 力学>熱力学>電磁気学 といった難しさになっています。
特に、電磁気学は参考書に例題として載っているような問題がそのまま出題されることがほとんどで、しっかりと基本的な参考書の例題を押えておけば爆死は避けられます。それに比べて力学と熱力学(特に力学)は凝った問題が多く、完答出来るかどうかは(僕の場合)かなり運に左右されます。とにかくヤマを張りました。

1.力学

一端を固定された剛体棒に質点をぶつける問題でした。この問題は丁度サイエンス社の力学演習に類題が載っていた事もあり、ヤマを張っていたので爆死は避けられました。
系の運動エネルギーを求められず死亡。
点数: 15/30

2.電磁気学

(1)~(3)は円筒の外部に発生する電場と電位、(4)~(6)では円筒を2本に増やした場合の静電容量を求める問題でした。
誘導がかなり丁寧で、出題者の優しさを感じました。(6)は知っていれば簡単、知らなければ少し難しかったのではないかと思います。2本の円筒間の静電容量をなぜかノートにメモしていたのであっさり答えられました。
点数: 30/30

3.熱力学

大雑把に、定圧熱容量と定積熱容量が温度Tの関数である場合のディーゼルサイクルの熱効率を求める問題でした。(1)と(3)でサイクルが吸収した熱量と放出した熱量を求める必要があるのですが、それぞれ定圧変化、定積変化であることに気付いてしまえばあとは熱容量の定義式通りに積分を実行するとあっさり解けたと思います。
この問題は(1)が解けるかどうかで手ごたえが大きく変わったのでは無いかなあ、と思います。
点数 30/30

合計 75/90
力学と電磁気学はヤマを張っていたところからの出題だったのでラッキーでした。
力学は去年に引き続き剛体からの出題で、さらに言うと運動方程式を一切解く必要が無いという珍しい出題でした。力学はH29から傾向が変化したと見て良いと思います。

英語 90点/90分

長文1問、作文1問の計2問構成になっています。電通大の英語はなぜか年々易化が進んでおり、今年は長文が1.5ページ程度しか無かったので時間を余らせたという人がほとんどだったはずです。しっかりと見直しをしましょう(戒め)。

1.長文

自動清掃窓?に関する長文を利点、弱点それぞれ2つずつ挙げて要約する問題でした。文中に「advantage」,「disadvantage」とデカデカと書いてあったり、とにかく分かりやすい長文でした。
手ごたえ 35/50

2.作文

2020東京オリンピックは日本にとって有益か?という質問に自分なりの理由を2つ以上挙げて答える英作文と、ソーラーシステムに関する英作文のうちどちらかを選択する問題で、オリンピックを選択しました。
文法の間違いに気を付けつつ、練習通り淡々と作文しました。
手ごたえ 30/40

全体の手ごたえ 65/90
はっきり言ってボロボロだったと思います。長文はthicknessという単語を厚さでなく濃さと訳したりなど、見直したらすぐに分かるようなミスを積み重ねました。厳しく採点されればもっと低い点かもしれません。

口頭試問

電通大の口頭試問は科によってあったり無かったりするという情報もあるため、ほとんどの受験者が専用の対策は特にせずに臨むものと考えられます。今年度はⅠ類だけ口頭試問が実施されたようです。
口頭試問の試験時間は10分程度で大問が2つ、それぞれ5分ずつという感じでした。
試験部屋に入ると即座にタイマーがスタートし、「じゃあそれ解いて」と言われホワイトボードに貼ってある紙に誘導されます。

1.進数変換

(1)8進、16進→2進
(2)16進→9進
(3)見てない
(1)はやるだけの問題だったのに、テンパって一度10進数に変換してから2進数に変換したりなどガバガバでした。ぼくは(1)を解くのが遅く、(2)は解けずに終わりました。
手ごたえ 1/3

2.線形探索の計算回数

線形探索のフローチャートが書いてあり、それぞれ「①ループのカウント変数を比較する部分、②一致しているか比較する部分、③カウント変数のインクリメント」と番号が振ってありました。
(1){0, 1, 2}の配列から2を線形に探索するときの①、②、③の実行回数
(2){0, 1, 2}の配列から線形に探索するときの①、②、③の最悪実行回数
(3){0, 1, ..., n-1}の配列から線形に探索するときのn=2,3,4それぞれの①、②、③の平均実行回数
(4){0, 1, ..., n-1}の配列から線形に探索するときの①、②、③の平均実行回数
この手の問題が得意だったのもあり、完答出来ました。(3)の平均実行回数という言葉に聞き覚えが無いと、完答は難しい問題だったと思います。
手ごたえ 4/4

全体の手ごたえ 7割


まとめ

科目 手ごたえ
数学 95/120
物理 75/90
英語 65/90
3科目合計 235/300
口頭試問 7割

3科目の合計は大体220~240ぐらいだと思います。
受験自体はまだ終わっていないので、引き続き気合を入れ直し頑張っていきたいと思います。

同人誌を管理するツール作った

最近アクセスが増えているので記事を再編集しました。(2018/04)

同人誌の蔵書管理に役立つツールを作成しました。
タイトル、サークル名、著者、発行日、タグなどを指定して登録できます(ウェブ検索を利用した補完機能もあります)。

f:id:hokekyo1210:20160529130741p:plain:w600
f:id:hokekyo1210:20160529131033p:plain:w600

できること

  • 同人誌のデータベース化、閲覧
  • データベースの検索
  • タグ付け
  • etc

ダウンロード

実行にはJRE7(つまりJava7)以上のインストールが必須です!!!
通常のexe実行ファイルのようにダブルクリックなどで起動します。

  • ダウンロードURL

https://drive.google.com/file/d/1Sbb7mRPgmHS8_NW8usay7RThvJ4ZB9vO/view?usp=sharing
※補完機能が作動しない不具合を修正しました。(2018/04)

機能

作品の追加

f:id:hokekyo1210:20160529131802p:plain:w400
・画像はドラッグ&ドロップで追加できます。
・タイトル部にキーワードを入力し、Enterキーを押すと、
Web上より関連する作品を探して画像、タイトル、サークル名、著者、発行日を補完します。(※この機能を使わないといちいち打ち込むことになるのでめっちゃ大変です!!)
・同一作品の重複登録は行われないようになっています。

検索機能

・キーワードに当てはまる作品をデータベースから検索し、全てリスト表示
・発行日から検索することも可能(例:「2014」→2014年発行の作品を全表示)

ツリー表示

f:id:hokekyo1210:20160529132456p:plain:w240
・サムネイル表示
・サークルは辞書順にソート
・作品は発行日降順にソート

ブラウジング(リスト表示)

f:id:hokekyo1210:20160529133216p:plain:w400
・サムネイル画像にマウスを重ねると拡大表示
・作品は発行日降順にソート

グラフ表示

f:id:hokekyo1210:20160529134040p:plain:w500
・作品の発行日と、その作品数から棒グラフを作成

技術的な話

データベースは"user/temp/"ディレクトリに作成されます。バックアップなどの必要が生じた場合はこのディレクトリをそのままコピーしてください。

github.com
アイディア、バグ報告等あれば@_hokekyo1210までお願いします。