Mitä on kisakoodaus?

Kisakoodaus mittaa taitoa suunnitella ja toteuttaa algoritmeja. Kisoissa menestyminen vaatii kykyä ratkaista ongelmia sekä koodata nopeasti ja virheettömästi.

Ohjelmointikisassa on joukko tehtäviä, jotka täytyy ratkaista tietyn ajan kuluessa. Yleensä jokaisen tehtävän ratkaisu on ohjelma, joka lukee syötteen, ratkaisee tehtävän ja tulostaa vastauksen.

Ratkaisun arvostelu tapahtuu automaattisesti testaamalla sitä joukolla testisyötteitä. Testauksessa tutkitaan, toimiiko ratkaisu oikein ja riittävän tehokkaasti.

Esimerkkitehtävä

Annettuna on merkkijono, jossa on n merkkiä väliltä A–Z. Tehtäväsi on tutkia, saako merkkijonosta palindromin järjestämällä merkit sopivasti.

Esimerkiksi jos merkkijono on ABABC, siitä saa palindromin ABCBA. Merkkijonosta ABADC taas ei saa palindromia millään tavalla.

Ohjelmasi tulee tulostaa "YES", jos merkkijonosta saa palindromin, ja muuten "NO".

Ratkaisun idea

Lasketaan jokaisesta merkistä, montako kertaa se esiintyy merkkijonossa. Jos kaikkia merkkejä on parillinen määrä tai tasan yhtä merkkiä on pariton määrä, merkeistä voi muodostaa palindromin. Jälkimmäisessä tapauksessa pariton merkki on palindromin keskellä.

Ratkaisu C++-koodina

#include <iostream>

using namespace std;

string s;
int c[128];

int main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        c[s[i]]++;
    }
    int z = 0;
    for (int i = 'A'; i <= 'Z'; i++) {
        if (c[i]%2 == 1) z++;
    }
    if (z <= 1) cout << "YES\n";
    else cout << "NO\n";
}

Näin pääset alkuun

1. Opettele C++

Kisakoodaus vaatii sujuvaa ohjelmointitaitoa. Paras valinta kieleksi on C++, joka on tehokas ja jonka ominaisuudet sopivat hyvin kisakoodaukseen.

Kisakoodaus ei vaadi kielen erikoisominaisuuksien tuntemista. Muuttujat, taulukot, ehdot, silmukat ja funktiot riittävät pitkälle kisakoodauksessa.

2. Lue KKKK

Kisakoodarin käsikirja eli KKKK sisältää paljon tietoa kisakoodauksesta. Voit opetella sen avulla tärkeitä tietorakenteita ja algoritmeja. Voit kopioida KKKK:n itsellesi tästä.

KKKK sisältää myös syventäviä asioita algoritmiikasta, jotka ovat aluksi vaikeita. Kaikkea ei tarvitse oppia heti, vaan voit perehtyä asioihin pikkuhiljaa.

3. Harjoittele

Datatähden valmennuskurssi on hyvä paikka harjoitella kisakoodausta. Kurssi sisältää 200 tehtävää, jotka vaikeutuvat pikkuhiljaa. Kurssi on CSES:ssä ja pääset siihen tästä.

4. Osallistu kisoihin

Codeforces järjestää viikoittain nettikisoja. Sivuston käyttäjät ovat kahdessa sarjassa: aloittelijat ovat Div2:ssa ja pidemmälle päässeet ovat Div1:ssä.

Hyviä kisoja kisakoodauksen aloittamiseen ovat myös USACO ja COCI. Näitä kisoja järjestetään syksystä kevääseen noin kuukauden välein.

Osallistu kisoihin aina, kun pystyt. Mitä useammin osallistut, sitä enemmän opit.