NSTomoS’s blog

NSTomoSの情報系の記録用ブログです.

CODE FESTIVAL 2016参加記

r.recruit-jinji.jp

CODE FESTIVAL 2016参加記

今回はCODE FESTIVAL 2016に参加させて頂いたのでその参加記です.

僕は二年前競技プログラミングを始めたての頃にCODE FESTIVAL 2014に参加して,去年CODE FESTIVAL 2015は惜しくも予選落ちしCODE THANKS FSTIVAL2015に参加しましたが,今年はなんとか最後の予選で通って本戦に参加できました.

一日目

本戦

本戦の配点を見た時点で「3完すれば万々歳で,パーカー(1600点)は夢のまた夢だなぁ」と思っていましたが,びっくりするほど調子が良く最終的にABCD満点E部分点の4.5完2000点で100位ぴったりと大健闘してパーカー貰えました.

以下ざっくりとした解説です(オーダーはテキトーなので自信ないです…)

A問題(100点)

入力を受け取って O(HW)で愚直に実装するだけで通る.

B問題

配点の最大値の最小値は N 1,2,3,4,5,6,7,8,9,10…と増えると 1,2,2,3,3,3,4,4,4,4…と増える(頭悪いから手で試して求めた)ので, O(N)で求まる.配点の最大値の最小値さえ求まれば,あとは配点の最大値の最小値以下の数を大きい順に和がちょうど Nになるように貪欲に求めていけば求めたい集合が求まる.

C問題

言語でUnion Findを使って,各人の使える全ての言語を同じ集合にする( O(MKlog(M))).使われていない言語がない保証があれば集合の個数がMであれば”YES”を出力で良いのだが,そうではないので,ある一人と他の人のそれぞれ最初の言語が求めたUnion Findで同じ集合内にあるかを確認すれば通る( O(Mlog(M))).

D問題

それぞれの数の枚数,それぞれの数のペアの数,それぞれの数のペアになれなかった枚数, mod(M)を取った数のペアの数, mod(M)を取った数のペアになれなかった枚数,を管理して,先に足してMになるペアを組んで,それに応じて同じ数のペアを減らし,最終的に数え上げるゴリ押し解法で通った.

なんとここまでをノーミスノートラブルで1時間で解き切った

E問題

最初自明なDP解法を思いつくも部分点でもTLEすると思い,時間を前から追って最終的に時間短縮になるなら貪欲にクッキーを食べる手法を実装するが,10ほどWAを出して1時間以上を溶かした…諦めて自明なDPを駄目元で試したら部分点解法が通った…

E問題の部分点を取った段階で残り30分だったのでそれ以上は解けませんでした…

1日目のその後

体力測定で体力のNASAを実感しました…

同じ大学の先輩方とボードゲームに勤しんで(殺伐とした殴り合いをして),エキシビジョンマッチを観戦しました.

余談ですが去年一昨年よりもホテルが綺麗な所だったんですがもしかして今年は全体的に予算が増えたとか?

二日目

トーナメント戦

なんとトーナメント戦で普段負けまくっててたまたま前日の本戦で勝ってしまった同じ大学の強い先輩と最初から同じグループになりましたw結局Round1では1位で勝ち抜けましたが,Round2で完敗しそこで敗退しました…

Round1A問題

Union Findでコストの小さい辺から貪欲に繋いでいくと200 点の部分点解法だった.

Round1B問題

自明な100点の部分点解法を通した.

Round2A問題

200 点の部分点解法が自明である事に気付くのに遅れて時間がかかった…

Round2B問題

愚直に貪欲に魔法を使ったら200 点の部分点解法だと思ったがWAで時間切れして最下位になった…

Round3A問題

DPで通ると思ったが通らなかった.(多分実装がザルだったのと考察がだいぶテキトーだったのでDPでもきちんとやれば通りそう?)

Round3B問題

A問題をのんびり考えてたので目を通してすらいない…

空き時間

