C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

2017年 進捗大反省会

昨年同様、今年1年の振り返り記事を残します。
独り反省会なので反省をポジティブにしていきます。

C++ について

C++を勉強しだして2年が経ちました。
まだまだ知識が浅く、基礎的な事も解らなかったり、知識が定着していなかったりするので、
C++ をもう一度軽くやり直したりしていました。
全体としては、今年は言語自体の勉強はあまり深くしなかったです。

学習方法として変わってきた事としては、学習 1 年目の頃は誰かが噛み砕いて書いているような Blog とかを好んで見ていたのですが、最近では解らない事があると C++ referenceC++ ポケットリファレンス(本)を良く見るようになりました。
少しは C++ に慣れてきた...(?)

競プロについて

アルゴリズム

今年はアルゴリズムの勉強を主にしていました。
初めはTLE本で問題を解きながら進めていたのですが、いつの間にか離脱...。
本に沿って勉強していると、解らないまま進んでしまえるので良くない気がして、途中から本で勉強を進めるのはやめました。*1
TLE本, 蟻本やチーター本は自分には難しく、全然勉強が進まなくなりました。

f:id:chiwawa_star:20171228223121p:plain

それからは、アルゴリズム理論の本を読んだり、自分に最適化された(易しい)資料を読む事で少しずつまた勉強を進める事ができました。
↑画像の本2冊は知識が何もない自分にも解りやすかった2冊で、学習の助けとなりました。
何事も一つひとつ自分の中で納得しないと進めない面倒なタイプなので*2、実装前に「動的計画法とは」みたいな勉強から始める方が自分には合っている気がしました。

本に沿って勉強するのをやめたので、主に yukicoder の問題を使って学習していました。
(同じ問題を何度も何度も解き直しをしていたので、yukicoder管理人のyukiさんには不審に思われていたかも知れない...。)

DFSも書けるようになってきたので、最近はずーーっとDP(knapsack, 数え上げ)の勉強を主にしています。

AC数

今年は考察ばかりに時間を割いていたので、AC数は少なく終わりました。
主に解いていた AtCoder と yukicoder 合わせて 140 くらいでしょうか...。
でも来年はもっと少ない予感しかない。

コンテスト

今年はコンテストもあまり参加しなくなってしまった。
理由は色々あったのですが、解決済みなので来年はもう少し参加したいですね。
あと運良く ABC で初めて全完出来たんですよ。


しかしこれは罠でこの後プロからこのケースで D 落ちますみたいな指摘を受け凹む(現実は厳しい)(でもそういう指摘はうれしい)
来年も地道に ABC 頑張りたいな(希望)

LaTeXについて

今年は LaTeX と出会いました。
始まりは Blog の数式部分が読みづらいよというご指摘を頂いたことでした。
指摘されるまで全然意識していなかったのですが、確かに他の人の Blog を見るとちゃんと数式部分は LaTeX で書かれていました。
別に強く勧められた訳ではなく、なんとなく MacTeX を DL して使ってみたら凄く直感的で感動しました。マークアップで文書作成出来るって凄い...!楽しい!!みたいな感想しかなかった。
自分は Adobe 生まれ Adobe 育ちなので、これまで文書作成は Illustrator だったのですが(レポート類も)、こんなに便利なものが世の中にあるのか...みたいな衝撃でした。
LaTeX は最高。


2018年の課題

2018年はもうこれしかないと思っていて、逆に他の事する時間もなさそう。
全振りしてしまっていいかは謎ですが...。
アルゴリズムの勉強法はまだ自分の中でしっくり来ていなくて、どう勉強を進めたら良いのかも模索中なのですが、自分の場合、習得を急いでいる訳ではないので楽しく勉強したいなと思っています。

とにかく動的計画法をマスターしないと!
本を良く読み理解して勉強する!解らない事は解るまで調べる!

  • 考察する

DP の問題もそうなんですが、典型的な問題が解けてもちょっと応用っぽくなると解けなかったりするので、深く考察するようにしたいです。

  • Effective に C++ を書く