いくらのお弁当美味しかったです. ボードゲームは昨日の殺伐とした殺し合いとは逆にプレイヤーが必死に協力するゲームで楽しんで,クレーンゲームでは一番欲しかった手拭いを手に入れました.

リレー

Aチームでまた同じ大学の先輩と同じでしたww

変に本戦で順位が高かったためにG問題を担当しましたが,結局自力で解法が分からず強い人(DEGwerさん)に教えてもらって実装しただけで終わりました…結局チームは最下位で何も役に立てなくて申し訳なかったです…

G問題(教えてもらった解法)

最初から玉の入ってるコップの位置を管理しながら,コップに玉が入ってるかどうかの情報をクエリの通りswapしつつ,最初から玉の入ってるコップの左右にも玉が入ってるように更新すると,最終的に玉の入ってるコップを数え上げる事ができる.

感想

ボードゲームや様々な方のトーク,交流などがありとても楽しいイベントだった. また,code festivalの問題は典型アルゴリズムの適用よりも解法を考える事が重視される問題が多く???,僕でも解けるような問題(それでいて簡単には解けない)が他のコンテストよりも多いのも良いと思った.まだあと二年は参加出来るので,来年再来年も予選通過してぜひ参加したいし,知り合いにも是非勧めたいと思った.(このエントリー見た人競技プログラミング始めましょうw)

(よくある感想的なのしか言えませんが本当にとても楽しいです…)

今回はリクルートさん本当にありがとうございました. また

その後

せっかく東京に来たので,駅メモの君の名は東京イベントを消化して今は宿です. 明日は下宿探しの下見(各地域の雰囲気とかを見にぶらぶら)する予定です.

院試終わりました

春先に「院試受けるぞい」と言っていて,その結果が出たので報告のエントリーです.

院試結果

結論から言うと第一志望の大学,研究室に受かりました.
Twitterで散々「院死」って呟いてなんだよって感じです.
なので,来春から東京工業大学ソフトウェア工学の研究室に所属することになりました.

www.titech.ac.jp

院試まとめ

これだけだとちょっと記事的に寂しいので,一応参考までに滑り止めの工繊と,本命の東工大の院試の感想を書いておきます.

工繊

工繊は筆記のみでした.
内容はTOEICと数学とプログラミング(配点は1:1:2)です.
数学は線形微積統計が各一問.
ボクは微積苦手マンなので,微積白紙,線形統計完答でした.
プログラミングはjavaとcの基礎問題集という感じでした.
例年よりも少しひねった問題が出てましたが,それでもだいぶ初歩的な内容しか出なかったので,試験時間2時間の半分で退出しました.
もっと楽しい問題出せよ.

東工大筆記

東工大は筆記と面接の二段階選考のB日程でした.
(ボクは成績が良くなかったのでB日程でしたが,出身校の成績が優秀なら面接で一発OKのA日程になるそうです.)
筆記の内容はTOEICと専門(数学含む)(配点は不明)です.

今年の筆記試験は以下の内容でした.

数学はさすが東工大と言った難易度で,ボクは半分くらいしか解けませんでしたが,専門の問題は過去問よりもだいぶ簡単で,完答できました.
むしろ簡単すぎて自分が得意な分野で稼げないのが怖いくらいでした.

東工大面接

で,筆記の成績が良かったらしく,面接に行きました.
ただ,面接で聞かれたのが,配属研究室の意思確認だけだったので, ボクは「はい」を二回言っただけでしたw
「第一志望に書いてるんだから『はい』って答えるの当たり前なんだしんなことのために東京まで呼び出すなよww」って思ったことは内緒
ちなみに,5番目くらいとだいぶ早めに呼ばれたので,筆記の成績が良かったのかも知れません.(希望的観測)

総括

運が良く自分が得意な分野ばかりが出たので得点が出せた感じです.
少し分野や違ったり難易度が上がっていたら落ちていたかも知れない感が拭えません…

オタク活動

「どうせ東京にいくなら遊ばねば」ということで,遊んできました.
筆記試験の時はシネマシティ立川で3回目のガルパン極上爆音を楽しみ,
面接の時はガルパン疎開(?)先の小学校(旧上岡小学校)に聖地巡礼&東北新幹線北陸新幹線乗り鉄の旅をしてきました.

これから

研究とプロコンに重点を置きたいです(真顔)
(院試終わってから戦車乗ってるだけなんて言えない…)

c++で競プロ入門(3)

今回はABC040のD問題を解いていきます.

D問題 道路の老朽化対策について

abc040.contest.atcoder.jp

部分点とは

難しい問題には部分点が与えられる場合があります.
問題の制約条件よりもゆるい制約条件が与えられ,その条件下で成果した場合点数の一部が得られます.
部分点の解法は元の問題の解法(満点解法)よりも簡単なので,満点解法が思いつかない場合はあきらめて部分点解法を取りに行くのも戦略です.
(実際に,満点解法を思いつけると思って挑んだものの解けず,「最初から部分点解法を解いておけば順位が上がったのに…」なんてことも多々あります.)

今回のD問題の場合,問題の制約は1≦N≦100,000 0≦M≦200,000 1≦Q≦100,000,ですが,1≦N≦1,000 0≦M≦2,000 1≦Q≦1,000,の制約のテストケースを全てACできれば部分点が与えられます.
今回はまず部分点解法で解いていきます.

キュー

後述する幅優先探索ではキューというデータ構造が必要になります.
キューは待ち行列のことで,データを行列の最後に追加(push)して先頭から取り出すこと(front,pop)がそれぞれ{O(1)}でできるデータ構造です.

c++ではqueueというコンテナで実装されており,push()で最後にデータを追加,front()で先頭のデータを参照,pop()で先頭のデータを削除できます.

幅優先探索

今回の問題は都市とその間の道路についての問題です.
このような問題は都市を頂点,道路を辺としたグラフの問題として解くことができます.

今回の問題ではグラフを探索する必要がありますが,その手法の一つに幅優先探索探索があります.
これはグラフを出発地点から均等に掘り下げていく手法です.

アルゴリズムは前述のキューを用います.

  1. 空のキューと頂点の探索済みか否かのチェックリストを用意する.
  2. スタート地点の頂点をキューに追加する.
  3. キューが空でない間以下の操作を行う
  4. キューから頂点を取り出す
  5. 取り出した頂点に接続している頂点が探索済みでないならば,探索済みにしてキューに追加する.

幅優先探索の時間計算量は,最悪の場合全ての頂点と全ての辺を参照するので{O(|V|+|E|)}となります.
({|V|}はグラフの頂点数,{|E|}はグラフの辺数)

ちなみに,これを最後に追加したものを最初に取り出すデータ構造のスタックを用いると深さ優先探索となります.
これはどんどん探索を掘り下げていって探索できなかったら最後に見た枝分かれまで戻ることを繰り返す探索手法です.

ペアpair

今回の実装で使うpairを解説しておきます.
これは二要素の構造体のようなもので,競技プログラミングではしばしば用います.
pairの生成にはmake_pairを使います.
一つ目の要素をfirst,二つ目の要素をsecondで参照できます.
要素としてpairを取って入れ子にすることも出来ます.
優先順位を宣言しなくても一つ目の要素の型の優先順位を用いてくれるため,非常に便利な場面が多いです.

部分点解法

部分点解法は愚直な解法を考えてみましょう.
各クエリで与えられる出発地点から出発して,各クエリで与えられる年よりも後に作られた道だけを使っていける都市の数を数えればいいことになります.

この都市の数え上げには幅優先探索を用います.
キューへの追加時に,クエリで与えられる年よりも後に作られている道のみをキューに追加します.
また,チェックリストで探索済みにした回数を数えることで,行くことが出来る都市の数を数えます.
(これは探索後にチェックリストを数えることでも可能です.)

ソースコードは以下のようになります

gist5bd72c385abfbdd983bd458745d0d243