C++ もまだまだ初心者以下なのでちゃんと勉強する。(Effective C++ と Effective STL を買った)
効率的なコードを書けるようになりたいです。

  • 解いた問題の記事を書く

復習という意味で、簡単な問題でも出来ればしっかり書きたいです。
今年は結構書いたんですが、殆どが下書き状態で終わったので...。
Blog を書きながら考察してたりして、実装に入ってしまうと放置になってしまうの良くないので最後まで書きたいですね。
記事を書くと「計算量違うよ!」とか「もっと良い方法あるよ!」等、わりとお声がけいただけるので、本当に有り難いです。(お気付きの点があればください!)


まとめ

1年間何してたんだろう...(成長なし)
来年は DP を頑張る!それだけ!


余談

実は夏頃に転職しました。
少しだけキャリアチェンジもしました。(チェンジと言う程でもないけれど)
新しい職場の開発環境(git)にもやっと慣れて...もいないのですが、炎上案件に放り込まれ、毎日楽しいです(真顔)

*1: 1つの単元が理解できて解けるようになったらまた本で学習を進めます。

*2:そのわりには適当です。

広告を非表示にする

二分探索で平方根を求める

二分探索の練習をしました。
追記:二分探索と書いたけれど、正しくは二分法 *1 かも知れない...。

整数 および 実数  x が与えられるので  y \ast y = x となるような y を絶対 or 相対誤差が 10^{-5} となる精度で求めてください。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    cin >> N;
    
    for( int i = 0; i < N; i++ )
    {
        double x;
        cin >> x;
        
        double left{}, right{ x }, mid{};
        
        if( x < 1 ) right = 1;
    
        while( right - left > 0.00001 )
        {
            mid = ( left + right ) / 2.0;
            if( mid * mid > x )
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
        cout << fixed << setprecision( 8 ) << mid << "  " << sqrt( x ) << endl;
    }
    return 0;
}

INPUT

5
2
4
0.5
0.1
10

OUTPUT

1.41420746  1.41421356
2.00000763  2.00000000
0.70709991  0.70710678
0.31623077  0.31622777
3.16227913  3.16227766

実行コードはこちら

  • x0 以下の場合の処理を忘れない。
  • while の loop 回数を 増やすと精度が上がって std::sqrt() *2 の結果に近くなる。


参考になる記事
satanic0258.hatenablog.com

std::tuple|C++

std::tuple の使い方を覚えたのでメモします。

std::tuple とは?
std::pair2 つの型の値を保持出来るのに対し、std::tupleN 個の型の値を保持する事ができる。*1


宣言・要素格納:

//宣言
vector<tuple<int, string, bool>> vc;
for( int i = 0; i < 3; ++i )
{
    string a;
    bool b;
    cin >> a >> b;
    //要素構築
    vc.emplace_back( i, a, b );
}

格納する値が全部 int の場合 vector<tuple<int, int, int>> vc; となる。
値の型が異なる場合は vector<tuple<int, string, bool>> vc; とできる。
要素構築(格納)は std::emplace_back などを使ってできる。


要素の取得

std::tuple::get *2 を使って各要素を取得できる。

for( auto x : vc )
{
    //位置を指定する場合(I番目の引数)
    cout << get<0>( x ) << " " << get<1>( x ) << " " << get<2>( x ) << endl;
}

⬆ I 番目の引数を指定する事で要素を取得できる。( tuple<0番目, 1番目, 2番目> の順 )

for( auto x : vc )
{
    //型を指定する場合
    cout << get<bool>( x ) << " " << get<string>( x ) << " " << get<int>( x ) << endl;
}

⬆引数の代わりに型を入れると、その型の要素が取得できる。

for( int i = 0; i < 3; ++i )
{
    //添字も使える
    cout << get<0>( vc[ i ] ) << " " << get<1>( vc[ i ] ) << " " << get<2>( vc[ i ] ) << endl;
}

⬆ range-based for でなく普通の for 文 + 添字 で要素の取得もできる。


要素をソート

sort( begin( vc ), end( vc ) );

⬆ sort した場合、tuple の第一要素、第二要素、第三要素の順で比較した結果が返ります。*3