edgeは都市iから伸びるj番目の道路が都市edge[i][j].firstにつながっており,edge[i][j].second年に造られたことを示します.

これで部分点50点が得られました.

しかし,この実装は{O(Q\times (N+M))}なので,問題の制約条件下ではTLEとなります.

満点解法の方針

満点解法は方針を変えなければ解けません.

道路とクエリをそれぞれ造られた年({y_j})と使用する条件の年({w_j})の新しいものから考えると,道路によって最初はばらばらだった町を繋げていきながら,クエリを処理できそうだと気づきます.
(注:これは実際の道路の作成ではなく,使用可能な道が増えていくということです.)

従って,道路とクエリをそれぞれ年で管理して,年を最大値から減らしながら,その年に造られた道があったら都市を繋げて(同じ集合とみなし),その年が閾値のクエリがあったら出発地点が含まれる集合の要素数をクエリの番号で記録する作業を繰り返す方針で考えます.

ここでバラバラの都市を集合にまとめながらその集合内の個数を求めることが出来るデータ構造が(それもある程度の速度で)必要であることが分かります.

UnionFind

そこでUnionFind(素集合データ構造)を使います.
UnionFindは集合を管理するデータ構造で

  • 任意の二要素が属する集合を一つの集合に結合する
  • 任意の二要素が同一集合か否かを判定する.

の二つの操作を行うことが出来ます.

データ構造は木を用いて実現され,1つの木が一つの集合に対応し,木を連結させることで集合の結合を行い,二要素の根を探してそれが一致するかで判定を行います.

木を用いるために偏りが出て実行速度が落ちるのを防ぐために,

  • 経路圧縮:再帰的に根を調べるときに,要素を根につなぎ直す.
  • ランク:木の高さ(ランク)を管理し,ランクの低い木をランクの高い木に繋げる

の二手法が提案されていて,二つを組み合わせた実装も可能です.

今回は要素を配列で管理し,配列の値として親要素の番号を持つ方法で,経路圧縮のみを用いて実装します.
また,今回は集合の要素数が必要となるため,根要素の配列値として要素数を負にした値を持たせます.
実装すると以下のようになります.

gist2f7e1fce55a79a2ba8c5630cb37574f1

unionc言語由来の予約語に存在するため,結合操作の関数名はuniteにしています.

操作の計算量は{O\log(N)}です.
(根を再帰的に参照するroot関数がならし計算のために{O\log(N)}かかるため)

クラス

UnionFindの実装でクラスを用いたので軽く解説します.
クラスとはc言語的に言うと「関数を持つ構造体」のようなものです.
構造体の変数と同様に.で繋げて構造体の関数を呼び出すことが出来ます.
クラス内の変数,関数をメンバ変数,メンバ関数と言います.
実はここまで用いてきたSTLのコンテナなども全てクラスです.

返り値を持たない,クラス名と同名のメンバ関数コンストラクターと呼びます.
これは,クラスを実体化する(オブジェクトを生成する)際に呼び出される初期化用の関数です.
コンストラクターは引数の後に:で区切ってメンバ関数を引数で初期化できます.

また,クラスで宣言される変数関数はそのままではクラス内では参照できません.
クラス外から参照する必要のあるものはpublic:より下に記述します.

クラスを用いたオブジェクト指向は他にもクラスの継承などの重要な概念があるのですが,競技プログラミングではあまり利用しません.

満点解法

以上のことをまとめて実装すると以下のようになります.

gistb96577b78c6f740ee2b642f0fe215a36

edgeは各道路の繋げる都市を造った年ごとに格納したもので,
queryは各クエリの出発都市とクエリ番号を閾値の年ごとに格納したもので, ansは要素番号に対応したクエリの答えを格納します.

ちなみに,この実装は年を最大値から1ずつ減らすようにしていますが,edgequeryを造った年と閾値の年でソートした配列にして,マージのような作業を行うことで答えを出す実装も可能です.
もしも{y_i,w_i}の最大値が非常に大きい場合などはこちらで実装すべきでしょう.

まとめ

これでABC040の4問全てで満点を取ることが出来ました.

様々なアルゴリズムに触れることが出来る競技プログラミングの世界にぜひお越しください.

c++で競プロ入門(2)

今回はABC040のC問題を解いていきます.

まず前回は投稿後に色々修正してすみませんでした…
今回以降はなるべく減らします…

そもそもC言語c++の関係は?

前回さらっとifforを使ったのですが,きちんと書くのを忘れていました.
c++C言語を機能拡張したものです.
なので,C言語の機能をほぼそのまま使用できます.
従って,今後C言語にある機能は解説なしで使っていきます.

C問題 柱柱柱柱柱

abc040.contest.atcoder.jp

この問題ではc++vector,そして頻出アルゴリズム動的計画法(DP)を扱っていきます.

STL

vectorの説明の前に,c++で重要な概念の一つであるSTLについて説明します.
STL(Standard Template Library)はc++の標準ライブラリの一つで,データ構造や,それらの操作,アルゴリズム等を型に依存しないで実装されているライブラリです.
競技プログラミングではこれらを用いる場合が非常に多いです.

動的配列vector

vectorSTLの動的配列のコンテナ(データ構造)です.
vectorをインクルードして使用してください.

STLではコンテナ名の後に<type>の形で使用する形を指定します.
今回はint型で用いるので以下のように宣言します.

vector<int> hoge;

配列の要素の参照は普通の配列と同様に[]で行います.

push_back関数で末尾に要素を追加できます.
が,今回は宣言時に使用する大きさが分かっているので,宣言時にの大きさ指定を行います.
名前の後に(size)のようにするとsizeの数の要素数を持ち,さらに(size,init)のようにするとinitで初期化されます.

従って,今回の1整数nとn個の整数の入力部は以下のようになります.

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}

この時,{a_1〜a_n}{a_0〜a_{n-1}}に変えています.
つまり1オリジンだったものを0オリジンにしています.
競技プログラミングでは入力は1オリジンでも配列等の関係で内部的に0オリジンに直した方が良い場合が多々あります.
ただ,出力する際には1オリジンに戻し忘れないようにしましょう.

動的計画法(DP)

今回の問題は動的計画法(DP)で解くことができます.
動的計画法

  • 分割統治法
  • メモ化

を用いたアルゴリズムの総称です.
それぞれC問題を例に解説していきます.

分割統治法

分割統治法は問題を細かく分けて小さな問題の解から大きな問題の解を求める方法です.
今回の問題の場合は,「{x-1}本目の柱と{x-2}本目の柱までの最小移動コストが分かっている時,{x}本目までの最小移動コスト(これを{f(x)}と定義する)を求める」という小さな問題を考えます.

次の3つの場合を考えます.
{x=0}の時,まだ移動していないので移動コストは{f(0)=0}です.
{x=1}の時,一回だけ{0}本目の柱から{1}本目の柱まで移動したので,移動コストは{f(1)=|a_1-a_0|}です.
そして {x\ge2}の時は,{|a_x-a_{x-1}|+f(x-1)}か,{|a_x-a_{x-2}|+f(x-2)}のどちらか小さい方が{f(x)}の答えになるはずです.

この漸化式を再帰関数に落とし込んで実装すると以下のようになります.

gistf7473c2a8bda22edce7231f0d618cceb

再帰関数を使う関係でvector<int> aを大域変数にして,nの入力後に,resize()関数で要素数を指定しています.
(なお,このような使い方をするなら普通の配列を使った方が楽です.)

さて,このコードはサンプルケースでACします. しかしながらジャッジを通すとTLEします.

なぜでしょうか?
再帰関数は引数が01以外の場合,二つの再帰関数を呼び出します. 厳密な計算量は{O(N^2)}となります.
この計算量では,この問題の制約の最悪の場合({N=100,000})では,「時間制限 : 2sec」では終了しないのです.

メモ化