sort( begin( vc ), end( vc ), greater<tuple<int, string, bool>>() );

⬆ 降順 sort は第三引数に greater<tuple<int, string, bool>>() を指定します。

sort( ALL( vc ), []( const auto &x, const auto &y )
         {
             //第一要素が同一ならば第二要素の小さい方を返す
             return get<0>( x ) == get<0>( y ) ? get<1>( x ) < get<1>( y ) : get<0>( x ) > get<0>( y );
         });

std::sort の第三引数にラムダで各要素の比較結果を返せるようにも書けます。


型の要素数取得

//型の要素数取得
cout << tuple_size<tuple<int, string, bool, int, int>>::value << endl;

tuple 型としてみなせる型の要素数を取得してくれます。*4
この場合は int, string, bool, int, int なので 5 が出力される。
vector に格納された要素数が知りたい場合は vc.size() で普通に求まる。



実行コード:[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ
std::tuple 便利すぎる...。色々な問題で使ってみたい!


広告を非表示にする

ABC072 - C Together|AtCoder

C: Together - AtCoder Beginner Contest 072 | AtCoder を解きました。

題意:

  • 長さ  N の整数列  a_1, a_2, ... a_N が与えられます。
  •  a_i に対し、1 足すか、1 引くか、何もしない、の 3 つの操作が選べるので、ある整数  X を選んだ時、  a_i = X となる  i の個数の最大値を出力する。
  •  1 \leq N \leq 10^5
  •  0 \leq a_i < 10^5 (1 \leq i \leq N )
  •  a_i は整数

考察:

 a_i に対し 3 つの操作は自由に選べる為、 a_i = X となる  i の個数が最大化される操作を選択をすれば良い。
 a_i に対し  a_i,  a_i + 1,  a_i -1 の操作後となる整数をカウントし、最終的に重複が一番多い  X の個数が 3 つの操作を最善に選んだ結果となるので、その個数が答え。

コード:

X-codeで競プロテンプレートを読み込む設定

この記事は macOS Sierra バージョン 10.12.6, X-code Version 8.3.3 での設定方法です。

X-code で競プロのテンプレートを読み込む設定に苦労したので自分用にメモ。
結論からいうと簡単にできた。


はじめに

設定の前に確認。

  • X-code ProjectMac OSCommand Line Tool
  • 使用言語は C++

上記 2 点が私の設定環境なので、ここが違うと設定ディレクトリなどが違うので注意。


準備

まず、変更したい Default テンプレートファイルは書き込み禁止になっているので、
パーミッション設定を変更する所から始める。

1. ディレクトリ移動する

この時、フォルダ名に半角スペースが入っているので「 \ (BackSpace)」でエスケープする

$ cd /Applications/Xcode.app/Contents/Developer/Library/Xcode/Templates/File\ Templates/Source/C++\ File.xctemplate
2. 書き込み権限付与する

ディレクトリ /Default/ 以下のファイルを変更できるように管理者権限 sudo を使って変更する
パスワードが求められるので、入力すると完了。

/*USER NAME の所には自分のUSER NAMEを入れる*/
sudo chown -R USER NAME Default


テンプレ変更

Finder で /Applications/Xcode.app/Contents/Developer/Library/Xcode/Templates/
File Templates/Source/C++ File.xctemplate/Default/
に移動

___FILEBASENAME___.cpp という cpp ファイルがあるので、これにテンプレを書く。
Default では以下のように書かれている。

//
//  ___FILENAME___
//  ___PROJECTNAME___
//
//  Created by ___FULLUSERNAME___ on ___DATE___.
//___COPYRIGHT___
//

#include <stdio.h>

これを全部消して、自分の好きなように書いて保存。
(準備でやった書き込み権限が上手く付与されていないと変更できない)


新規ファイル作成してみる

念のため、X-code を再起動し、Project を開く。
新規ファイル作成C++ ファイル を選択すると、競プロテンプレートが反映されている!(最高)

f:id:chiwawa_star:20170826161357p:plain

他に正しい方法があるかも知れないけれど、もうこれで満足です(おわり)