何度も呼び出される再帰関数ですが,実は引数が同じ値で何度も呼び出されています. 例えばf(5)f(4),f(3)を呼び出しますが,このf(4)f(3)を呼び出します.
これは非常に無駄です.

そこでメモ化です.
これは何度も同じ計算をする場合に最初の計算を記憶しておいて無駄な計算を減らす手法です.

まず思いつくのは再起関数f(x)の返り値を記憶する配列を別に用意し,もしその配列に値があればそれを返すようなf(x)に改良する方法です.
これはメモ化再帰と呼ばれるトップダウン動的計画法です.
しかし,これは実装が少々面倒です.

簡単に実装できてメモ化も実現できる方法があります.
それがボトムアップ動的計画法です.
どうせf(x)x0からn-1まで求めるのであれば,配列のまま,小さい数から計算をしていけば良いのです.

実装すると以下のようになります.

gist491497c8e9f1705a51ac9fb96ebb9f39

これはちゃんと制限時間内に終了し,ACします.
ちなみに計算量は{O(N)}です.

この動的計画法が使えるようになると解ける問題の幅がだいぶ広がります.

次回予告(D問題)

このままD問題に突っ込むと長くなるのでC,Dで分けます…
次回もぜひ読んでください.

c++で競プロ入門(1)

最近ラボの先輩やら情報の後輩氏がgitとかpythonの入門エントリーを書いてて,自分も何か書いてみようと思い,「c++で競プロ入門」と題してc++競技プログラミングの入門講座を書こうと思います.
試しにツイッターでアンケートをしたところ,以下のような結果になりました.

ということで,院試勉強の合間の息抜き程度にc++入門レベルで書きたいと思います. (院試勉強めんどい…)

基本的にc言語(ないし他の言語)が分かっている前提で解説します.

競技プログラミングとは

競技プログラミングとは,プログラミングを武器にアルゴリズム力や実装力を競う競技です.
競技ルールはコンテストやマラソン,AI等の様々なものがありますが,このエントリーでは一般的なコンテストを対象にします.
基本的なルールはこんな感じです.

  • 制限時間が短い(数時間)
  • 厳密解の求まる数個~十数個の問題が与えられる
  • 入力に対して正しい答えを出力するプログラムを作成し,提出
  • テストケースを全て正解できればその問題を解いたことになる
  • 解いた問題の数が多いほど順位が高い
  • 解いた数が同じなら最後に正解した問題の提出時刻が早い方が順位が高い
  • コンテストによっては誤答に時間ペナルティがある

AtCoder

僕が主に参加してるのはAtCoderのコンテストです.
ほぼ毎週土曜日に定例コンテスト(初心者向けのABCか上級者向けのARCのどちらか)が開催されます.
その他にも不定期のイベントがあります.

AtCoder (アットコーダー)

今回はこの中からABC(AtCoder Beginner Contest)040を解いていきたいと思います.

AtCoder Beginner Contest 040 - AtCoder Beginner Contest 040 | AtCoder

まず,最初に右上の新規登録からアカウント作成を行ってください.

アカウントを作成したら「問題」のタブから問題を見ましょう.
定例コンテストでは毎度4問出題されます.
では,各問題を解説していきます.

A問題 赤赤赤赤青

A: 赤赤赤赤青 - AtCoder Beginner Contest 040 | AtCoder

この問題ではc++の基本的な構文や入出力,AtCoderの使い方の話をします.

ライブラリ

まず,ライブラリのインクルードです.

#include <iostream>

今回の問題で必要なのは入出力だけです.

名前空間

ここで魔法の呪文が出てきます.

using namespace std;

c++には名前空間という概念があります.
異なるライブラリの同じ識別名を区別するためにあり,各識別名を利用する際は,hoge::piyo(名前空間hogeの識別名piyoを指す)のようにどの名前空間の識別名かを明示しなければなりません.
しかしながら,基本的にc++標準ライブラリしか用いない競技プログラミングにおいてはただただ面倒なだけです.
そこでこの魔法の呪文を書いておくことで,識別名単体の記述を可能にします.
(なお,一般には名前空間の汚染等の問題からあまり良いコードではないとされる場合が多いので気をつけて下さい.)

メイン関数

int main(void) {
    
    return 0;
}

メイン関数はc言語の場合と同じです.
コマンドライン引数は必要ないので引数はvoid返り値は正常終了の0です.

入出力

c++では入出力に入力演算子>>,出力演算子<<を用います.
変数と標準入力ストリームcin,標準出力ストリームcoutをこれらの演算子で繋げることで入出力ができます.
スペース区切りで次の変数へ格納されます.

今回のA問題では2整数が入力され,1整数を出力するので以下のようにします.

int n,x;
cin >> n >> x;

int ans;
cout << ans << endl;

endlを出力すると改行出力されます. 最後に改行がないと正しい答えだと判定されない場合が多いので気を付けて下さい.

解法

本題の問題の解き方です.
端は1番目の位置かn番目の位置の2通りなので,簡単な条件分岐で解けそうです.

1番目に来る場合はx-1回の交換が必要で,
n番目に来る場合はn-x回の交換が必要です.
このどちらか小さい方を出力すればいいことが分かります.

以下の簡単な条件分岐で実装できます.

if (x-1 < n-x){
    ans = x-1;
}else{
    ans = n-x;
}

提出&ジャッジ

これらをまとめると以下のようなコードになります.

gist7f95b3db41d292e17427d39d6dfa5643

まず,問題文の入出力例(サンプルケース)で,方針が合ってるかを確認します.

次に提出です.(この提出してソースコードが全てのテストケースで正解するか確認することをジャッジと言います)
問題文の最後の「提出する」ボタンか,上部の「提出」タブからソースコードの提出画面に行きます.
ここで,問題,言語を確認し,ソースコードをコピペし,「ソースコードを提出」ボタンを押します.
言語はデフォルトで「C++14(GCC)」なので弄らなくていいでしょう.
(余談ですが,ちょっと前まではデフォルトがbashで面倒でした.)

ソースコードを提出すると自分の結果画面に遷移します.
この画面では自分の提出したソースコードの一覧が見れます.
一番上にさっき提出したはずの投稿があるはずなので,「詳細を確認」のリンクを押します.

提出した各ソースコードのジャッジ結果がわかります.
「状態」がその問題に対するソースコードの結果です.
問題の「状態」が「AC」だったら正解です.

また,下には各テストケースに対する結果があります.
この「状態」には主に以下のようなものがあります.

  • AC (Accepted) 正解
  • WA (Wrong Answer) 誤答
  • CE (Compilation Error) コンパイルエラー
  • TLE (Time Limit Exceeded) 制限時間内にプログラムが終了しなかった
  • RE (Runtime Error) 実行時エラー

他にもMLE,OLE,IEなどがありますが,ほとんど出てこないです.

その他コンテスト,ジャッジシステムについて疑問があれば下のチュートリアル,ルール,用語集,よくある質問のページを読んでください.

このサイクルで問題をドンドン解いていきます.

最小

この問題,二つの数のどちらか小さい方なので「2値の最小値を取る関数とかないの?」と思った人がいるでしょう.
ちゃんとあります.
min(x,y)xyどちらか小さい方を返します.
(cの三項演算子(x<y?x:y)と同値です)
逆はmaxで大きい方を返します.

cout << min(x-1,n-x) << endl;

このmin,maxはとても良く使うので覚えておきましょう.

[2016年7月4日追記1] 厳密にはmin,maxalgorithmのインクルードが必要です.
僕の環境やAtCoderのジャッジではなくてもコンパイルが通ったのでリファレンスを見るまで気付きませんでした.
(後述のabscstdlibのインクルードなしでコンパイルが通ります.)
この現象,前はclangだけだったのですが,どこかのバージョン以降のgccでも出るようになりました.
忘れてても勝手にコンパイルが通るだけなので特に困る事はないはずです…
ただ,気持ちが悪いので調べているのですが,答えが出ません…

[2016年7月4日追記2] 知り合いの方からのご指摘で原因が分かりました.
「明示的にインクルードしたヘッダファイルが、内部でそれらをインクルードしてるから」のようです.
例えばclangの場合iostreamをインクルードすると,ios,__locale,string,algorithm再帰的にインクルードされます.

B問題 □□□□□

B: □□□□□ - AtCoder Beginner Contest 040 | AtCoder

この問題は全数探索の問題です.

絶対値

abs(x)xの絶対値を返します.
扱う値が整数の場合はcstdlibのインクルードを,
扱う値が実数の場合はcmathのインクルードをします.
(c++C言語の標準ライブラリを扱う場合は.hを除いて,冒頭にcを付加します.)

解法

x,横yの長方形を考えた時,「長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和」はabs(x-y)+n-x*yで表せます.

これを縦横の長さの組み全てを試します.
つまり,x1からnまで動かし,y1からn/xまで動かした時のabs(x-y)+n-x*yの最小値を求めれば良いことになります.
一見すると {O(n^2)} に見えますが実は {O(n\ {\rm ln}\ n)} なので実行時間は問題ありません.
(僕は別解法で問題を通して(ACして),コンテスト後の解説で想定解法の正しい実行時間を知りました…)

gist0d0b7da4ad970bde18a4503117950f80

次回予告(C,D問題)

C,D問題はA,Bに比べると難しく,解法が長くなるため,B問題までで第一回とします.
アルゴリズム的な話よりもc++AtCoderの話が中心になってしまいました.

研究室生活始まりました

新学期が始まって1週間ほど経ったので報告です.

研究室

研究室配属が決定しました. 無事第一希望のソフトウエア工学研究室に配属が決まりました. 最終的に予想外に人気だったようで,GPAがあまり高くない自分が溢れそうで怖かったですが,どうにか滑り込めたようです.

se.is.kit.ac.jp

自由な研究室なのでコアタイム等はないのですが,家にいたら遊ぶだけなのでここ一週間平日は毎日研究室に行ってます.(と言ってもプロコンの問題を解いてるだけなので遊んでるようなものですが…)

研究テーマはまだアバウトにしかありませんが,開発者研究者ツールの開発などに取り組みたいと考えています.

ロンダリング

大学院でロンダリングを考えていて,うちの大学の内部生向け推薦(3x3入試)を蹴りました. 「就職を考えると,関西で修士の2年を過ごすよりも関東で過ごした方が色々と楽になりそう」という非常に下心満載な安直な考えなので,失敗するかもしれません. 失敗したらそのまま工繊に残ります.

今期の授業

うちの大学は4回生で修士課程の講義を下履修できる制度があるので,ロンダ失敗の備えとどうせ学ぶなら早い方が良いと思い,授業を取ることにしました.授業ないとどうせ勉強しないだろうし…

今期は前半の1Qに4科目受講します.

基本的に研究に必要そうなものを中心に取りました.

今年度の予定

だいたい今後の予定としては

  • [1Q]上記授業の履修,数学の復習,オケ本番
  • [2Q]院試勉強
  • [夏休み]院試
  • [3Q]研究本格化
  • [4Q]研究仕上げ

みたいな感じになりそうです.

ブログを始めてみる

ブログ開設理由

最近情報系の幾つかのイベントに参加するものの,

体験記を書く先がないことに気づき,今更ながらブログを始めてみようと思います.

また,前々から技術的な調べ物の記録だったりアウトプットだったりをしたいと思っていたので,それを兼ねる予定です.

(イベントの参加だけだとまともに記事を書くネタがないので…)

自己紹介

京都工芸繊維大学情報工学課程B4の学生 出身は大阪だが,滋賀東京滋賀岡山と転々と移り住み,現在は京都市民 趣味は楽器(オーケストラでホルンを吹いている) あとミリオタだったりアニオタだったりする

最初の投稿はこんなもんで…

(Markdownに統一のため再投稿しました)